Transcript Primehunting_uj - Eötvös Loránd Tudományegyetem

Prime Hunting
Gábor Farkas
Department of Computer Algebra
Faculty of Informatics Eötvös Loránd University
Jena, Germany
26. May 2008.
What does „prime hunting” mean ?
What is the main goal of prime hunting?
To find the largest known prime number
and curious prime combinations
What can we do to reach new world records?
Develop fastest programs than others and we are ready!
almost
2/25
Computational Number
Mathematics
Informatics
Theory
to study the classical and new theoretical results
to invent new algorithms
to implement them taken advantage of qualities of the processors
3/25
Motivations
– the published prime records win laurels for us
– the large primes are marketable
e. g. public key cryptographic systems need large primes, or
the prize of the first known prime 10.000.000 of digits is 100.000 $
– the achieved prime records prove the efficiency of our programs
– the fast routines are utilized in software used in practice life
4/25
The Top 10 Largest Known Primes in May, 2008
5/25
Example
Def. An positive integer p is a Sophie Germain prime if p and 2p + 1
are simultaneously primes.
Def. A Cunningham chain of length k (of the first kind) is sequence
of k primes, each which is twice the proceeding one plus one.
{2, 5, 11, 23, 47}
k=5
k=6
{89, 179, 359, 719, 1439, 2879}
SG
6/25
Let us consider now an RSA public key cryptographic algorithm,
where p and q are odd primes, n = pq, e positive integer relatively
prime to (n) and d is a solution of the following linear congruence:
ex  1  n.
Then (n, e) is the public, d is the secret key .
Naturally we want the probability of a successful cycling attack on the
RSA to be as small as possible.
How do we choose the parameters ?
The best choice:
if n is a product of only two factors of the same magnitude that are
doubly Sophie Germain pairs and e is a primitive root with respect to
p – 1 and q – 1 as moduli.
p and q are the first member of a Cunningham chain of length 3
7/25
Description of the „Hunting”
• Candidates (H = {0, 1, …, N})
• Sieving Methods
– Production of „Small” Primes
– Sieving Tables
– Generalized Sieving
• Probabilistic Primality Test
• Exact Primality Test
8/25
Generalized sieve
f1(x), f2(x), …, fs(x)  Z[x] irreducible polynomials
p „sieving prime”
H
…
0, 1,
1 .
ST
.
. 10 .
h
…
.
. 10 .
h+p
.
…
N = 2R–1
. 10 . . . 10 1 1 1
h + 2p … h + kp
if  i  [0, s] : p | fi(h)  h will be „beaten out”
9/25
Particular case
f1(x) = (h0 + cx)2e – 1
h0 = 5775
f2(x) = (h0 + cx)2e + 1
c = 30030
f3(x) = (h0 + cx)2e+1 + 1
e = 171960
„triple-sieving”
~ 51780 digits
2, 3, 5, 7, 11, 13 will never be a prime factor of fi(x) (i = 1, 2, 3)
17  p < 2T = M
17, 19, 23, …,  2T/2
„small primes”
10/25
Sieving with small primes
ST
1 .
.
. 10 .
h
fi(x)  0 (mod p)
.
. 10 .
h+p
.
. 10 . . . 10 1 1 1
h + 2p … h + kp
solution: h
i = 1, 2, 3
After sieving the elements of H which are represented by 1 have not
any „small” primefactor.
11/25
Multiprocessing
sieve of Eratosthenes with small primes
PST1
PST2
…
PSTn
ST
ST
…
ST
proc1
proc2
…
procn
ST(1)
ST(2)
…
ST(n)
Merge ST(j), j = 1, 2, …, n
12/25
The more the sieving primes increase,
the more the efficiency of the sieve decrease,
e. g. if p > N , then p can beat out at most 1 candidate from H.
Sooner or later the sieve will be slower than probabilistic primality test.
Probabilistic primality test: Miller – Rabin
Exact (deterministic) primality test
x2y – 1: Lucasian type test
x2y + 1: Brillhart, Lehmer, Selfridge
13/25
Theoretical base
F(n)
14/25
The idea behind the conjecture
Prime number theorem
Gauss conjectured (1792) that
x
 x  ~
ln( x)
de la Vallée Poussin and Hadamard (1896) proved
The probability that the numbers f1(n), …, fs(n) are simultaneously
prime would be
1
ln  f1 (n)  ln  f s (n) 
if these events were independent.
15/25
But, the prime combinations (s-tuples) are not random!
chance that none of the integers f1(n), …, fs(n) is divisible by p
chance that none of the integers of an s-tuple is divisible by p
C f1 ,, f s
ln  f1 (n)  ln  f s (n) 
the probability that f1(n), …, fs(n) are simultaneously prime
16/25
Let us denote by Q(a, b) the expected number of integers n[a, b) for
which f1(n), …, fs(n) are simultaneously prime. Then
Q(a, b) ~ C f1 ,, f s 
b
a
du
.
ln  f1 (u )  ln  f s (u ) 
In our case f1(x), …, fs(x) are linear polynomials it is easy to calculate
C f1 ,, f s
C1 = 1
from the constants
1 s / p
Cs  
s


ps 1  1 / p
twin prime constant
C2 = 0.6601618158468695739278121100145…
C3 = 0.63516699356280296543…
17/25
If we use the sieve with primes a  p < b, than the density of the
prime s-tuples is increased by the factor
and the number of the elements of H is decreased by this factor.
In our cases this formula can be reduced:

for p  1.000.033 we do the multiplications
a ,1000033
s
D
18/25


ln( b)

 
 ln( 1000033) 
s
How does the above mentioned calculations estimate the real values?
N = 233 – 1
8.589.934.592 candidates
The upper bound of small primes is: 305.020.993
triple-sieving with the small primes
How many candidates remain?
theoretical calculation: 27344542
reality: 27347222
Error < 0.01%
19/25
233 = 8.589.934.592 candidates
2 GB OM
expected ~ 16.13558453 twin and so many SG primes
triple-sieving: 17  p < 248+ε
~ 5.3 million of candidates
Prospective value: ~ 1.37 twin and SG primes
51779 digits
16869987339975 · 2171960 ±1
twin primes
20/25
„The weapons”
• SGI Altix 3700
• Intel Itanium 2
– 3 MB cache
– 128 db processorregister
– 2 GB operative memory
• ~ 0-100 processors
21/25
Software
• Redhat GNU/Linux (ia64), kernel 2.4
• Compilers (C):
– GNU C Compiler (gcc)
– Intel C Compiler (icc)
• Parallelization softwares:
– PVM library
– MPI library
22/25
„The Hunters”
Járai, Antal
Csajbók, Tímea
Járai, Zoltán
Farkas, Gábor
Kasza, János
23/25
The Top 10 Largest Known Twin Primes in May, 2008
24/25
The Top 10 Largest Known Sophie Germain Primes in May, 2008
25/25