cours.primalite-factorisation

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 ...