Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW

Hermann-SW/gcd.bc

Created November 18, 2022 16:53
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/46c0ed01a59ebaec354b1b7e1c31a13b to your computer and use it in GitHub Desktop.
Save Hermann-SW/46c0ed01a59ebaec354b1b7e1c31a13b to your computer and use it in GitHub Desktop.
Download ZIP
greatest common divisor / lowest common multiple
Raw
gcd.bc
define gcd_(a, b) {
if (b==0) return a
return gcd_(b, a%b)
}
define gcd(a, b) {
if (a<b) return gcd_(b, a)
return gcd_(a, b)
}
define lcm(a, b) {
return a*b/gcd(a,b)
}
@Hermann-SW
Copy link
Author 

pi@pi400-64:~ $ bc -q gcd.bc powm.bc 
p=3490529510847650949147849619903898133417764638493387843990820577
q=32769132993266709549961988190834461413177642967992942539798288533
n=p*q
phi=(p-1)*(q-1)
gcd(p-1, q-1)
4
powm(2, phi/(2^4), n)
1
powm(2, phi/(2^5), n)
42836191202508728742199299040582900202976222916017767167551870216509\
444518239462186379470569442055101392992293082259601738228702
lcm(21,28)
84

powm() here:
https://gist.github.com/Hermann-SW/aefd972ef795347bd5cc7ec4557a769f

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