Theorem of Carmichael
The set of Carmichael (after Robert Daniel Carmichael , 1910 ) is a number theoretical statement about a specific class of easily programmable random number generators and provides criteria to help choose generators of the best possible quality.
Statement of the sentence
Let a natural number be given (the so-called module). The multiplicative congruence generator can be defined for every whole number as a factor and every whole number in the range from 0 to (inclusive) as the start value (or seed) . The combination of and leads at least to a maximum period length among the multiplicative congruence generators with the same module if
- is too coprime , d. H. , and
- "Primitive element" is modulo .
(Let us denote a number as a primitive element modulo if the smallest positive exponent for which is valid is maximal. If the prime residue class group is also cyclic , then there are primitive roots modulo , and a "primitive element" is a primitive root .) The Function is called the Carmichael function . Formulas for their calculation and other properties can be found in the article there.
Examples
- Accordingly, 1, 3, 7 and 9 are suitable starting values for the module , while 3 and 7 are suitable factors . In fact , the sequence with the period length four yields - more is not possible in the case .
- To are about and appropriate values. The sequence produced has a period length of 16 and already gives a "slight impression of an apparently random irregularity".
Remarks
- The criteria mentioned in the sentence are sufficient; the second is also necessary, but not the first. For example, delivers the choice , , the result of the period length of four, although not prime is.
- In computer applications, the power of two is usually not too small; then is primitive if and only if or holds. And it applies to all powers with an even exponent .
literature
- Robert Daniel Carmichael . In: Bulletin of the American Mathematical Society . No. 16, 1910, pp. 232-238.
- Donald E. Knuth : The Art of Computer Programming , Vol. 2. Addison-Wesley, Reading, Mass. (USA) 1969, ISBN 0-201-03822-6 .