Cryptography Reference
In-Depth Information
For a proof and additional details see [Knut], Section 3.2.1.2.
As an example of parameters that fulfill these criteria let us consider the linear
congruence that the ISO-C standard recommends as exemplary for the function
rand()
:
X
i
+1
=(
X
i
·
1103515245 + 12345) mod
m,
(12.2)
where
m
=2
k
,with
k
determined by
2
k
1
being the largest number
representable by the type
unsigned int
. The number
X
i
+1
is not returned as the
value of
rand()
, but rather
X
i
+1
/
2
16
mod
(RAND_MAX
+1)
, so that the function
rand()
generates all values between 0 and
RAND_MAX
. The macro
RAND_MAX
is
defined in
stdio.h
and should have a value of at least 32267 (see [Pla1], p. 337).
Here the recommendation of Knuth to do without the least-significant binary
digits in the case of power-of-two moduli has apparently been taken into account.
We easily determine that the above requirements (i)-(iii) are satisfied and that
therefore a sequence produced by this generator possesses the maximum period
length
2
k
.
Whether this happens to be the case for a particular implementation of the C
library, whose source code is usually unavailable,
1
can be tested under favorable
circumstances with the aid of the following algorithm by R. P. Brent. The Brent
algorithm determines the period length
λ
of a sequence that is computed by the
recursion
X
i
+1
=
F
(
X
i
)
on a set of values
D
using the generating function
F
:
D → D
and an initial value
X
0
∈ D
. One needs at most
2
·
max
{ µ, λ }
calculations of the function
F
(cf.[HKW], 4.2).
−
Algorithm of Brent for determining the period length
λ
of a sequence generated
by
X
0
,
X
i
+1
=
F
(
X
i
)
1.
Set
y ← X
0
,
r ←
1
,and
k ←
0
.
2.
Set
x ← y
,
j ← k
,and
r ← r
+
r
.
3.
Set
k
←
k
+1
and
y
←
F
(
y
)
; repeat this step until
x
=
y
or
k
≥
r
.
4.
If
x
=
y
, go to step 2. Otherwise, output
λ
=
k − j
.
This process is successful only if in step 3 one actually sees the actual
sequence values
F
(
y
)
and not, as in the above ISO recommendation, only their
most-significant parts.
We turn first to the actual subject of this chapter and supply ourselves with
functions for generating random numbers in
CLINT
integer format. As our starting
1
The GNU-C library, of the Free Software Foundation, and the EMX-C library, by Eberhard
Mattes, are excellent exceptions. The
rand()
function of the EMX library uses the parameters
a
= 69069
,
b
=5
, and
m
=2
32
. The multiplier
a
= 69069
suggested by G. Marsaglia
produces, together with the modulus
m
=2
32
, good statistical results and a maximal period
length (see [Knut], pp. 102-104).
