# 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/b1], ro^x-qob*, r-t-r0, /•/-().
• 2. While q, > 0 do the following:
• 2.1 qi+i^[qic/bt, ri+i<-gjC - qi+ib*.
• 2.2 i<—i + 1, r<— r + Vi.
• 3. While r > m do: r«— rm.
• 4. Retum(r).
• 14.48 Example (reduction modulo bl - c) Let b = 4, rn = 935 = (32213)4, and x = 31085 = (13211231)4- Since m = 45 - (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, qs = 0; hence, Algorithm 14.47 terminates.

Justification. qtc = qt+ib*+ri+1,i > 0. Since c < //, q, = (qi+ibl/c) + (ri+i/c) > qi+1. Since the q, ’s are non-negative integers which strictly decrease as i increases, there is some integer .s > 0 such that qs = 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 qt = 0 (i.e., qs = 0). Now, x = q0b( + ro and qtc = l+i// + ri+4, 0 < i < s 1. Adding these equations gives

x + (Е-Го 9») c = (E*=o Ji) b* + Ei=oSince I/ = c (mod m), it follows that

x = E'J=o ri (mod m). Hence, repeated subtraction of m from r = EL о ri 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.