Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!bionet!agate!darkstar!central.cis.upenn.edu
From: jms@central.cis.upenn.edu (Jonathan M. Smith)
Newsgroups: comp.os.research
Subject: Some thoughts on 17
Message-ID: <1522@darkstar.ucsc.edu>
Date: 28 Feb 90 16:28:11 GMT
Sender: usenet@darkstar.ucsc.edu
Organization: University of Pennsylvania
Lines: 27
Approved: comp-os-research@jupiter.ucsc.edu


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