The Euclidean algorithm (also called Euclid's algorithm) is an efficient method for computing the greatest common divisor (GCD), also known as the greatest common factor (GCF) or highest common factor (HCF). It is named after the Greek mathematician Euclid, who described it in Books VII and X of his Elements.
Number of steps
Number of steps in the Euclidean algorithm for
. Red points indicate relatively few steps (quick), whereas yellow, green and blue points indicate successively more steps (slow). The largest blue area follows the line
represents the Golden ratio
The number of steps to calculate the GCD
of two natural numbers
, may be denoted by
is the GCD
for two coprime
as may be seen by dividing all the steps in the Euclidean algorithm by
By the same argument, the number of steps remains the same if
are multiplied by a common factor
Therefore, the number of steps
may vary dramatically between neighboring pairs of numbers, such as
, depending on the size of the two GCDs
The recursive nature of the Euclidean algorithm gives another equation
Worst case number of steps
If the Euclidean algorithm requires
steps for a pair of natural numbers
, the smallest values of
for which this is true are the Fibonacci numbers
This can be shown by induction
with no remainder; the smallest natural numbers for which this is true is
, which are
, respectively. Now assume that the result holds for all values of
. The first step of the
-step algorithm is
and the second step is
Since the algorithm is recursive, it required
steps to find
and their smallest values are
. The smallest value of
is therefore when
, which gives
|a = b + r0 = FM + 1 + FM = FM + 2|
. This proof, published by Gabriel Lamé
in 1844, represents the beginning of computational complexity theory
and also the first practical application of the Fibonacci numbers
This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10).
For if the algorithm requires
is greater than or equal to
which in turn is greater than or equal to
is the golden ratio
|log10 ϕ > , < log10 ϕ logϕ b = log10 b.|
. Thus, the Euclidean algorithm always needs less than
is the number of digits in the smaller number
Calculating a greatest common divisor is an essential step in several integer factorization algorithms, such as Pollard's rho algorithm, Shor's algorithm, Dixon's factorization method and the Lenstra elliptic curve factorization. The Euclidean algorithm may be used to find this GCD efficiently. Continued fraction factorization uses continued fractions, which are determined using Euclid's algorithm.
The Euclidean algorithm can be adapted to some other domains. Those domains in which the Euclidean algorithm can be adapted and implemented are then called Euclidean domains.
- ↑ Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications.
- ↑ 2.0 2.1 Knuth, p. 344.
- ↑ Ore, p. 45.
- ↑ 4.0 4.1 Knuth, p. 343.
- ↑ Mollin, p. 21.
- ↑ LeVeque, p. 35.
- ↑ Mollin, pp. 21–22.
- ↑ Crandall R., Pomerance C. (2001). Prime Numbers: A Computational Perspective (1st ed.). New York: Springer-Verlag. pp. 225–349. ISBN 0-387-94777-9.
- ↑ Knuth, pp. 369–371.
- ↑ Shor P.W. (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM J. Sci. Statist. Comput. 26: pp. 1484.
- ↑ Dixon J.D. (1981). “Asymptotically fast factorization of integers”. Math. Comput. 36 (153): pp. 255–260. doi:10.2307/2007743. http://jstor.org/stable/2007743.
- ↑ Lenstra Jr. H.W. (1987). “Factoring integers with elliptic curves”. Annals of Mathematics 126 (3): pp. 649–673. doi:10.2307/1971363. http://jstor.org/stable/1971363.
- ↑ Knuth, pp. 380–384.