610 ANSWERS (Free web servers) TO EXERCISES 4.5.4 11. U V
610 ANSWERS TO EXERCISES 4.5.4 11. U V A P S T output 1984 1 0 992 0 - 1981 1981 1 992 1 1981 1983 4 495 993 0 1 9932 E +22 1983 991 2 98109 1 991 1981 4 495 2 0 1 22 E +22 1984 1981 1 99099 1 1981 1984 1 1984 99101 0 1 991012 Z!! +2O The factorization 199 991 is evident from the first or last outputs. The shortness of the cycle, and the appearance of the well-known number 1984, are probably just coincidences. 12. The following algorithm makes use of an auxiliary (m + 1) X (m + 1) matrix of single-precision integers Ejk, 0 2 j, Ic 5 m; a single-precision vector (bo, br, . . . , bm); and a multiple-precision vector (20, ~1,. . , 2,) with entries in the range 0 2 xk < N. Fl. [Initialize.] Set b, + -1 for 0 5 i 2 m; then set j + 0. F2. [Next solution.] Get the next output (x, eo, el, . . , e,) produced by Algorithm E. (It is convenient to regard Algorithms E and F as coroutines.) Set k + 0. F3. [Search for odd.] If k > m go to step F5. Otherwise if ek is even, set k + k + 1 and repeat this step. F4. [Linear dependence?] If bk 2 0, then set i + bk, x + (s,z)modN, e, + e7 + E,, for 0 5 r 2 m; set k + k + 1 and return to F3. Otherwise set bk + j, x3 + x, I& + eT for 0 5 r 5 m; set j + j + 1 and return to F2. (In the latter case we have a new linearly independent solution, modulo 2, whose first odd component is ek.) F5. [Try to factor.] (Now es, ei, . , e, are even.) Set y + ((-l) p~ . . . pz ) mod N. If x = y or if 1: + y = N, return to F2. Otherwise compute gcd(a: -y, N), which is a proper factor of N, and terminate the algorithm. 1 It can be shown that this algorithm finds a factor, whenever it is possible to deduce one from the given outputs of Algorithm E. [Proof: Let the outputs of Algorithm E be (X%, EZO,. , Ei,) for 1 5 i < t, and suppose that we could find a factorization N = N1iV2 when x E Xpl.. .XFt and y E (-l)eo 2p~ 2.. . p$ (modulo N), where e, = al&, + . . . + atEi, is even for all j. Then x = +y (modulo Nr) and 2 = Ty (modulo Nz). It is not difficult to see that this solution can be transformed into a pair (x, y) that appears in step F5, by a series of steps that systematically replace (x, y) by (zz , yy ) where 2 = fy (modulo N).] 13. There are 2d values of x having the same exponents (eo, . . , e,), since we can choose the sign of 3: modulo qf arbitrarily when N = 4; . . . q$ . Exactly two of these 2d values will fail to yield a factor. 14. Since P2 = kNQ2 (modulo p) for any prime divisor p of V, we have 1 E P2(P- )/2 =_ (kNQ2)(p- )/2 s (kN)(p- )/2 (modulo p), if P $ 0.