jms@central.cis.upenn.edu (Jonathan M. Smith) (03/01/90)
Some thoughts on 17 as a modulus. One possibility is that primes with a large number of primitive roots (see number theory book for rigor) make good moduli. Avoiding technical (i.e., number theoretic) language, a primitive root is a number (for a prime modulus p), a, such that a**(p-1) mod p == 1, and p-1 is the smallest positive integer for which this is true. Now, if a number is not a primitive root, the modulus calculation will yield a result which will be contained in a smaller set, which it will not leave in the subsequent remultiplications by "prime" in the loop you presented. The XOR confuses the analysis; perhaps somebody from the crypto community might offer some insight. In any case, there is a formula for computing the number of primitive roots a prime has, and this number is phi(phi(p)), where phi() is Euler's phi function. But phi(p)=p-1, so that p has phi(p-1) primitive roots. For 17, phi(16)=16*(1-1/2), or 8, which is quite a lot. I don't have a table of ratios of (phi(p-1))/p handy; this might be useful to examine, since it gives the probability (directly) that an input will land on a primitive root. I stand ready to be corrected.... Interesting aside: There are some interesting implications of this theory. For example, have you ever wondered why the period of a repeating decimal such as 1/7=.142857... is 6 decimal digits (probably not) and others such as 1/3=.3... are shorter. For 1/p, the maximum length of the repeating portion is p-1, and in the decimal system occurs iff 10 is a primitive root of p. As a matter of fact, 7 and 17 are the two smallest examples, which is why I thought of this stuff... -Jonathan