Euclid's Extended Algorithm

This page contains an implementation of the extended version of Euclid's Algorithm for calculating the Greatest Common Divisor of two numbers and also the multiplicative inverse of a number b mod a modulus m

This algorithm is at the core of the RSA algorithm for public-key encryption

Q A1 A2 A3 B1 B2 B3
- 1 0 0 1

EXTENDED EUCLID(m,b)
  1. (A1,A2,A3) <- (1,0,m); (B1,B2,B3) <- (0,1,b)
  2. if B3 == 0 return gcd(m,b) = A3; no inverse
  3. if B3 == 1 return gcd(m,b) = 1 ; b-1 mod m = B2
  4. Q <- floor(A3 / B3)
  5. (T1,T2,T3) <- (A1-Q×B1, A2-Q×B2, A3-Q×B3)
  6. (A1,A2,A3) <- (B1,B2,B3)
  7. (B1,B2,B3) <- (T1,T2,T3)
  8. Goto step #2

:-)
Back to BogPeople.com