Cryptography Reference
In-Depth Information
12
Primality testing and integer factorisation using
algebraic groups
There are numerous topics about primality testing and integer factorisation, of which the
most notable is Crandall and Pomerance [
150
]. There is no need to reproduce all the details
of these topics. Hence, the purpose of this chapter is simply to sketch a few basic ideas
that will be used later. In particular, we describe methods for primality testing and integer
factorisation that exploit the structure of algebraic groups.
Definition 12.0.1
A
primality test
is a randomised algorithm that, on input
N
∈ N
, outputs
a single bit
b
such that if
N
is prime then
b
1. A composite integer that passes a primality
test is called a
pseudoprime
. An algorithm
splits
N
=
∈ N
if it outputs a pair (
a,b
) of integers
=
such that 1
<a,b<N
and
N
ab
.
12.1 Primality testing
The simplest primality test is
trial division
(namely, testing whether
N
is divisible by
any integer up to
√
N
). This algorithm is not useful for factoring numbers chosen for
cryptography, but the first step of most general-purpose factoring algorithms is to run trial
division to remove all 'small' prime factors of
N
before trying more elaborate methods.
Hence, for the remainder of this section we may assume that
N
is odd (and usually that it
is not divisible by any primes less than, say, 10
6
).
12.1.1 Fermat test
)
∗
over the ring
Let
N
∈ N
.If
N
is prime then the algebraic group
G
m
(
Z
/N
Z
)
=
(
Z
/N
Z
Z
/N
Z
has
N
−
1 elements. In other words, if
a
is an integer such that gcd(
a,N
)
=
1 and
a
N
−
1
≡
1(mod
N
)
then
N
is not prime. Such a number
a
is called a
compositeness witness
for
N
. The hope is
that if
N
is not prime then the order of the group
G
m
(
1 and
so a compositeness witness exists. Hence, the Fermat test is to choose random 1
<a<N
and compute
a
N
−
1
(mod
N
).
As is well-known, there are composite numbers
N
that are pseudoprimes for the Fermat
test.
Z
/N
Z
) is not a divisor of
N
−
