Cryptography Reference
In-Depth Information
ten million. Though you'd need ten million storage locations (3 Mbits might
be sufficient), that shouldn't represent a hurdle today.
With 512-bit numbers, however, you'd overtax all resources. The search can
be simplified if we break away from our idea of 100 % security and make do
with 99
.
9999
...
% instead.
With huge numbers like these, it is generally most effective to randomly select
a number in the desired order of magnitude and test whether or not it is a
prime number. If it isn't, we choose the next number — whether randomly or
deterministically doesn't matter.
Testing for prime numbers is also done with the help of chance. We will always
get just statements in the form: 'There is a 50 % probability that the number in
this test is a prime number.' After 50 independent tests, the error probability
will drop to 2
−
50
, which roughly corresponds to one error in one quadrillion
trials. I will use the test by Rabin - Miller as an example [Rabin]; its hit ratio
is not 50 %, but 99.9 % and better. With long numbers, the error probability is
supposedly smaller than 2
−
50
after only six tests.
In practice, prime numbers are created as follows:
1. We create a random number with a length of
N
bits,
p
(
N
is the given
key length). We set the first and the
N
th bits to 1 to make the number
uneven and greater than 2
N
−
1
.
2. We check to see whether
p
is divisible by a small prime number, e.g.,
by a prime number smaller than 256 or 2000. If so, then
p
is out, and
we have to return to Step 1.
This is faster than discarding, if needed, by the following test.
We represent
p
in the form
p
=
2
b
m
+
1, where
b
should be as large
as possible. It is pretty easy: we set the last bit of
p
to equal 0; the
number of zero bits at the end is equal to
b
, and the previous remainder
produces
m
.
3. We run the following Rabin - Miller test [Knuth2, 4.5.4] six times, for
example:
(a) We randomly select a number,
a<p
.
(b) We compute
z
a
m
−
1, then
p
passed the test for this
a
. Otherwise, we set a counter,
j
=
mod
p
.If
z
is equal to 1 or
p
=
0, and
enter into a loop.
