Théorie algorithmique des nombres - Cours no. 10

Th´eorie algorithmique des nombresCours no. 10Jean-S´ebastien CoronUniversit´e du LuxembourgNovember 22, 2009Jean-S´ebastien Coron Th´eorie algorithmique des nombresSummaryAlgorithmic number theory.Probabilistic primality testingApplication to prime-number generation.Jean-S´ebastien Coron Th´eorie algorithmique des nombresTrial divisionGoalGiven an integer n, determine whether n is prime or composite.Simplest algorithm: trial division. √Test if n is divisible by 2, 3, 4, 5,... We can stop at n.Algorithm determines if n is prime or composite, and outputsthe factors of n if n is composite.Very inefficient algorithm√Requires around n arithmetic operations.128 30If n has 256 bits, then 2 arithmetic operations. If 222operations/s, this takes 10 years !Jean-S´ebastien Coron Th´eorie algorithmique des nombresProbabilistic primality testingGoal: describe an efficient probabilistic primality test.Can test primality for a 512-bit integer n in less than a second.Probabilistic primality testing.The algorithm does not find the factors of n.The algorithm may make a mistake (pretend that an integer nis prime whereas it is composite).−100But the mistake can be made arbitrarily small (e.g. < 2 ,so this makes no difference in practice.Jean-S´ebastien Coron Th´eorie algorithmique des nombresDistribution of prime numbersLet π(x) be the number of primes in the interval [2,x].Theorem (Prime number theorem)We have π(x)≃ x/logx.Fact (approximation of the n-th ...