Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW

Hermann-SW/powm.bc

Last active November 18, 2022 14:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Hermann-SW/aefd972ef795347bd5cc7ec4557a769f to your computer and use it in GitHub Desktop.
Save Hermann-SW/aefd972ef795347bd5cc7ec4557a769f to your computer and use it in GitHub Desktop.
Download ZIP
bc equivalent to gmp powm() "power mod" function
Raw
powm.bc
define powm_(a, e, n) {
if (e==1) return a%n
p = powm_(a, e/2, n)
if (e%2==0) { return p*p%n } else { return a*p*p%n }
}
define powm(a, e, n) {
if (e==0) return 1
return powm_(a, e, n)
}
@Hermann-SW
Copy link
Author

Fermat little theorem 100-digit number example (RSA-100):
https://en.wikipedia.org/wiki/RSA_numbers#RSA-100

pi@pi400-64:~ $ bc -q powm.bc
p=37975227936943673922808872755445627854565536638199
q=40094690950920881030683735292761468389214899724061
n=p*q
phi=(p-1)*(q-1)
powm(2, phi, n)
1

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment