Difference between revisions of "Euclidean algorithm"

Latest revision as of 08:53, 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

@@ Line 30: / Line 30: @@
 ===The algorithm computes the GCD===
 Equally important is the proof that the algorithm always outputs the [[GCD]] of {{M|a}} and {{M|b}}
+==See next==
+* [[Extended Euclidean algorithm]]
+==See also==
+* [[GCD]]
+* [[Divisor]]
+* [[Division algorithm]]
 ==References==