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