cours.primalite-factorisation

Description

Primality - FactorizationChristophe RitzenthalerNovember 9, 20091 Prime and factorizationDe nition 1.1. An integer p > 1 is called a prime number (nombre premier) if ithas only 1 and p as divisors.Example 1. There are in nitely many prime numbers. The biggest generic one is3 3 3 3 3 3 3 3 3 3(((((((((2 + 3) + 30) + 6) + 80) + 12) + 450) + 894) + 3636) + 70756) + 97220Interested readers may read http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Caldwell/caldwell78.html for the origin of this number. It has 20,562 decimal digitsand the proof was built using fastECPP on several networks of workstations.We will write P the set of prime numbers. To estimate the e ciency of some algo-rithms, we need results on density of primes.Theorem 1.1. Let (x) = #fpx primeg. One hasx(x) :logxLet n 2 be an integer and c an integer prime to n. Let (x) = #fpx prime; p =n;ckn +cg: One has1 x (x) :n;c(n) logxTo nd a prime number, the number of attempts is then of the size of x. Indeed,kthe probability to fail in k attempts is (1 1= log(x)) so the probability to succeedk k=log(x)1 (1 1= log(x)) 1 e1+which is closed to 1 for any k = log(x) .Remark 1. For x 17, one has (x) > x= logx and for x > 1 one has (x) <1:25506(x= logx).Let us nish with the fundamental result.1Theorem 1.2. Every integer a> 1 can be written as the product of prime numbersYe(p)a = pp2Pwith e(p) 0 and e(p) = 0 except for nitely many primes p. Up to permutation, thefactors in ...

Informations

• Publié par: Affe
• Nombre de lectures: 65
• Langue: English

Extrait

1

Primality - Factorization

Christophe Ritzenthaler

November9,2009

Prime and factorization

Definition 1.1.An integerp >1is called aprime number(nombre premier) if it has only1andpas divisors.

Example 1.There are infinitely many prime numbers. The biggest generic one is

3 3 3 3 3 3 3 3 3 3 (((((((((2 + 3) + 30) + 6) + 80) + 12) + 450) + 894) + 3636) + 70756) + 97220

Interested readers may readhttp: // www. cs. uwaterloo. ca/ journals/ JIS/ VOL8/ Caldwell/ caldwell78. htmlfor the origin of this number. It has 20,562 decimal digits and the proof was built using fastECPP on several networks of workstations.

We will writePthe set of prime numbers. To estimate the efficiency of some algo- rithms, we need results on density of primes.

Theorem 1.1.Letπ(x) = #{p≤xprime}. One has x π(x)∼. logx

Letn≥2be an integer andcan integer prime ton. Letπ n,c (x) = #{p≤xprime, p= kn+c}.One has 1x π n,c (x)∼. φ(n) logx To find a prime number, the number of attempts is then of the size ofx. Indeed, k the probability to fail inkattempts is (1−1/log(xthe probability to succeed)) so

k−k/log(x) 1−(1−1/log(x))∼1−e

1+ which is closed to 1 for anyk= log(x) .

Remark 1.Forx≥17, one hasπ(x)> x/logxand forx >1one hasπ(x)< 1.25506(x/logx).

Let us finish with the fundamental result.

1

Theorem 1.2.Every integera >1can be written as the product of prime numbers Y e(p) a=p p∈P

withe(p)≥0ande(p) = 0except for finitely many primesp. Up to permutation, the factors in this product are uniquely determined.

2

Prime numbers

To produce big prime numbers is very important for cryptographic applications. For a givenn, there is no generic algorithm which can compute a random prime number less thanndanddelayHadamarraselubtH.woverestowt#hassuohsnillaVPee´{p≤ n nprime} ∼(see 1). So the usual method is to pick random numbers and to test if logn they are prime or not. This requests that we have fast algorithms to test primality.

2.1Primalitytest 2.1.1 Trial division

The simplest algorithm is based on the following result. Proposition 2.1.nis a composite number if and only if it has a prime divisorpsuch √ thatp≤n. √ Proof.Sincenis composite,n=aband eitheraorbis smaller thann. √ This proposition suggests that one can try all prime numbers less or equal tonusing Eratosthenes sieve. Following the estimate density of prime (see 1), it means that we √ √ 1 (−) logn make up ton/logndivisions, leading to an exponential algorithm inO(e). 2

2.1.2 Fermat test and Carmichael numbers n−1 By Fermat little theorem, one knows that ifnis a prime number thena≡1 (modn) for alla∈Zcoprime withnthe theorem was an equivalence, we would have an easy. If polynomial algorithm to test if a number is a prime. Unfortunately 340 Example 2.Considern= 341 = 11∙31has. One 2≡341)1 (mod .Such a number is calledpseudo-prime(pseudo-premier) in base2. We can prove that there are infinitely many pseudo-primes in base2by showing that if n nis such a number then2−1becausealso. Indeed nis a pseudo-prime in base2one n−1n−1 hasn|2−1, i.e. there iscsuch thatnc= 2−1. Now

n n−1 2−1−1 2(2−1) 2nc 2−1 = 2−1 = 2−1.

n The last expression is divisible by2−1so n 2−1−1n 2≡21 (mod −1).

2

n n To finish the proof, one has to show that2−1is not a prime. Sincen=ab,2−1is a divisible by2−1.

340 An idea is then to change the value ofa: for instance 3≡56 (mod 341). Un- fortunately, there are numbers that are pseudo-prime in any base. Such numbers are calledCarmichael numbers(for instance 561 = 3∙11∙has been shown by Alford,17). It Granville and Pomerance in 1994 that there are infinitely many Carmichael numbers so Fermat test cannot be completely sure. Let us show some properties of these numbers.

Proposition 2.2.An (odd) composite numbern≥3is a Carmichael number if and only if it is square free and for each prime divisorpofn,p−1dividesn−1.

n−1 Proof.indeed (First it is easy to see that a Carmichael number is odd : −1)≡1 (modn) if and only ifnis odd. Letabe a Carmichael number, for anyaprime tonone has

n−1 a≡1

(modn).

Letpbe a prime divisor ofn. There existsaprimitive element modulopthat is prime r ton. Indeed, letaa primitive element modulopandn=p∙mwithmcoprime to r pexists an element (still denoted. There a) inZ/pZlifting the initiala(because the r morphismZ/pZ→Z/pZWe findest surjectif). s∈Z/mZcoprime tomand since r Z/nZ'Z/pZ×Z/mZwe construct the elementa∈Z/nZimage of (a, s). Such an n−1 element satisfies the properties foraone has of course. Now, a≡1 (modp) but as ais primitivep−1 dividesn−1. 2 Now suppose thatn=p mand writea= 1 +pmhas. One

p2 a≡1 +p m+. . .≡1

(modn)

So the order ofaisp. Butpdoes not dividen−1 (p|n) so we get a contradiction. Conversely, letnbe a square-free integer such thatp−1 dividesn−1 for all prime divisorspofn. Letabe prime tonone has

p−1 a≡1

and becausen−1 is a multiple ofp−1,

n−1 a≡1

(modp)

(modp).

Using the Chinese Remainder theorem for all the factorsp, one gets

n−1 a≡1

(modn).

Corollary 2.1.Any Carmichael number is the product of at least3distinct odd primes.

3

Proof.Because a Carmichael number is without square factor and is not prime it has at least two prime factors. Let us assume thatn=pqwithp < q. Thenq−1 divides pq−1 =p(q−1) +p−1 soq−1 dividesp−1. Absurd.

Example 3.Show that if6m+ 1,12m+ 1and18m+ 1are primes thenn= (6m+ 1)(12m+1)(18m+1)is a Carmichael number. First by the Chinese Remainder theorem, one can see that ifn=abwitha, bcoprime then for anyxprime tonone has lcm(φ(a),φ(b)) x≡1 (modn).

Now lcm(φ(6m+ 1), φ(12m+ 1), φ(18m+ 1)) = 36mand also36m|n−1can check. One that1729is such a number.

2.1.3 Lucas test n−1 Letn >We will show that if there exists an1 be an integer. asuch thata≡1 q (modn) anda6≡1 (modn) for allq|n−1,q6=n−1, thennThis is ais prime. m 2 very good test for Fermat numbersF m numbers of the form, i.e. n= 2 (For+ 1 m= 0. . .32 only the first five are prime.F 33 is so big that it may be many years before we can decide its nature). But obviously this test is not good for a generic prime since we must know the factorization ofn−1. ∗n−1 Let assume that such anaexists and letdbe the order ofain (Z/nZ) . Sincea≡1 (modn),d|(n−1). More exactly as no proper divisor ofn−1 is the order ofa, one has d=n−1. Nown−1 =d|φ(n). This is possible only ifnis prime.

2.1.4 Rabin-Miller test Contrary to the Fermat test, the Miller-Rabin test can prove the compositeness of any composite number (i.e. there is no analog of Carmichael numbers for this test). But Rabin-Miller test is a Monte-Carlo algorithm : it always stops ; if it answers yes, the number is composite and if it answers no then the answer is correct with a probability greater than 3/4. r s Letnbe an odd positive integer ands= max{r∈N,2|n−1}. Letd= (n−1)/2 . Lemma 2.1(Miller).Ifnis a prime and ifais an integer prime tonthen we have r d2d eithera≡1 (modn)or there existsr∈ {0, . . . , s−1}such thata≡ −1 (modn). d Proof.The order ofais a divisor ofn−can be1. It dand thena≡1 (modn). If r r−1 r2d2d it is not then its order is 2dforr∈ {1, . . . , s}. Soa≡1 (modn) andais a r−1 2d non-trivial square root of 1 soa≡ −1 (modn).

If we find anawhich is prime tonand that satisfies neither of the conditions, then nis composite. Such an integerais called awitness(inmo´et) for the compositeness of n. Example 4.Letn= 561.a= 2is a witness forn. Indeed heres= 4, d= 35 35 2∙35 4∙35 8∙35 and2≡561)263 (mod ,2≡166 (mod 561),2≡561)67 (mod ,2≡1 (mod 561).

4

For the efficiency of the Rabin-Miller test, it is important that there are sufficiently many witnesses for the compositeness of a composite number. Theorem 2.1(Rabin).Ifn≥3is an odd composite number, then the set{1, . . . , n−1} contains at most(n−1)/4numbers that are prime tonand not witnesses for the compositeness ofn. Proof.Letkbe the maximum value ofrfor which there is an integeraprime ton Q k e(p) that satisfies the second identity. We setm= 2d. Letn=pbe the prime p factorization ofn. Let

J K L M

= = = =

n−1 {a: gcd(a, n) = 1, a≡1 (modn)} m e(p) {a: gcd(a, n) = 1, a≡ ±1 (modp) for allp|n} m {a: gcd(a, n) = 1, a≡ ±1 (modn)} m {a: gcd(a, n) = 1, a≡1 (modn)}.

∗ We haveM⊂L⊂K⊂J⊂(Z/nZ) . For eachawhich is not a witness for the compositeness ofn, the residue classabelongs toLwill prove that the index of. We L ∗ in (Z/nZ) is at least four. The index ofMinKIndeed one can writeis a power of 2.

M x

→K 7→x

→M 2 7→x .

2 Let denoteIthe image of the morphisms:x→xfrom the multiplicative groupK.s j j has kernel a group of order 2 for somejso #I= #K/Now since #2 . Idivides #M j j we can write #M= #I∙aand [K:M] = 2/tLet’s say 2 . Ifand is a power of 2. j≥2 then we are finished. Ifj= 1 (i.e. [L:K] = 2) thennIt follows from Cor. 2.1 thathas two prime divisors. n ∗ is not a Carmichael number. This implies thatJis a proper subgroup of (Z/nZ) and ∗ ∗ the index ofJin (Z/nZat least 2. ) is Therefore the index ofLin (Z/nZ) is at least 4. e∗ Finally, letj= 0. Thennis a prime power, sayn=pwithe >1. Butφ: (Z/nZ)→ e−1n−1 Z/(p−1)Z×Z/pZis an isomorphism. Asn−1 is prime top a≡1 (modn) if ∗e−1e−1 and only ifφ(a) = (µ,[(0). So Z/nZ) :J] = #Z/pZ=pis bigger than 4. This except forn= 9 which can be checked by hand.

To apply the Rabin-Miller test, we choose a random numbera∈ {2, . . . , n−1}. If s−1 d2d2d gcd(a, n)>1 thennOtherwise we computeis composite. . . . , aa , a , we find. If a witness for the compositeness ofn, then we have proved thatnis composite. By Th. 2.1, the probability thatnis composite and thatais not a witness is less than 1/4. So t if we repeat the testttimes we can make this probability less than (1/4) . Fort= 10 −6 this probability is less than 10 . Remark 2.Under the Generalized Riemann hypothesis (which is conjectural but believed true), it can be proved that there is always a witness for the compositeness ofnwith

5

2 a≤ O((logn) ). If we want a absolute test, Adleman, Pomerance, Rumely, Cohen and Lenstra have given an algorithm (APRCL) which is slower but still feasible on numbers of1000digits (it Clog log|n| 2 runs inO(|n|)). 2 In 2002, M. Agrawal, N. Kayal and N. Saxena have found a deterministic polynomial algorithm to solve the problem of primality.

3

Factorization

Now given annthat is known to be composite, how can we find its decomposition in prime factors ? We are going to present algorithms to obtain a non-trivial factor. By repeating inductively the algorithm, we can then factorize the number.

3.1

Trial division

To find small prime factors ofn, a precomputed table of all prime numbers below a fixed boundBA typicalis computed. This can be done using the sieve of Eratosthenes. 6 bound isB.= 10

21 Example 5.We want to factorn= 3 + 1. Trial division with primes less than50 2 2 yields the factors2,7,43we divide. If nby those factors, we obtainm= 1241143. m−1 Since2≡793958 (modm), this number is still composite.

3.2

Pollardp−1odhtem

This algorithm is efficient whennhas a prime factorpsuch thatp−1 has only small prime divisors. Indeed, by Fermat’s little theorem, one has

k a≡1

(modp)

for all multiplekofp−1. Ifp−1 has only small prime divisors, one can try Y e k=q e q∈P,q≤B

k k whereBis a given bound. Now ifa−1 is not divisible byn, then gcd(a−1, n) is a non-trivial factor ofn.

Example 6.Letn= 1241143of the previous example. We setB= 13. Thenk= k 8∙9∙5∙7∙11∙13andgcd(2−1, n) = 547. Son= 547∙2269which are both prime numbers.

6

3.3 Quadratic sieve 3.3.1 Idea The quadratic sieve finds integerx, ysuch that 2 2 x≡y(modn) and x6≡ ±y(modn). 2 2 Thennis a divisor ofx−y= (x−y)(x+y) but of neitherx−yorx+y. Hence g= gcd(x−y, n) is a proper divisor ofn. 2 2 Example 7.Letn= 7429, x= 227, y= 210. Thenx−y=n,x−y= 17so17|n.

3.3.2 Determination ofxandy The idea from the previous section is also used in other factoring algorithms, such as the number field sieve (NFS), but those algorithms have different ways of findingx, y. We describe howx, yare found in the quadratic sieve. √ Letm=bncand 2 f(X) = (X+m)−n. We first explain the procedure on an example. Example 8.Letn= 7429. Thenm= 86. One has 2 2 3 f(−3) = 83−7429 =−540 =−1∙2∙3∙5, 2 2 f(1) = 87−7429 = 140 = 2∙5∙7, 2 2 f(2) = 88−7429 = 315 = 3∙5∙7. This implies 2 2 3 83≡ −1∙2∙3∙5 (mod 7429), 2 2 87≡2∙5∙7 (mod 7429), 2 2 88≡3∙5∙7429)7 (mod . If the last two congruences are multiplied then we obtain 2 2 (87∙88)≡(2∙3∙5∙7) (modn). Therefore we can setx≡87∙88 (modn)≡227andy≡2∙3∙5∙7 (modn)≡210. In the example we have presented numbersfor which the valuef(s) has only small prime factors. Then we use the congruence 2 (s+m)≡f(s) (modn). From those congruences, we select a subset whose products yields squares on the left- and the right-hand sides. The left-hand side of each congruence is a square anyway. Also we know the prime factorization of each right-hand side. The product of a number of right-hand sides is a square if the exponents−In1 and all prime factors are even. the next section, we explain how an appropriate subset of congruences is chosen.

7