288 ARITHMETIC 4.3.3 This leaves us with operation (Web server address)
288 ARITHMETIC 4.3.3 This leaves us with operation (d), which seems to be quite a difficult computation; but Schiinhage has found an ingenious way to perform step (d) in O(pk logpk) cycles, and this is the crux of the method. As a consequence, we have tk = 6tk–1 + o(pk l%Pk). Since pk = 3k+2 + 17, we can show that the time for n-bit multiplication is T(n) = O(N loga 6) = o(~1.63). (23) (See exercise 7.) Although the modular method is more complicated than the O(n1z3) pro- cedure discussed at the beginning of this section, Eq. (23) shows that it does, in fact, lead to an execution time substantially better than O(n2) for the mul- tiplication of n-bit numbers. Thus we can improve on the classical method by using either of two completely different approaches. Let us now analyze operation (d) above. Assume that we are given a set of positive integers el < ez < . . < e,, relatively prime in pairs; let ml = 2e -1, 77x2 = 2ez -1, . . .) m, = 2=T-1. (24) We are also given numbers WI, . . . , w7 such that 0 2 Wj 2 mj. Our job is to determine the binary representation of the number w that satisfies the conditions 0 2 w < mlm2...m,, w - WI (modulo ml), . . . , w G wr (modulo m,). (25) The method is based on (23) and (24) of Section 4.3.2. First we compute W> = (. . . ((Wj -Wi) Clj -W ,) Cq -+ * * -~5~~) c(j-l)j modmj, (26) for j = 2, . . . , r, where w: = wr modml; then we compute w=(.. . (w’,m,-1 + wGml) mT-2 +. . * + 4) ml + 4. (27) Here Cij is a number such that cijmi E 1 (modulo my); these numbers Cij are not given, they must be determined from the ej s. The calculation of (26) for all j involves (3 additions modulo mj, each of which takes O(e,) cycles, plus (i) multiplications by Cij, modulo mj. The calculation of w by formula (27) involves T additions and T multiplications by mj; it is easy to multiply by mj, since this is just adding, shifting, and subtracting, so it is clear that the evaluation of Eq. (27) takes O(r2e,) cycles. We will soon see that each of the multiplications by cij, modulo mj, requires only O(e, log e,) cycles, and therefore it is possible to complete the entire job of conversion in O(r2e, loge,) cycles.