Theorem of Carmichael

from Wikipedia, the free encyclopedia

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

  1. is too coprime , d. H. , and
  2. "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.


  • 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".


  • 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 .