Skip to content

Instantly share code, notes, and snippets.

@dkull
Created February 20, 2010 15:24
Show Gist options
  • Save dkull/309721 to your computer and use it in GitHub Desktop.
Save dkull/309721 to your computer and use it in GitHub Desktop.
Efficient SQAM(Square-And-Multiply) method for very! large integers. Several hundred digits is fine.
def sqam(self, base, exponent, modulus):
base = int(base)
exponent = int(exponent)
modulus = int(modulus)
z = 1
expBin = bin(exponent)[2:]
for i in expBin:
if (i == "1"):
z = base*z*z%modulus
else:
z = z*z%modulus
return z
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment