# 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}}}$