Transcript N - bYTEBoss

Primality and generation of
prime numbers
Motivations
• Most of the public key encryption
algorithms require large prime numbers.
• Example: in the RSA scheme, the modulo is
the product of two prime numbers.
• In El-Gamal, LUC, ECC, etc … large prime
numbers are also required.
Prime and composite numbers
• A number is said to be prime if it is
divisible only by 1 and by itself (1 is not a
prime number). Otherwise it is said to be
composite.
• Example: 7 is prime, 9 is composite.
• Euclid’s theorem: There is infinitely many
prime numbers.
Density
• LaVallée-Poussin theorem: the number of prime
numbers smaller than N is almost equal to N/ln(N).
• A number smaller than N randomly chosen has
approximately 1 chance out of ln(N) to be prime.
• Example: a number with 100 decimal digits has 1
chance out of 230 to be prime.
• There are « relatively » many prime numbers.
Primality: prehistory
• Erathostene’s sieve: to determine whether N is
prime, try to divide it by all the integer numbers
between 2 and N.
• Unpracticable if N is large.
• China (200 BC): If 2N-1  1 (mod. N) then N is
prime.
• Other works: ideonal numbers (Euler).
• Before Lehmer, there were no efficient criterion.
Primality: history
• Lehmer (186?): two efficient criteria which require the factorization of
either N-1 or N+1.
• Pocklington (1914): improved Lehmer’s criterion (an incomplete
factorization of N-1 is sufficient).
• Brillhart (1973): lighter factorization and combination of N-1 and
N+1criteria.
• Other works (1976-1978): Judd, Williams, Bach, … Criteria using
factorizations de N2+1, N2+N+1, N2-N+1, …
• Lenstra-Cohen (1983): First generalist test (no factorization required).
• Schoof (1985): Generalist test using elliptic curves.
• Atkin-Morain (1988): Elliptic curves. Lighter than Schoof’s algorithm.
• Agarwal-Saxena-Kayal (2001): Primality has a polynomial complexity.
Complexity
• Factorization of numbers with more than
100 decimal digits are not practically
feasible.
• Elliptic curve algorithms are unpracticable
for digits with more than 300 decimal
digits. Moreover, they are difficult to
implement.
• There are inexact (or only incomplete)
methods which give good results.
Fermat’s theorem
• Let a and N be two integers with 2aN-1. If N is
prime then aN-11 (mod N).
• N=7, a=2, 26=641 (mod 7). So 7 is maybe
prime.
• N=9, a=5, 587 (mod 9). So 9 is not prime.
• N=341, a=2, 23401 (mod 341). But 341=1131 is
composite. 341 is said to be pseudo-prime for the
basis 2.
• The converse of Fermat’s theorem is false.
• The chinese criterion is not true.
Fermat’s test
• 334056 (mod 341) and thus 341 is not
prime.
• We can consider to combine several
Fermat’s tests.
• But 561 takes any Fermat’s test in default:
25601 (mod 561), 35601 (mod 561), 55601
(mod 561), etc …
• Fermat’s test, alone, is insufficient.
Carmichael’s numbers
• A composite number which suceed for any Fermat’s test is
said to be a Carmichael’s number.
• 561 is the smallest Carmichael’s number.
• Let n be an integer such that 6n+1, 12n+1 et 18n+1 are
prime, then N=(6n+1)(12n+1)(18n+1) is said to be a
Chernick’s number.
• A Chernick’s number is a Carmichael’s number (1729 is
the least one).
• Heuristically, there are infinitely many Chernick’s
numbers.
• Granville’s theorem (1993): There are infinitely many
Carmichael’s numbers.
The equation X21 (mod N)
• Let X be an integer suxh that X21 (mod N).
• Then X2-1=(X+1)(X-1)0 (mod N).
• If X1 and XN-1, then we have the product
of 2 numbers smaller than N whose result is
a multiple of N, then N is not prime.
• Example 521 (mod 24), thus 640 (mod
24).
Miller-Rabin’s test
•
•
•
•
•
•
•
Let N be an odd integer greater or equal to 3.
Let a be an integer such that 2aN-1.
Suppose that aN-11 (mod N).
N-1 is even. Let X=a(N-1)/21 (mod N).
Then X21 (mod N).
Thus if X1 et XN-1 then N is not prime.
If X1 (mod N) and (N-1)/2 is even, we continue with
Y=a(N-1)/41 (mod N).
• If X=N-1 then the test is finished.
• N is said to pass Miller-Rabin’s test for the basis a when all
the possible verifications have been made without to obtain
any contradiction.
Iterative version
• N,a integers, N odd, N3, 2aN-1.
N,a
ii+1
Determine h and d
such that d odd
and N-1=2h.d
i=h ?
no
N succeeds
N fails
XX2 (mod N)
Compute
Xad(mod N)
i0
X=1 or N-1 ?
yes
yes
no
no
X=1 ?
no
X=N-1 ?
yes
N succeeds
yes
N fails
Example 1
•
•
•
•
•
N=53, a=2
N-1=52=2213
X0=213 (mod 53)30
X1=302 (mod 53)52=N-1
We have obtained no contradiction thus 53
passes the test for basis 2.
Example 2
•
•
•
•
•
•
•
N=561, a=2
N-1=2435
X0=235 (mod 53)263
X1=2632 (mod 53)166
X2=1662 (mod 53)67
X3=672 (mod 53)1
We have obtained a contradiction thus 561 does
not pass the test.
• 561 is not prime.
Example 3
•
•
•
•
•
•
N=2047, a=2
N-1=21023
X0=21023 (mod 53)1
2047 passes Miller-Rabin’s test for basis 2.
But 2047=2389 is not prime.
2047 is said to be a strong pseudo-prime for
basis 2.
Miller-Rabin’s test
• Miller’s theorem: Let N be a composite number,
then it can pass successfully at most N/4 MillerRabin’s test.
• In fact this is a very pessimistic bound.
• Let N be a number to be tested, we choose
randomly n basis for the tests.
• If N passes all the tests, then there is less than 1
chance out of 4n that N is in fact composite.
Balance
• The algorithmic cost of a Miller-Rabin’s test is
inferior to the one of Fermat’s test.
• It enables to efficiently distinguish composite
numbers from prime numbers.
• But this test cannot establish that a number is
prime above any doubt.
• Note nevertheless that no strong pseudo-prime for
at least 30 different basis is known.
Prime number generation
• There exist methods which generate
numbers which are effectively prime.
• In counterpart, the generated numbers are
not absolutely random.
• Any prime number cannot be generated. In
fact, the generated numbers N have a shape
such that if N is effectively prime, the
« proof » is easy to obtain.
Lehmer’s theorem
• Let N be an odd integer greater than 3.
• Suppose that there exists an integer a2
such that aN-11 (mod N).
• Suppose moreover that for any prime
divisor p of N-1, there exists an integer ap
such that ap(N-1)/p1 (mod N).
• Then N is prime.
Gordon’s method (1985)
• Choose N randomly and try to factorize N-1.
• If N-1 can be entirely factorized, apply Lehmer’s
theorem to N.
• If the factorization is not successful, choose
another integer N and iterate.
• Problem: The entire factorization of N-1 does not
have any chance to terminate if N has several
hundreds of decimal digits.
Example (Knuth)
• N0=37866809061660057264219253397.
• 3N0-11 (mod N0), thus N0 is suspected to be prime.
• We factorize N0-1 and we obtain N0-1=22 . 19 . 107 . 353 . 91813 . N1
with N1=143675413657196977.
• 3N1-11 (mod N1), thus N1 is suspected to be prime.
• N1-1=24 . 32 . 547 . 1103 . N2 with N2=1653701519.
• 3N2-11 (mod N2), thus N2 is suspected to be prime.
• N2-1=2 . 7 . 19 . 23 . 137 . 1973.
• The factorization of N2-1 is exact: all the prime divisors are known
with certainty.
• We can try to apply Lehmer’s criterion.
Example (Knuth)
• We have 2(N2-1)/21 (mod N2), thus a2=2 is not
satistactory.
• We try successively 2, 3, 5, 7 …
• We have 7(N2-1)/21653701518 (mod N2) thus a2=7
satisfy Lehmer’s condition.
• We also find a7=a19=a23=a137=a1973=2.
• N2 is then established to be prime.
• The factorization of N1-1 is then exact and we try
to apply Lehmer’s criterion to N1.
Example (Knuth)
• We continue and we show that N1, then N0
are prime.
• This is a descending proof.
• N0 is prime if N1<N0 is prime, N1 is prime if
N2<N1 is prime and N2 is small enough to
be easily shown to be prime.
• Other certificates like Atkin-Morain’s one
use also a descending principle.
Pocklington’s theorem
•
•
•
•
•
Let N be an odd integer greater than 3.
Hypotheses: N=R.F+1 with F even.
The factorization of F is entirely known.
GCD(R,F)=1.
There exists an integer a such that aN-11 (mod N)
for any prime divisor p of F, GCD(a(N-1)/p-1,N)=1.
• Then: Any prime divisor of N is of the form k.F+1
with k1.
• In particular, if N<(F+1)2, then N is prime.
• In fact, if N<(F+1).(2F+1) then N is prime.
Maurer’s method (1987)
• We wish to generate a prime number with 20 decimal
digits.
• We choose F even whose factorization is known. For
instance, F=23257376907=5010183422.
• We choose randomly an odd integer R such that R2F, for
instance R=7419669081.
• We compute N=R.F+1=37173903026352175183.
• We choose a randomly and compute aN-1 (mod N).
• Example 2N-1  31953700866015605260 (mod N).
• The result is not equal to 1 so N is not prime.
• We choose a new value for R and we iterate.
Maurer’s method (1987)
•
•
•
•
R=7785640265.
N=39007485785358686831.
We have 7N-11 (mod N) thus N is maybe prime.
We have 7(N-1)/2 39007485785358686830 (mod
N).
• GCD(39007485785358686829,N)=1 thus N
satisfies the first condition.
• Likewise, GCD(7(N-1)/32573-1,N)=1 and GCD(7(N1)/76907-1,N)=1.
• Thus N is prime.
Remarks
• In the preceding example, if we take a=2, we
effectively have 2N-11 (mod N) and thus N is
suspected to be prime.
• But 2(N-1)/21 (mod N) and thus GCD(2(N-1)/21,N)=N.
• The value a=2 does not permit to establish the
primality of N.
• Two strategies are possible: either we insist and
choose a new value for a (because we expect that
N is effectively prime), or we give away and
generate a new candidate.
Remarks
• Most of the problems appear when the divisor 2 of F is
tested: half of the times, a « does not work ».
• We can avoid this problem by computing the Jacobi
symbol of a for N: if J(a,N)=-1, a will not cause a
problem.
• This computation is quick with respect of the
exponentiations.
• Another remark: in order to choose the prime divisors of F,
we can recursively use the same method.
• Then we can choose values for F with large prime factors.
Refinement of Brillhart et al.
• Let N verifying the conditions of
Pocklington’s theorem except that N<2F3
only.
• We pose R=2Fs+r with 0r2F.
• Then if s=0 or if r2-8s is not a perfect
square, then N is prime.
• Determining exactly whether a number is a
perfect square is algorithmically costly.
Perfect square
• When generating prime numbers, only sufficient
conditions are considered.
• If N2 (mod 3), N is not a perfect square.
• If N2 ou 3 (mod 5) or N3, 5 ou 6 (mod 7) idem.
• If N verifies at least one of these congruences,
then N is not a perfect square.
• Generally, if Na (mod M) with J(a,M)=-1 where
J is Jacobi’s symbol (resp. Legendre) if M is
composite (resp. prime), then N is not a perfect
square.
Other methods
• There also exist primality tests based on Lucas series.
• Those criteria permit to establish if a number not too large
is prime, to generate large prime numbers or to test with a
great fiability (Strong pseudo-primalité for Lucas’s
criterion)
• The primality criteria of logiciels like Mupad, Maple or
Mathematica are in fact most of the time composed of a
series of Miller-Rabin’s tests followed by a strong pseudoprimality test for Lucas’s criterion.
• It is also possible to combine with other tests: Perrin’s
series, Fibonacci, Judd, Williams, elliptic curve tests.