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)

- (A
_{1},A_{2},A_{3}) <- (1,0,m); (B_{1},B_{2},B_{3}) <- (0,1,b)ifB_{3}== 0returngcd(m,b) = A_{3}; no inverseifB_{3}== 1returngcd(m,b) = 1 ; b^{-1}mod m = B_{2}- Q <- floor(A
_{3}/ B_{3})- (T
_{1},T_{2},T_{3}) <- (A_{1}-Q×B_{1}, A_{2}-Q×B_{2}, A_{3}-Q×B_{3})- (A
_{1},A_{2},A_{3}) <- (B_{1},B_{2},B_{3})- (B
_{1},B_{2},B_{3}) <- (T_{1},T_{2},T_{3})- Goto step #2

Back to BogPeople.com