Abyss web server - 45.4 ANSWERS TO EXERCISES 615 31. Set r
45.4 ANSWERS TO EXERCISES 615 31. Set r = M, qM = 4m, EM = 2m. 32. Let M = [ml, and let the places xi of each message be restricted to the range 0 < x < M3 -M2. If x > M, encode it as x3mod N as before, but if x < M change the encoding to (x + TJM)~ mod N, where y is a random number in the range M2 -M 5 y 2 M2. To decode, first take the cube root; and if the result is M3 -M2 or more, take the remainder mod M. 34. Let P be the probability that xm mod p = 1 and let Q be the probability that xm modq = 1. The probability that gcd(xm-1, N) = p or q is P(l-Q) $ &(1-P) = P f Q -2PQ. If P 5 3 or Q 5 f, this probability is > 3 max(P, Q) > i10e6, so we have a good chance of finding a factor after about 1061ogm arithmetic operations modulo N. On the other hand if P > 3 and Q > i then P zz Q z 1, since we have the general formula P = gcd(m, p -1)/p; thus m is a multiple of lcm(p -1, q -1) in this case. Let m = 2kr where r is odd, and form the sequence x1 mod N, x2 mod N, . . ..x 2k mod N; with high probability we find that the first appearance of 1 is preceded by a value y other than N -1, as in Algorithm P, hence gcd(y -1, N) = p or q. 35. Let f = (pq- -qpml) mod N. Since pmod 4 = q mod 4 = 3, we have ($) = (+) = (i) = -($) = -1, and we also have ($) = -(t) = 1. Given a message x in the range 0 5 x 2 Q(N -5), let Z = 4x + 2 or 8x f 4, whichever satisfies (3) = 1; then transmit the message Z2 mod N. To decode this message, we first use a SQRT box to find the unique number y such that y2 E Z2 mod N and (6) = 1 and y is even. Then y = 5, since the other three square roots of Z2 are N -Z and (ff%) mod N; the first of these is odd, and the other two have negative Jacobi symbols. The decoding is now completed by setting x = [y/4] if ymod4 = 2, otherwise x + [y/8]. Anybody who can decode such encodings can also find the factors of N, because the decoding of a false message Z2mod N when (5) = -1 reveals (ff)modN, a number that has a nontrivial gcd with N. 36. The mth prime equals m In m + m In In m -m + m In In m/n m -2m/ln m + O(m(log log m)2(log m)-2), by (4), although for this problem we need only the weaker estimate pm = m In m + O(m log log m). (We will assume that pm is the mth prime, since this corresponds to the assumption that V is uniformly distributed.) If we choose lnm = icdln N lnln N, where c = O(l), we find that r = c-l dm–c-2-c-2(ln In In N/n In N)- 2C2(ln $c)/ln In N + O(dm). The estimated running time (21) now simp- lifies somewhat surprisingly to the formula exp(f(c, N)dln N lnln N + O(loglog N)), where we have f(c, N) = c + (1 -(1 + In 2)/ln In N)c- The value of c that minimizes f(c, N) is J 1 -(1 + In 2)/ln In N, so we obtain the estimate exp(2Jln N In In N d/1 -(1 + In 2)/ln In N + O(log log N)). When N = 105 this gives e(N) z .33, which is still much larger than the observed behavior. Note: The partial quotients of fi seem to behave according to the distribution obtained for random real numbers in Section 4.5.3. For example, the first million partial quotients of the number 1018 + 314159 include exactly (415236, 169719, 93180, 58606)