Difference between revisions of "Euclidean algorithm"

Revision as of 08:52, 21 May 2015

Note: this is an algorithm for computing the GCD of two positive integers

The algorithm is as follows^[1]:

Input	$a,b\in\mathbb{N}_+$ , such that $a\ge b$ (swap them around if $a< b$ )
Output	The GCD of $a$ and $b$
Process	Let $A=a$ Let $B=b$ Let $R=$ the remainder of $A\div B$ (see Division algorithm) If $R=0$ then: RETURN: $B$ (we have $B=\text{gcd}(a,b)$ ) Let $A=B$ Let $B=R$ Goto step 3

TODO: These proofs

Given this algorithm loops until $R=0$ it is important to know for certain that eventually we will have $R=0$

Equally important is the proof that the algorithm always outputs the GCD of $a$ and $b$

Jump up ↑ The mathematics of ciphers, Number theory and RSA cryptography - S. C. Coutinho