Cryptography Reference
In-Depth Information
7
Algorithmic Number Theory
Content
Primality: Fermat test, Miller-Rabin test
Primality: Carmichael numbers, Solovay-Strassen test
Factorization: rho method, p
1 method, elliptic curve method
Discrete logarithm: baby steps - giant steps, Pohlig-Hellman
This chapter is a continuation of the previous one. Here we see that prime numbers
can be efficiently generated, while factorization is intractable to date. We also study the
discrete logarithm problem. These are basic tools in public-key cryptography.
7.1
Primality
This section deals with the prime number generation problem. We first try to distinguish
prime numbers from composite ones by primality tests .
We first recall the intuitive method depicted in Fig. 7.1. This algorithm tries to
divide the input n by every integer. At each iteration, we perform all possible divisions
by integers up to i
1 and obtain x , thus the remaining factors are between i and x .
This method has been optimized: since we know that there is no factor of x b etween
2 and i
= x
1, we know that the remaining factors lie between i and b
. Thus
we can stop as soon as i
b . The worst case oc c urs when n is prime or a product
of two primes of same size, for which we need n iterations, which is enormous for
typical numbers in cryptography. We notice however that this algorithm does more than
expected since it prints the factorization of the input instead of just checking whether
or not it is prime. Primality tests are nevertheless easier than factorization as will be
shown in Section 7.2.
>
7.1.1 Fermat Test
A first important primality test is the Fermat test . We first notice that all prime numbers
p are such that for any b with 0
p ,wehave b p 1
1 (mod p ). This property
is known as the Little Fermat Theorem . We can thus check the primality behavior of a
number n by picking a random b such that 0
<
b
<
n , and checking whether b n 1
1 (mod n ). For all prime numbers, this verification will always succeed. But how about
composite numbers?
<
b
<
Search WWH ::




Custom Search