Cryptography Reference
In-Depth Information
where their quality, as one might expect, depends on the choice of parameters
a , b ,and m . In [Knut] it is shown that linear congruences with carefully chosen
parameters can pass through the hoops of statistical tests with flying colors, but
that on the other hand, a random selection of parameters almost always leads to
a poor generator. The moral is this: Be careful in your choice of parameters!
The choice of m as a power of two has at once the advantage that forming
the residue modulo m can be accomplished with a mathematical AND. An
accompanying disadvantage is that the least-significant binary digits of numbers
thus generated demonstrate less random behavior than the most-significant
digits, and thus one must be careful in working with such numbers. In general,
one must look out for poor random properties of such numbers formed from
sequential values of a linear congruence generator modulo a prime divisor of the
modulus m ,sothatthechoiceof m as a prime number should also be considered,
since in this case individual binary digits are no worse than any others.
The choice of a and m has influence on the periodic behavior of the sequence:
Since only finitely many, namely at most m , distinct sequence values can appear,
the sequence begins to repeat at the latest with the generation of the ( m +1) st
number. That is, the sequence is periodic. (One says also that the sequence enters
a period or a cycle .) The entry point into a cycle need not be the initial value X 0 ,
but can be some later value X µ . The numbers X 0 ,X 1 ,X 2 ,...,X µ 1 are called
the nonrecurring elements. We may thus indicate the periodic behavior of the
sequence as shown in Figure 12-1.
Nonrecurring
Elements
X
µ
Period
X 0
Figure 12-1. Periodic behavior of a pseudorandom sequence
Since the regular repetition of numbers in short cycles represents poor
random behavior according to all reasonable criteria, we must strive to maximize
the length of the cycles or indeed to find generators that possess only cycles
of maximum length. We can establish criteria by which a linear congruence
sequence with parameters a , b ,and m possesses exactly the maximal period
length. Namely, the following conditions should be fulfilled:
(i) gcd( b, m )=1 .
(ii) For all primes p one has p | m ⇒ p | ( a − 1) .
(iii) 4
|
m
4
|
( a
1) .
 
Search WWH ::




Custom Search