Reduction methods for moduli of special form
When the modulus has a special (customized) form, reduction techniques can be employed to allow more efficient computation. Suppose that the modulus m is a / -digit base b positive integer of the form m = // - c, where c is an /-digit base 6 positive integer (for some / < t). Algorithm 14.47 computes x mod m for any positive integer x by using only shifts, additions, and single-precision multiplications of base b numbers.
14.47 Algorithm Reduction modulo m = b* - c
INPUT: a base 6, positive integer x, and a modulus m = b* - c, where c is an /-digit base b integer for some / < t.
OUTPUT: r = x mod m.
- 1. qo^lx/b^{1}], ro^x-qob*, r-t-r_{0}, /•/-().
- 2. While q, > 0 do the following:
- 2.1 q_{i+}i^[q_{i}c/b^{t}, r_{i+}i<-gjC - qi+ib*.
- 2.2 i<—i + 1, r<— r + Vi.
- 3. While r > m do: r«— r — m.
- 4. Retum(r).
- 14.48 Example (reduction modulo b^{l} - c) Let b = 4, rn = 935 = (32213)_{4}, and x = 31085 = (13211231)4- Since m = 4^{5} - (1121)_{4}, take c = (1121)_{4}. Here / = 5 and / = 4. Table 14.9 displays the quotients and remainders produced by Algorithm 14.47. At the beginning of step 3, r = (102031)_{4}. Since r > m, step 3 computes r — m = (3212)_{4}. □
i |
qt-ic |
Яг |
Ti |
r |
0 |
- |
(132)4 |
(11231)4 |
(11231)4 |
1 |
(221232)4 |
(2)4 |
(21232)4 |
(33123)4 |
2 |
(2302)_{4} |
(0)4 |
(2302)4 |
(102031)4 |
Table 14.9: Reduction modulo rn = b' - c (see Example 14.48).
14.49 Fact (termination) For some integer .s > 0, q_{s} = 0; hence, Algorithm 14.47 terminates.
Justification. q_{t}c = qt+ib*+r_{i+1},i > 0. Since c < //, q, = (q_{i+}ib^{l}/c) + (r_{i+}i/c) > q_{i+1}. Since the q, ’s are non-negative integers which strictly decrease as i increases, there is some integer .s > 0 such that q_{s} = 0.
14.50 Fact (correctness) Algorithm 14.47 terminates with the correct residue modulo m.
Justification. Suppose that s is the smallest index i for which q_{t} = 0 (i.e., q_{s} = 0). Now, x = q_{0}b^{(} + ro and q_{t}c =
x + (Е-Го 9») ^{c =} (E*=o Ji) b* + Ei=oSince I/ = c (mod m), it follows that
x = E'J=o ^{r}i (mod m). Hence, repeated subtraction of m from r = EL о ^{r}i gives the correct residue.
- 14.51 Note (computational efficiency of reduction modulo I/ - c)
- (i) Suppose that x has 21 base b digits. If l < t/2, then Algoritlmi 14.47 executes step 2 at most s = 3 times, requiring 2 multiplications by c. In general, if l is approximately (s - 2)t/(s - 1), then Algorithm 14.47 executes step 2 about s times. Tlius, Algorithm 14.47 requires about si single-precision multiplications.
- (ii) If c has few non-zero digits, then multiplication by c will be relatively inexpensive. If c is large but has few non-zero digits, the number of iterations of Algorithm 14.47 will be greater, but each iteration requires a very simple multiplication.
- 14.52 Note (modifications) Algorithm 14.47 can be modified if m = b^{[1]} ^{[2]} ^{[3]} ^{[4]} + c for some positive integer с < Ь^{г} in step 2.2, replace r<—r + r, with r«—r + (—l)Vj.
- 14.53 Remark (using moduli of a special form) Selecting RSA moduli of the form h^{[2]} ± c for small values of c limits the choices of primes p and q. Care must also be exercised when selecting moduli of a special form, so that factoring is not made substantially easier; this is because numbers of this form are more susceptible to factoring by the special number field sieve (see §3.2.7). A similar statement can be made regarding the selection of primes of a special form for cryptographic schemes based on the discrete logarithm problem.
- [1] INPUT: two positive integers x and у with x > y. OUTPUT: gcd(:r, у).
- [2] 1.
- [3] While both x and у are even do the following: x<-x/2, y<—y/2, д<—2д.
- [4] While x Ф 0 do the following: 3.1 While x is even do: x<-x/2. 3.2 While у is even do: y<—y/2. 3.3 x — y/2. 3.4 If x > у then x<-t otherwise, y<-t.
- [5] 1.