Greatest common divisor algorithms
Many situations in cryptography require the computation of the greatest common divisor (gcd) of two positive integers (see Definition 2.86). Algorithm 2.104 describes the classical Euclidean algorithm for this computation. For multiple-precision integers, Algorithm 2.104 requires a multiple-precision division at step 1.1 which is a relatively expensive operation. This section describes three methods for computing the gcd which are more efficient than the classical approach using multiple-precision numbers. The first is non-Euclidean and is referred to as the binary gcd algorithm (§14.4.1). Although it requires more steps than the classical algorithm, the binary gcd algorithm eliminates the computationally expensive division and replaces it with elementary shifts and additions. Lehmer’s gcd algorithm (§14.4.2) is a variant of the classical algorithm more suited to multiple-precision computations. A binary version of the extended Euclidean algorithm is given in §14.4.3.
Binary gcd algorithm
- 14.54 Algorithm Binary gcd algorithm
- 5
14.55 Example (binary> gcd algorithm) The following table displays the steps performed by Algorithm 14.54 for computing gcd(1764,868) = 28. □
X |
1764 |
441 |
112 |
7 |
7 |
7 |
7 |
7 |
0 |
У |
868 |
217 |
217 |
217 |
105 |
49 |
21 |
7 |
7 |
9 |
1 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
- 14.56 Note (computational efficiency of Algorithm 14.54)
- (i) If x and у are in radix 2 representation, then the divisions by 2 are simply right-shifts.
- (ii) Step 3.3 for multiple-precision integers can be computed using Algorithm 14.9.
Lehmer’s gcd algorithm
Algorithm 14.57 is a variant of the classical Euclidean algorithm (Algorithm 2.104) and is suited to computations involving multiple-precision integers. It replaces many of the multiple-precision divisions by simpler single-precision operations.
Let x and у be positive integers in radix b representation, with x > y. Without loss of generality, assume that x and у have the same number of base b digits throughout Algorithm 14.57; this may necessitate padding the high-order digits of у with 0’s.
14.57 Algorithm Lehmer’s gcd algorithm
INPUT: two positive integers x and у in radix b representation, with x > y. OUTPUT: gcd(:r, y).
- 1. While у > b do the following:
- 1.1 Set x, у to be the high-order digit of x, у, respectively (y could be 0).
- 1.2 At—1, Bt—0, Ct—0, Dt—1.
- 1.3 While (у + C) f 0 and (y + D ) f 0 do the following:
q<- l(x + A)/(y + C), q‘V L(* + B)/(y + D)J.
If q ф q' then go to step 1.4.
tt—A — qC, At—(7, Ct—t, tt—В — qD, Bt—D, Dt—t. ttr-x - qy, xt y, yt-t.
- 1.4 If В = 0, then Tt—x mod y, xt^y, yt—T otherwise, Ttr-Ax + By, u-^Cx + Dy, xt—T yt—u.
- 2. Compute v = gcd(a:, y) using Algorithm 2.104.
- 3. Retum(u).
- 1
- 14.59 Note (computational efficiency of Algorithm 14.57)
- (i) Step 1.3 attempts to simulate multiple-precision divisions by much simpler singleprecision operations. In each iteration of step 1.3, all computations are single precision. The number of iterations of step 1.3 depends on b.
- (ii) The modular reduction in step 1.4 is a multiple-precision operation. The other operations are multiple-precision, but require only linear time since the multipliers are single precision.
- 14.60 Example (Lehmer’s gcd algorithm) Let b = 10^{3}, x = 768454 923, and у = 542 167814. Since b = 10^{3}, the high-order digits of x and у are x = 768 and у = 542, respectively. Table 14.10 displays the values of the variables at various stages of Algorithm 14.57. The single-precision computations (Step 1.3) when q = q' are shown in Table 14.11. Hence
gcd(ar, y) = 1. □