Cryptography Reference
In-Depth Information
primes of 1024 bits or less. Thus this algorithm is very far from being able to deal
with, say, 1024-bit primes (as we will see, primes of this size are often used in
cryptography). A practical trick to economize memory usage when sieving is to
segment the array of numbers from 2 to
n
. There are many variations on the basic
algorithm which, for example, can be modified to output all the primes in an interval
[
. Moreover, generalizations of the sieve of Eratosthenes are used in many other
algorithms, including the most powerful factoring algorithms that we shall discuss
later: the quadratic sieve and the number field sieve. For more information about this
see [60].
a
,
b
]
2.3.3.2 Trial Division
Trial division is another old primality test that, in contrast with the sieve, has the
advantage that it requires very little memory. The alg
or
ithm p
ro
ceeds by trying to
divide
n
successively by the integers between 2 and
.If
√
n
is reached without
any of them dividing
n
, then
n
is declared prime, othe
r
wise,
n
is composite. In fact, it
√
n
suffices to trial divide by the primes between 2 and
√
n
, for which one has to generate
the list of these primes. As in the case of the sieve of Eratosthenes, this algorithm
also does more than primality testing for it is actually a factoring algorithm that can
output all the prime factors of
n
.
The following implements trial division (as a primality test) in Maple for integers
10
14
:
≤
> primelist := Eratosthenes(10ˆ7):
> TrialDivision := proc(n)
local s, p, r;
ifn<2then
return false
end if;
if 10ˆ14 < n then
error "number too big"
end if;
s := isqrt(n);
r:=1;
for p in primelist while r <> 0 and p <= s do
r := modp(n, p)
end do;
evalb(r <> 0)
end proc:
For example, the primes among the last 50 integers preceding 10
14
are:
> select(TrialDivision, [$10ˆ14-50 .. 10ˆ14]);
[99999999999959, 99999999999971, 99999999999973]
The bit complexity of trial division can be easily estimated as follows using the
PNT (Theorem 6.
2)
. By this theorem, there are approximately
n
1
/
2
ln
n
1
/
2
n
1
/
2
=
O
(
ln
n
)
primes less than
√
n
.If
n
is prime, then one division for each of those primes must be
performed, with cost
O
ln
2
n
n
1
/
2
ln
n
(
)
. This gives a total cost of
O
(
)
bit operations
n
ε
)
and, since ln
n
=
O
(
for
ε>
0, the running time of the algorithm can be estimated
