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 ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle y_{0}}$ ${\displaystyle m\!-\!1}$ ${\displaystyle y_{i+1}\equiv (ay_{i})\ {\bmod {\ }}m}$ ${\displaystyle a}$ ${\displaystyle y_{0}}$ ${\displaystyle \lambda (m)}$ ${\displaystyle m}$

1. ${\displaystyle y_{0}}$is too coprime , d. H. , and ${\displaystyle m}$ ${\displaystyle \mathrm {ggT} (y_{0},m)=1}$
2. ${\displaystyle a}$"Primitive element" is modulo . ${\displaystyle m}$

(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. ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle e}$ ${\displaystyle a^{e}\equiv 1{\pmod {m}}}$ ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}$ ${\displaystyle m}$
${\displaystyle \lambda (m)}$

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 . ${\displaystyle m=10}$ ${\displaystyle y_{0}}$ ${\displaystyle a}$ ${\displaystyle a=3}$ ${\displaystyle y_{0}=9}$ ${\displaystyle 9,7,1,3,9,7,1,3,\ldots }$ ${\displaystyle m=10}$
• 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". ${\displaystyle m=64}$ ${\displaystyle a=5}$ ${\displaystyle y_{0}=11}$ ${\displaystyle 11,55,19,31,27,7,35,47,43,23,51,63,59,39,3,15,11,\ldots }$

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. ${\displaystyle m=10}$ ${\displaystyle a=3}$ ${\displaystyle y_{0}=2}$ ${\displaystyle 2,6,8,4,2,6,8,4,\ldots }$ ${\displaystyle y_{0}}$ ${\displaystyle m}$
• 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 . ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle a\equiv 3{\pmod {8}}}$ ${\displaystyle a\equiv 5{\pmod {8}}}$ ${\displaystyle a^{e}\equiv 1{\pmod {8}}}$

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 .