Théorie algorithmique des nombres - Cours no. 10

Jean-Sébastien Coron

Description

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

Informations

• Publié par: Erkyo
• Nombre de lectures: 31
• Langue: English

Extrait

Th´eoriealgorithmiquedesnombres Cours no. 10

JeanSe´bastienCoron

Universit´eduLuxembourg

November 22, 2009

JeanS´ebastienCoron

The´oriealgorithmiquedesnombres

Summary

Algorithmic number theory. Probabilistic primality testing Application to primenumber generation.

JeanSe´bastienCoron

Th´eoriealgorithmiquedesnombres

Trial division

Goal Given an integern, determine whethernis prime or composite. Simplest algorithm: trial division. Test ifnis divisible by 2, 3, 4, 5,... We can stop atn. Algorithm determines ifnis prime or composite, and outputs the factors ofnifnis composite. Very inefficient algorithm Requires aroundnarithmetic operations. 128 30 Ifnarithmetic operations. If 2has 256 bits, then 2 22 operations/s, this takes 10 years !

JeanS´ebastienCoron

Th´eoriealgorithmiquedesnombres

Probabilistic primality testing

Goal: describe an efficient probabilistic primality test. Can test primality for a 512bit integernin less than a second. Probabilistic primality testing. The algorithm does not find the factors ofn. The algorithm may make a mistake (pretend that an integern is prime whereas it is composite). −100 But the mistake can be made arbitrarily small (e.g.<2 , so this makes no difference in practice.

JeanSe´bastienCoron

Th´eoriealgorithmiquedesnombres

Distribution of prime numbers

Letπ(x) be the number of primes in the interval [2,x]. Theorem (Prime number theorem) We haveπ(x)≃x/logx. Fact (approximation of thenth prime number) Letp n denote thenth prime number. Thenp n ≃n∙logn. More explicitely,

nlogn<p n <n(logn+ log logn) forn≥6

JeanS´ebastienCoron

The´oriealgorithmiquedesnombres

The Fermat test

Fermat’s little theorem Ifnis prime andais an integer between 1 andn−1, then n−1 a≡1 modn. Therefore, if the primality ofnis unknown, finding n−1 a∈[1,n−1] such thata6= 1 modnproves thatnis composite. Fermat primality test with security parametert. Fori= 1 totdo Choose a randoma∈[2,n−2] n−1 Computer=amodn Ifr6= 1 then return “composite” Return “prime’

JeanS´ebastienCoron

Th´eoriealgorithmiquedesnombres

Analysis of Fermat’s test

n−1 LetL n ={a∈[1,n−1] :a≡1 modn} Theorem: ∗ ∗ Ifnis prime, thenL=Z. Ifnis composite andL n n n ( Z n , then|L n | ≤(n−1)/2. Proof: ∗ Ifnis prime, L n =Z n from Fermat. ∗ s a subgroup ofZ Ifnis composite, sinceL n i n and the order ∗ of a subgroup divides the order of the group,|Z|=m∙ |L n | n for some integerm.

1 1n−1 ∗ ∗ =|| ≤ Z| |L n |Z n | n ≤ m2 2

JeanSe´bastienCoron

The´oriealgorithmiquedesnombres

Analysis of Fermat’s test

∗ Ifnis comZ posite andL n ( n n−1 thena= 1 modnwith probability at most 1/2 for a randoma∈[2,n−2]. −t The algorithm outputs “prime” wih probability at most 2 . Unfortunately, there are odd composite numbersnsuch that ∗ L n =Z. n Such numbers are called Carmichael numbers. The smallest Carmichael number is 561. Carmichael numbers are rare, but there are an infinite number of them, so we cannot ignore them.

JeanSe´bastienCoron

Th´eoriealgorithmiquedesnombres

The MillerRabin test

The MillerRabin test is based on the following fact: s Letnbe a prime>2, letn−1 = 2∙rwhereris odd. Leta r be any integer such that gcd(a,nThen either) = 1. a≡1 j 2∙r modnora≡ −1 modnfor somej, 0≤j≤s−1. Proof: n−1 Sincenis prime,a≡1 modn. j+1 r∙2 Consider the minimum 0≤j≤s−1 such thata≡1 j r∙2 modn. Letβ:=amodn 2 Thenβ≡1 modnmust have. We β=±1 because a polynomial of degree 2 has at most two roots overZ n forn prime.

JeanSe´bastienCoron

The´oriealgorithmiquedesnombres

The MillerRabin test

s Writen−1 = 2∙rfor oddr. Fori= 1 totdo r Generate a randoma∈[2,n−2]. Letβ←a Ifβ6= 1 andβ6=−1 do j←1. Whilej≤s−1 andβ6=−1 do 2 Letβ←βmodn Ifβ= +1 return “composite” j←j+ 1 Ifβ6=−1 return “composite” Return “prime”

JeanS´ebastienCoron

modn.

The´oriealgorithmiquedesnombres

The MillerRabin test

Property Ifnis prime, then the MillerRabin test always declaresnas prime. Ifn≥3 is composite, then the probability that the   t 1 MillerRabin test outputs “prime” is less than 4 Most widely used test in practice. −80 Withtless than. Much = 40, error probabitility less than 2 the probability of a hardware failure. Can test the primality of a 512bit integer in less than a second. 3 Complexity:O(logn)

JeanSe´bastienCoron

The´oriealgorithmiquedesnombres