Difference between revisions of "Euclidean algorithm"
From Maths
(Created page with "'''Note:''' this is an algorithm for computing the GCD of two positive integers ==Definition== The algorithm is as follows<ref>The mathematics of ciphers, Number theory a...") |
m |
||
| Line 30: | Line 30: | ||
===The algorithm computes the GCD=== | ===The algorithm computes the GCD=== | ||
Equally important is the proof that the algorithm always outputs the [[GCD]] of {{M|a}} and {{M|b}} | 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== | ==References== | ||
Latest revision as of 08:53, 21 May 2015
Note: this is an algorithm for computing the GCD of two positive integers
Contents
Definition
The algorithm is as follows[1]:
| Input | [ilmath]a,b\in\mathbb{N}_+[/ilmath], such that [ilmath]a\ge b[/ilmath] (swap them around if [ilmath]a< b[/ilmath]) |
|---|---|
| Output | The GCD of [ilmath]a[/ilmath] and [ilmath]b[/ilmath] |
| Process |
|
Proofs of correctness
TODO: These proofs
The algorithm terminates
Given this algorithm loops until [ilmath]R=0[/ilmath] it is important to know for certain that eventually we will have [ilmath]R=0[/ilmath]
The algorithm computes the GCD
Equally important is the proof that the algorithm always outputs the GCD of [ilmath]a[/ilmath] and [ilmath]b[/ilmath]
See next
See also
References
- ↑ The mathematics of ciphers, Number theory and RSA cryptography - S. C. Coutinho
