Free web space - 586 ANSWERS TO EXERCISES 4.3.2 6. (a) If
586 ANSWERS TO EXERCISES 4.3.2 6. (a) If e = f + kg, then 2 = 2f(2g)k = af . lk (modulo 2g -1). So if 2 = 2f (modulo 2g -l), we have 2e modg = af modg (modulo 2g -1); and since the latter quantities lie between zero and 2g -1 we must have e mod g = f mod g. (b) By part (a), (1 + zd + . . . + 2(c- )d). (ze -1) E (1 + sd + . . . + 2(c-1)d). (zd -1) = zCd-1 E 2 -1 = 2l -1 = 1 (modulo af -1). 7.(u, -(2)1 +ml(V2 fmz(w3 + +~~-2w~-l)…)))Cl~ . ..C(2-l)j = (Uj -W1)C13 . . .c(J-l)J -Tnlz)ZC13 . ..C(j-l)j -. . . -ml m,7-2w,-lclj.. . C(j-1)j E (IL7 -211) Clj . . . C(J-l)j -wzc23 c(J-l)j –w3-lC(j-l)j = ( . . . ((uj -vi) cij -~2) CQ -. . -~~-1) c(J-l)j (modulo mj). This method of rewriting the formulas uses the same number of arithmetic opera- tions and fewer constants; but the number of constants is fewer only if we order the moduli so that ml < m2 < . < m,, otherwise we would need a table of m, mod m3. This ordering of the moduli might seem to require more computation than if we made ml the largest, m2 the next largest, etc., since there are many more operations to be done modulo m, than modulo ml; but since VU~ can be as large as m3 -1, we are better off with ml < m2 < … < rnT in (23) 1 So this idea appears to be preferable to a so. the formulas in the text, although the formulas in the text are advantageous when the moduli have the form (14) as shown in Section 4.3.3. 8. m3–1.. .miw3 = m3-l.. . ml(…((u,-Wl ) Clj -V2)C2j - -w j-l)c(,-l)~ E m3-2.. ml ( . . . (uj -WI) cl2 -. . . -wJ-2)c(j-2j3 -w3–lm3-2.. ml = z uj -vi -wsml -. . - wl-im,-s . . ml (modulo m3). 9. ur + ((…(v,m,-1 +w7-l)mr–2 +…)rnl +wl)modm,, . . . . u2 +– (w,m, + wi)modm2, u1 t w1 modmi. (The computation should be done in this order, if we want to let uj and wj share the same memory locations, as they can in (23).) 10. If we redefine the mod operator so that it produces residues in the symmetrical range, the basic formulas (2), (3), (4) for arithmetic and (23), (24) for conversion remain the same, and the number u in (24) lies in the desired range (10). (Here (24) is a balanced mixed-radix notation, generalizing balanced ternary notation.) The comparison of two numbers may still be done from left to right, in the simple manner described in the text. Furthermore, it is possible to retain the value u3 in a single computer word, if we have signed magnitude representation within the computer, even if rnj is almost twice the word size. But the arithmetic operations analogous to (11) and (12) are more difficult, so it appears that on most computers this idea would result in slightly slower operation. 11. Multiply by m-t1 ml + 1 mr + 1 -= 2 ( 2 ” 2 1. Note that 2t.q = t (modulo m). In general if w is relatively prime to m, then we can find (by Euclid s algorithm) a number w = (vi,. . . , vi) such that VW = 1 (modulo m); and then if u is known to be a multiple of w we have u/w = uw , where the latter is computed with modular multiplication. When w is not relatively prime to m, division is much more difficult.