Skip to content

Instantly share code, notes, and snippets.

@arya-oss
Created December 4, 2016 13:14
Show Gist options
  • Save arya-oss/07175c9e4bb88981b5cd929acfb90cdc to your computer and use it in GitHub Desktop.
Save arya-oss/07175c9e4bb88981b5cd929acfb90cdc to your computer and use it in GitHub Desktop.
Calculate a^b mod n, used in cryptography
def powmod(a,b,n):
'''
calculates a^b mod n
:a base number
:b power
:n A prime number
'''
c = 0
f = 1
k = b.bit_length()
while k >= 0:
c *= 2
f = (f*f)%n
if b & (1 << k):
c += 1
f = (f*a) % n
k -= 1
return f
if __name__='__main__':
assert(powmod(2,5,17) == 15)
assert(powmod(2,4,17) == 16)
assert(powmod(3,3,17) == 10)
assert(powmod(3,4,17) == 13)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment