Web And Email Hosting, Jsp Web Hosting Blog

30 RANDOM NUMBERS 3.2.2 The fourth instruction here is the exclusive or operation found on nearly all binary computers (cf. exercise 2.5-28 and Section 7.1); it changes each bit position in which location A has a 1 bit. The value in location A is the binary - constant (al . . . uk)~, where xk -alx k–l . . . - ak is a primitive polynomial modulo 2 as above. After the code (10) has been executed, the next bit of the generated sequence may be taken as the least significant bit of word X (or, alternatively, we could consistently use the most significant bit of X, if it were more convenient to do so). For example, consider Fig. 1, which illustrates the sequence generated for Ic = 4 and CONTENTS(A) = (0011)~. This is, of course, an unusually small value for k. The right-hand column shows the sequence of bits of the sequence, namely 1101011110001001.. . , repeating in a period of length 2k - 1 = 15. This sequence is quite random, considering that it was generated with only four bits of memory; to see this, consider the adjacent sets of four bits occurring in the period, namely 1101, 1010, 0101, 1011, 0111, 1111, 1110, 1100, 1000, 0001, 0010, 0100, 1001, 0011, 0110. In general, every possible adjacent set of Ic bits occurs exactly once in the period, except the set of all zeros, since the period length is 2k - 1; thus, adjacent sets of Ic bits are essentially independent. We shall see in Section 3.5 that this is a very strong criterion for randomness when Ic is, say, 30 or more. Theoretical results illustrating the randomness of this sequence are given in an article by R. C. Tausworthe, Math. Comp. 19 (1965), 201-209. Primitive polynomials modulo 2 of degree 5 100 have been tabulated by E. J. Watson, Math. Comp. 16 (1962), 368-369. When k = 35, we may take CONTENTS(A) = (OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOlOl)~, but the considerations of exercises 18 and 3.3.4-26 imply that it would be better to find random constants that define primitive polynomials modulo 2. Caution: Several people have been trapped into believing that this random bit-generation technique can be used to generate random whole-word fractions (.X0X1 . . . xk-112, (.xkxk+l . . .X2k-1)2, . . . ; but it is actually a poor source of random fractions, even though the bits are individually quite random. Exercise 18 explains why. Mitchell and Moore s additive generator (7) is essentially based on the con- cept of primitive polynomials; the polynomial x55 + x24 + 1 is primitive, and Table 1 is essentially a listing of all the primitive trinomials modulo 2. A generator almost identical to that of Mitchell and Moore was independently dis- covered in 1971 by T. G. Lewis and W. H. Payne [cf. JACM 20 (1973), 456-4681, but using exclusive or instead of addition so that the period is exactly 255 - 1; each bit position in their generated numbers runs through the same periodic sequence, but has its own starting point. (See Bright and Enison, Computing Surveys 11 (1979), 357-370, for further discussion of Lewis and Payne s method.) We have now seen that sequences with 0 2 X, < m and period mk -1 can be found, when X, is a suitable function of X,-l, . . . ,X+.-k and when m is prime. The highest conceivable period for any sequence defined by a relation

3.2.2 OTHER METHODS 29 Of course, the mere fact that suitable constants al, . . . , uk exist giving a period of length pk -1 is not enough for practical purposes; we must be able to find them, and we can t simply try all p possibilities, since p is on the order of the computer s word size. Fortunately there are exactly p(pk -1)/k suitable choices of (al, . . . , ak), so there is a fairly good chance of hitting one after making a few random tries. But we also need a way to tell quickly whether or not (9) is a primitive polynomial modulo p; it is certainly unthinkable to generate up to p -1 elements of the sequence and wait for a repetition! Methods of testing for primitivity modulo p are discussed by Alanen and Knuth in Sankhya (A) 26 (1964), 305-328; the following criteria can be used: Let r = (pk - l)/(p -1). i) (-I) - ak must be a primitive root modulo p. (Cf. Section 3.2.1.2.) ii) The polynomial x7 must be congruent to (-l)k-lak, modulo f(x) and p. iii) The degree of 2 7/q mod f(z), using polynomial arithmetic modulo p, must be positive, for each prime divisor q of T. Efficient ways to compute the polynomial CP mod f(z), using polynomial arithmetic modulo a given prime p, are discussed in Section 4.6.2. In order to carry out this test, we need to know the prime factorization of T = (p -l)/(p -l), and this is the limiting factor in the calculation; T can be factored in a reasonable amount of time when k = 2, 3, and perhaps 4, but higher values of k are difficult to handle when p is large. Even k = 2 essentially doubles the number of significant random digits over what is achievable with k = 1, so larger values of k will rarely be necessary. An adaptation of the spectral test (Section 3.3.4) can be used to rate the sequence of numbers generated by (8); see exercise 3.3.4-26. The considerations of that section show that we should not make the obvious choice of al = j-1 or -1 when it is possible to do so; it is better to pick large, essentially random, values of al,…, ak that satisfy the conditions, and to verify the choice by applying the spectral test. A significant amount of computation is involved in finding al, . . . , ak, but all known evidence indicates that the result will be a very satisfactory source of random numbers. We essentially achieve the randomness of a linear congruential generator with k-tuple precision, using only single precision operations. The special case p = 2 is of independent interest. Sometimes a random number generator is desired that merely produces a random sequence of bits- zeros and ones-instead of fractions between zero and one. There is a simple way to generate a highly random bit sequence on a binary computer, manipulating k-bit words: Start with an arbitrary nonzero binary word X. To get the next random bit of the sequence, do the following operations, shown in MIX s language (see exercise 16): LDA X (Assume that overflow is now off. ) ADD X Shift left one bit. JNOV *+2 XOR A Jump if high bit was originally Otherwise adjust number with zero. exclusive or. (10) STA X I

28 RANDOM NUMBERS 3.2.2 Table 1 SUBSCRIPT PAIRS MELDING LONG PERIODS MOD (1, 2) (1, 15) (5, 23) (7, 31) (5, 47) (21, 52) (18, 65) (28, 73) (2, 93) (1, 3) (4, 15) (9, 23) (13, 31) (14, 47) (24, 55) (32, 65) (31, 73) (21, 94) (1, 4) (7, 15) (3, 25) (13, 33) (20, 47) (7, 57) (9, 68) (9, 79) (11, 95) (2, 5) (3, 17) (7, 25) (2, 35) (21, 47) (22, 57) (33, 68) (19, 79) (17, 95) (1, 6) (5, 17) (3, 28) (11, 36) (9, 49) (19, 58) (6, 71) (4, 81) (6, 97) (1, 7) (6, 17) (9, 28) (4, 39) (12, 49) (1, 60) (9, 71) (16, 81) (12, 97) (3, 7) (7, 18) (13, 28) (8, 39) (15, 49) (11, 60) (18, 71) (35, 81) (33, 97) (4, 9) (3, 20) (2, 29) (14, 39) (22, 49) (1, 63) (20, 71) (13, 84) (34, 97) (3, 10) (2, 21) (3, 31) (3, 41) (3, 52) (5, 63) (35, 71) (13, 87) (11, 98) (2, 11) (1, 22) (6, 31) (20, 41) (19, 52) (31, 63) (25, 73) (38, 89) (27, 98) For each pair (1, k), the pair (k–l, k) is also valid (see exercise 24), hence only values of 1 5 k/2 are listed here. For extensions of this table, see N. Zierler and J. Brillhart, Information and Control 13 (1968), 541-554; 14 (1969), 566-569; 15 (1969), 67-69. is that the period is very long, and this is not enough. John Reiser (Ph. D. thesis, Stanford Univ., 1977) has shown, however, that an additive sequence like (7) will be well distributed in high dimensions, provided that a certain plausible conjecture is true (cf. exercise 26). The fact that the special numbers (24, 55) in (7) work so well follows from theoretical results developed in some of the exercises below. Table 1 lists all pairs (I, k) for which the sequence X, = (X,-l +X+-k) mod 2 has period length 2k -1, when Ic < 100. The pairs (1, Ic) for small as well as larger k are shown, for the sake of completeness; the pair (1, 2) corresponds to the Fibonacci sequence mod 2, whose period has length 3. However, only pairs (1, k) for relatively large k should be used to generate random numbers in practice. Instead of considering only additive sequences, we can construct useful ran- dom number generators by taking general linear combinations of Xn-i, . . . , Xn-k for small k. In this case the best results occur when the modulus m is a large prime; for example, m can be chosen to be the largest prime number that fits in a single computer word (see Table 4.5.4-l). When m I= p is prime, the theory of finite fields tells us that it is possible to find multipliers al, . . . , ok such that the sequence defined by x, = (al&-1 + * * * + &&+k) modp (8) has period length pk - 1; here Xc, . . . ,Xk-r may be chosen arbitrarily but not all zero. (The special case k = 1 corresponds to a multiplicative congruential sequence with prime modulus, with which we are already familiar.) The constants al,…, ak in (8) have the desired property if and only if the polynomial f(x) = xk -al+-1 -. . . - ak (9) is a primitive polynomial modulo p, that is, if and only if this polynomial has a root that is a primitive element of the field with p elements (see exercise 4.6.2-16).

3.2.2 OTHER METHODS 27 where m is even, and where X0, . . . ,X54 are arbitrary integers not all even. The constants 24 and 55 in this definition were not chosen at random, they are special values that happen to have the property that the least significant bits (X, mod 2) will have a period of length 255 -1. Therefore the sequence (Xn) must have a period at least this long. Exercise 11, which explains how to calculate the period length of such sequences, proves that (7) has a period of length 2f(255 -1) for some f, 0 2 f < e, when m = 2=. At first glance Eq. (7) may not seem to be extremely well suited to machine implementation, but in fact there is a very efficient way to generate the sequence using a cyclic list: Algorithm A (Additive number generator). Memory cells Y[l], Y[2], . . . , Y[55] are initially set to the values X54, X53, . . . , X0, respectively; j is initially equal to 24 and k is 55. Successive performances of this algorithm will produce the numbers X55, X56, . . . as output. Al. [Add.] (If we are about to output X, at this point, Y[j] now equals X+-24 andY[k] equalsXn-55.) Set Y[k] t (Y[k]+Y[j])mod2 , andoutputY[k]. A2. [Advance.] Decrease j and k by 1. If now j = 0, set j +- 55; otherwise if k = 0, set k c 55. 1 This algorithm in MIX is simply the following: Program A (Additive number generator). Assuming that index registers 5 and 6 are not touched by the remainder of the program in which this routine is embedded, the following code performs Algorithm A and leaves the result in register A. r15 = j, r16 = k. LDA Y,6 Al. Add. ADD Y, 5 Yk + Y, (overflow possible) STA Y,6 + Yk. DEC5 1 A2. Advance. j t j -1. DEC6 1 ktk-1. J5P *+ 2 ENT5 55 If j = 0, set j t 55. J6P *+ 2 ENT6 55 If k = 0, set k + 55. 1 This generator is usually faster than the previous methods we have been discussing, since it does not require any multiplication. Besides its speed, it has the longest period we have seen yet; and it has consistently produced reliable results, in extensive tests since its invention in 1958. Furthermore, as Richard Brent has observed, it can be made to work correctly with floating point numbers, avoiding the need to convert between integers and fractions (cf. exercise 23). Therefore it may well prove to be the very best source of random numbers for practical purposes. The only reason it is difficult to recommend sequence (7) wholeheartedly is that there is still very little theory to prove that it does or does not have desirable randomness properties; essentially all we know for sure

26 RANDOM NUMBERS 3.2.2 An interesting quadratic method has been proposed by R. R. Coveyou when m is a power of two; let X0 mod 4 = 2, X,+1 = X,(X, + 1) mod 2e, n 2 0. (4) This sequence can be computed with about the same efficiency as (l), without any worries of overflow. It has an interesting connection with von Neumann s original middle-square method: If we let Y, be Z X,, so that Y, is a double-precision number obtained by placing e zeros to the right of the binary representation of -L then Y,+l consists of precisely the middle 2e digits of Yg + 2eY,! In other words, Coveyou s method is almost identical to a somewhat degenerate double- precision middle-square method, yet it is guaranteed to have a long period; further evidence of its randomness is proved in exercise 3.3.4-25. Other generalizations of Eq. (1) also suggest themselves; for example, we might try to extend the period length of the sequence. The period of a linear congruential sequence is extremely long; when m is approximately the word size of the computer, we usually get periods on the order of 10 or more, so that typical calculations will use only a very small portion of the sequence. On the other hand, when we discuss the idea of accuracy in Section 3.3.4 we will see that the period length influences the degree of randomness achievable in a sequence. Therefore it is occasionally desirable to seek a longer period, and several methods are available for this purpose. One technique is to make X,+i depend on both X, and Xn-1, instead of just on X,; then the period length can be as high as m2, since the sequence will not begin to repeat until we have wn+x 7-&+x+1) = (-%I, x7x+1>. The simplest sequence in which X,+i depends on more than one of the preceding values is the Fibonacci sequence, X n+~ = (& + G-1) mod m. (5) This generator was considered in the early 1950s and it usually gives a period length greater than m; but tests have shown that the numbers produced by the Fibonacci recurrence (5) are definitely not satisfactorily random, and so at the present time the main interest in (5) as a source of random numbers is that it makes a nice bad example. We may also consider generators of the form X n+~ = (-G + L–k) mod m, (6) when k is a comparatively large value. These were introduced by Green, Smith, and Klem [JACK 6 (1959), 527-5371, who reported that, when Ic 5 15, the sequence fails to pass the gap test described in Section 3.3.2, although when k = 16 the test was satisfactory. A much better type of additive generator was devised in 1958 by G. J. Mitchell and D. P. Moore [unpublished], who suggested the somewhat unusual sequence defined by -G = (K-24 + X-55) mod m, n > 55,

3.2.2 OTHER METHODS 25 7. [A4,20] When a satisfies the conditions of Theorem 3.2.1.2A, it is relatively prime to m; hence there is a number a such that aa = 1 (modulo m). Show that a can be expressed simply in terms of b. b 8. [A4261 A random number generator defined by X,+1 = (217 $3)X, mod 235 and X0 = 1 was subjected to the following test: Let, Y, = [1OX,/235]; then Y, should be a random digit between 0 and 9, and the triples (Ysn, Ys~+~, Ysn+2) should take on each of the 1000 possible values from (0, 0, 0) to (9, 9, 9) with equal probability. But with 30000 values of n tested, some triples hardly ever occurred, and others occurred much more often than they should have. Can you account for this failure? 3.2.2. Other Methods Of course, linear congruential sequences are not the only sources of random num- bers that have been proposed for computer use. In this section we shall review the most significant alternatives; some of these methods are quite important, while others are interesting chiefly because they are not as good as a person might expect. One of the common fallacies encountered in connection with random number generation is the idea that we can take a good generator and modify it a little, in order to get an even-more-random sequence. This is often false. For example, we know that X n+l = (ax, + c) mod m (1) leads to reasonably good random numbers; wouldn t the sequence produced by X n+l = ((ax,) mod (m + 1) + c) mod m (2) be even more random? The answer is, the new sequence is probably a great deal less random. For the whole theory breaks down, and in the absence of any theory about the behavior of the sequence (a), we come into the area of generators of the type Xn+l = f(Xn) with the function f chosen at random; exercises 3.1-11 through 3.1-15 show that these sequences probably behave much more poorly than the sequences obtained from the more disciplined function (1). Let us consider another approach, in an attempt to get more random numbers. The linear congruential method can be generalized to, say, a quadratic congruential method: X n+l = (dXt + ax, + c) mod m. (3) Exercise 8 generalizes Theorem 3.2.1.2A to obtain necessary and sufficient con- ditions on a, c, and d such that the sequence defined by (3) has a period of the maximum length m; the restrictions are not much more severe than in the linear method.

24 RANDOM NUMBERS 3.2.1.3 in this case, so the differences between consecutively generated numbers change in a simple way from one value of n to the next. The point (X,,X,+i,X,+z) always lies on one of the four planes x-2y+z=d+m, x-2y+z=d-m, x-2y+z=d, x-2y+z=d-2m, in three-dimensional space, where d = cb mod m. If the potency is 3, the sequence begins to look somewhat more random, but there is a high degree of dependency between X,, Xn+i, and Xn+s; tests show that sequences with potency 3 are still not sufficiently good. Reasonable results have been reported when the potency is 4 or more, but these have been disputed by other people. A potency of at least 5 would seem to be required for sufficiently random values. Suppose, for example, that m = 235 and a = 2k + 1. Then b = 2k, so we find that when Ic 2 18, the value b2 = 22k is a multiple of m: the potency is 2. If Ic = 17,16,. . . , 12, the potency is 3, and a potency of 4 is achieved for Ic = 11, 10,9. The only acceptable multipliers, from the standpoint of potency, therefore have Ic 5 8. This means a 5 257, and we shall see later that small multipliers are also to be avoided. We have now eliminated all multipliers of the form 2k + 1 when m = 235. When m is equal to w f 1, where w is the word size, m is generally not divisible by high powers of primes, and a high potency is impossible (see exercise 6). So in this case, the maximum-period method should not be used; the pure-multiplication method with c = 0 should be applied instead. It must be emphasized that high potency is necessary but not sufficient for randomness; we use the concept of potency only to reject impotent generators, not to accept the potent ones. Linear congruential sequences should pass the spectral test discussed in Section 3.3.4 before they are considered to be accept- ably random. EXERCISES 1. [MO] Show that, no matter what the byte size B of MIX happens to be, the code (3) yields a random number generator of maximum period. 2. [IO] What is the potency of the generator represented by the MIX code (3)? 3. [II] When m = 235, what is the potency of the linear congruential sequence with a = 3141592621? What is the potency if the multiplier is a = 223 + 214 + 22 + l? 4. [15] Show that if m = 2e 2 8, maximum potency is achieved when a mod 8 = 5. 5. [M20] Given that m = pt . . . pf and a = 1 + kpp . . , pp, where a satisfies the conditions of Theorem 3.2.1.2A and k is relatively prime to m, show that the potency is max(Tel/fil,. . . , retlftl). b 6. [20] Which of the values of m = w f 1 in Table 3.2.1.1-1 can be used in a linear congruential sequence of maximum period whose potency is 4 or more? (Use the result of exercise 5.)

3.2.1.3 POTENCY and this equation suggests that we can avoid the multiplication; merely shifting and adding will suffice. For example, suppose that a = B2 + 1, where B is the byte size of MIX. The code LDA X SLA 2 ADD X (3) INCA I can be used in place of the instructions given in Section 3.2.1.1, and the execution time decreases from 1611 to 721. For this reason, multipliers having form (1) have been widely discussed in the literature, and indeed they have been recommended by many authors. However, the early years of experimentation with this method showed that multipliers having the simple form in (1) should be avoided. The generated numbers just aren t random enough. Later in this chapter we shall be discussing some rather sophisticated theory that accounts for the badness of all the linear congruential random number generators known to be bad. However, some generators (such as (2)) are suffi- ciently awful that a comparatively simple theory can be used to dispense with them. This simple theory is related to the concept of potency, which we shall now discuss. The potency of a linear congruential sequence with maximum period is defined to be the least integer s such that bS = 0 (modulo m). (4 (Such an integer s will always exist when the multiplier satisfies the conditions of Theorem 3.2.1.2A, since b is a multiple of every prime dividing m.) We may analyze the randomness of the sequence by taking X0 = 0, since 0 occurs somewhere in the period. With this assumption, we have x, = ((a -l)c/b) mod m, and if we expand an -1 = (b + l)n -1 by the binomial theorem, we find that All terms in bS, bs+l, etc., may be ignored, since they are multiples of m. Equation (5) can be instructive, so we shall consider some special cases. If a = 1, the potency is 1; and X, = cn (modulo m), as we have already observed, so the sequence is surely not random. If the potency is 2, we have X, G cn + cb(;), and again the sequence is not very random; indeed, X n+l-Xn=c+cbn

22 RANDOM NUMBERS 3.2.1.2 14. [Ml81 If e > 1 and p is an odd prime, and if a is a primitive element modulo p, prove that either a or a + p is a primitive element modulo pe. [Hint: See exercise 12.1 15. [A4991 (a) Let al, a2 be relatively prime to m, and let their orders modulo m be X1, X2, respectively. If X is the least common multiple of Xi and X2, prove that a;E1atZ has order X modulo m, for suitable integers ICY, ~2. [Hint: Consider first the case that X1 is relatively prime to X2.1 (b) Let x(m) be the maximum order of any element modulo m. Prove that x(m) is a multiple of the order of each element modulo m; that is, prove that a Vrn) =_ 1 (modulo m) whenever a is relatively prime to m. b 16. [M2?4] Let p be a prime number. (a) Let f(x) = xn + clxn-- +. . . + cn, where the c s are integers. Given that a is an integer for which f(a) = 0 (modulo p), show that there exists a polynomial q(x) = xn- + qixn- + … $- qn-i with integer coefficients such that f(z) = (x - a)q(s) (modulo p) for all integers Z. (b) Let f(x) be a polynomial as in (a). Show that f(x) h as at most n distinct roots modulo p; that is, there are at most n integers a, with 0 5 a < p, such that f(a) = 0 (modulo p). (c) Because of exercise 15(b), the polynomial f(x) = ~ (~1 -1 has p -1 distinct roots; hence there is an integer a with order p - 1. 17. [A!.%] Not all of the values listed in Theorem D would be found by the text s construction; for example, 11 is not primitive modulo 5e. How can this be possible, when 11 is primitive modulo lo , according to Theorem D? Which of the values listed in Theorem D are primitive elements modulo both 2 and 5 ? 18. [A4851 Prove Theorem D. (Cf. the previous exercise.) 19. [40] Make a table of some suitable multipliers, a, for each of the values of m listed in Table 3.2.1.1-1, assuming that c = 0. b 20. [M24] (G. Marsaglia.) The purpose of this exercise is to study the period length of an arbitrary linear congruential sequence. Let Y,, = 1 + a + . . . + an- , so that X, = (AY, + Xc)modm for some constant A by Eq. 3.2.1-8. (a) Prove that the period length of (Xn) is the period length of (Yn mod m ), where m = m/gcd(A, m). (b) Prove that the period length of (Y, modp ) satisfies the following when p is prime: (i)Ifumodp=O,itisl. (ii)Ifumodp=1,itispe,exceptwhenp=2ande>2and a mod 4 = 3. (iii) If p = 2, e 2 2, and a mod 4 = 3, it is twice the order of a modulo pe (cf. exercise ll), unless a F -1 (modulo 2e) when it is 2. (iv) If umodp > 1, it is the order of a modulo pe. 21. [M.Z5] In a linear congruential sequence of maximum period, let Xc = 0 and let s be the least positive integer such that us = 1 (modulo m). Prove that gcd(X,, m) = s. 3.2.1.3. Potency. In the preceding section, we showed that the maximum period can be obtained when b = a -1 is a multiple of each prime dividing m; and b must also be a multiple of 4 if m is a multiple of 4. If z is the radix of the machine being used-so that z = 2 for a binary computer, and z = 10 for a decimal computer-and if m is the word size ze, the multiplier. a=zk+l, 2

3.2.1.2 CHOICE OF MULTIPLIER 21 4. [M20] When a and c satisfy the conditions of Theorem A, and when m = 2e, Xe = 0, what is the value of X2,-1? 5. [14] Find all multipliers a that satisfy the conditions of Theorem A when m = 235 + 1. (The prime factors of m may be found in Table 3.2.1.1-1.) b 6. [Z O] Find all multipliers a that satisfy the conditions of Theorem A when m = lo6 -1. (See Table 3.2.1.1-l.) l 7. [M23] The period of a congruential sequence need not start with X0, but we can always find indices p 2 0 and X > 0 such that Xn+x = X, whenever n 2 p, and for which ,U and X are the smallest possible values with this property. (Cf. exercises 3.1-6 and 3.2.1-1.) If p~j and Xj are the indices corresponding to the sequences (X0 modpJ3, a mod pT3, c modpJT3, p;j), and if ,LL and X correspond to the sequence (X0, a, c, p; . . . pet), Lemma Q states that X is the least common multiple of X1, . . . , Xt. What is the value of p in terms of the values of ~1, . . . , pt? What is the maximum possible value of /J obtainable by varying X0, a, and c, when m = p; . . . pz is fixed? 8. [M20] Show that if amod = 3, we have (a - -l)/(a -1) 3 0 (modulo 2 ) when e > 1. (Use Lemma P.) b 9. [MZ2] (W. E. Thomson.) When c = 0 and m = 2 > 16, Theorems B and C say that the period has length 2e-2 if and only if the multiplier a satisfies amod = 3 or amod 8 = 5. Show that every such sequence is essentially a linear congruential sequence with m = 2e–2, having full period, in the following sense: a) If Xn+l = (4c $1)X% mod 2e, and X, = 4Y, + 1, then Y n+l = ((4~ + l)Y, $ ~)mod2 -~. b) If Xn+r = (4c - l)Xn mod2 , and X, = ((-l)n(4Y, + l))mod2 , then Yn+~ = ((1 -4c)Y, -c) mod Ze- . [Note: In these formulas, c is an odd integer. The literature contains several statements to the effect that sequences with c = 0 satisfying Theorem B are somehow more random than sequences satisfying Theorem A, in spite of the fact that the period is only one-fourth as long in the case of Theorem B. This exercise refutes such statements; in essence, one gives up two bits of the word length in order to save the addition of c, when m is a power of 2.1 10. (MB] For what values of m is k(m) = cp(m)? b 11. [ML%] Let x be an odd integer greater than 1. (a) Show that there exists a unique integer f > 1 such that x 3 af f 1 (modulo 21t1). (b) Given that 1 < x < 2e - 1 and that f is the corresponding integer from part (a), show that the order of x modulo 2 is 2e-f. (c) In particular, this proves Theorem C(i). 12. [M26] Let p be an odd prime. If e > 1, prove that a is a primitive element modulo pe if and only if a is a primitive element modulo p and ape1 $ 1 (modulo p ). (For the purposes of this exercise, assume that X(p ) = p - (p-1). This fact is proved in exercises 14 and 16 below.) 13. [M22] Let p be prime. Given that a is not a primitive element modulo p, show that either a is a multiple of p or CJ@- )/~ G 1 ( modulo p) for some prime number o that divides p - 1.