Lehmer's GCD algorithm

Lehmer's GCD algorithm, named after Derrick Henry Lehmer, is a rather fast GCD algorithm, an improvement on the simpler but slower Euclidean algorithm.

Algorithm

Lehmer noted that that most of the quotients from each step of the division part of the standard algorithm are small. (For example, Knuth observed that the quotients 1, 2, and 3 comprise 67.7% of all quotientsKnuth, "The Art of Computer Programming vol 2 "Seminumerical algorithms", chapter 4.5.3 Theorem E.] .)

Say we want to obtain the GCD of the two integers "a" and "b". Let "a" ≥ "b".
* If "b" contains only one digit (in the chosen base, say $eta=1000$ or $eta=2^{32}$ ), use some other method, such as the Euclidean algorithm, to obtain the result.
* If "a" and "b" differ in the length of digits, perform a division so that "a" and "b" are equal in length, with length equal to "m".
* Iterate until one of "a" or "b" is zero:
** Decrease "m" by one. Let "x" be the leading (most significant) digit in "a", $x=a ext{ div } eta^m$ and "y" the leading digit in "b", $y=b ext{ div } eta^m$ .
** Initialize a 2 by 3 matrix $extstyle egin{bmatrix} A & B & x\ C & D & y end{bmatrix}$ to an extended identity matrix $extstyle egin{bmatrix} 1 & 0 & x \ 0 & 1 & yend{bmatrix}$ , and perform the euclidean algorithm simultaneously on the pairs $(x+A,y+C)$ and $(x+B,y+D)$ , until the quotients differ. That is, iterate:
*** Compute the quotients "w"₁ of the long divisions of ("x" + "A") by ("y" + "C") and "w"₂ of ("x" + "B") by ("y" + "D") respectively. Also let "w" be the (not computed) quotient from the current long division in the chain of long divisions of the euclidean algorithm.
*** If "w"₁ ≠ "w"₂, then break out of the inner iteration. Else set "w" to "w"₁ (or "w"₂).
*** Set our current matrix:::: $extstyle egin{bmatrix} A & B & x \ C & D & y end{bmatrix}$ ::: to:::: $extstyle egin{bmatrix} 0 & 1 \ 1 & -w end{bmatrix} cdot egin{bmatrix} A & B & x \ C & D & y end{bmatrix} = egin{bmatrix} C & D &y \ A - wC & B - wD & x-wy end{bmatrix}$
*** If "B" = 0, we have reached a "deadlock"; perform a normal step of the euclidean algorithm with "a" and "b", and recompute the matrix.
** Set "a" to "aA" + "bB" and "b" to "Ca" + "Db" (again simultaneously). This applies the steps of the euclidean algorithm that were performed on the leading digits in compressed form to the long integers "a" and "b". Restart the outer iteration.

References

* Kapil Paranjape, [http://www.imsc.res.in/~kapil/crypto/notes/node11.html Lehmer's Algorithm]

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

Euclidean algorithm — In number theory, the Euclidean algorithm (also called Euclid s algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). Its major significance is that it does… … Wikipedia
Derrick Henry Lehmer — Born February 23, 1905(1905 02 23) Berkeley, California Died May 22, 1991(1991 05 22) (aged&# … Wikipedia
Williams' p + 1 algorithm — In computational number theory, Williams p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic group factorisation algorithms. It was invented by Hugh C. Williams in 1982. It works well if the number N to be… … Wikipedia
Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… … Wikipedia
Cipolla's algorithm — In computational number theory, Cipolla s algorithm is a technique for solving a congruence of the form x2 = n, where , so n is the square of x, and where p is an odd prime. Here denotes the finite field with p elements; . Th … Wikipedia
Cornacchia's algorithm — In computational number theory, Cornacchia s algorithm is an algorithm for solving the Diophantine equation x2 + dy2 = m, where and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia[1]. Contents 1 The algorithm … Wikipedia
List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… … Wikipedia
AKS primality test — The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra… … Wikipedia
Dixon's factorization method — In number theory, Dixon s factorization method (also Dixon s random squares method[1] or Dixon s algorithm) is a general purpose integer factorization algorithm; it is the prototypical factor base method, and the only factor base method for which … Wikipedia
Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… … Wikipedia

Academic Dictionaries and Encyclopedias

Lehmer's GCD algorithm

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Lehmer's GCD algorithm

Look at other dictionaries:

Share the article and excerpts

Direct link