Cryptography Reference
In-Depth Information
multiple of
p
, in contradiction to our assumption. Now we would like to consider
how this sieve might be implemented, and as preparation we shall develop a
programmable algorithm, for which we take the following viewpoint: Since except
for 2 there are no even prime numbers, we shall consider only odd numbers as
candidates for primality. Instead of making a list of odd numbers, we form the
list
f
i
,
1
≤ i ≤
(
N −
1)
/
2
, which represents the primality property of the
numbers
2
i
+1
. Further, we use a variable
p
that will contain the current value
2
i
+1
of our (imagined) list of odd numbers, as well as a variable
s
for which the
relation
2
s
+1=
p
2
=(2
i
+1)
2
,thatis,
s
=2
i
2
+2
i
, always holds. We may
now formulate the following algorithm (cf. [Knut], Section 4.5.4, Exercise 8).
Sieve of Eratosthenes, algorithm for calculating all prime numbers less than or
equal to a natural number
N
√
N/
2
.Set
f
i
←
1
for
1
≤ i ≤ L
.Set
1.
Set
L ←
(
N −
1)
/
2
and
B ←
i ←
1
,
p ←
3
,and
s ←
4
.
2.
If
f
i
=0
, go to step 4. Otherwise, output
p
as a prime and set
k
←
s
.
3.
If
k ≤ L
, set
f
k
←
0
,
k ← k
+
p
, and repeat step 3.
4.
If
i
≤
B
, then set
i
←
i
+1
,
s
←
s
+2
p
,
p
←
p
+2
, and go to step 2.
Otherwise, terminate the algorithm.
The algorithm leads us to the following program, which as result returns a
pointertoalistof
ULONG
values that contains, in ascending order, all primes below
the input value. The first number in the list is the number of prime numbers
found.
Function:
prime number generator (sieve of Eratosthenes)
ULONG * genprimes (ULONG N;)
Syntax:
Input:
N
(upper bound for the prime search)
a pointer to vector of
ULONG
values with primes less than
or equal to
N
. (At position 0 the vector contains the
number of primes found.)
NULL
,ifanerrorwith
malloc()
.
Return:
ULONG *
genprimes (ULONG N)
{
ULONG i, k, p, s, B, L, count;
char *f;
ULONG *primes;
