12 Pages
English
Learn all about the services we offer

# Théorie algorithmique des nombres - Cours no. 10

-

Learn all about the services we offer
12 Pages
English

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 ineﬃcient 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 eﬃcient probabilistic primality test.Can test primality for a 512-bit integer n in less than a second.Probabilistic primality testing.The algorithm does not ﬁnd 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 diﬀerence 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 ...

Subjects

##### Formal sciences

Informations

Exrait

Th´eoriealgorithmiquedesnombres Cours no. 10
JeanSe´bastienCoron
Universit´eduLuxembourg
November 22, 2009
JeanS´ebastienCoron
The´oriealgorithmiquedesnombres
Summary
Algorithmic number theory. Probabilistic primality testing Application to primenumber generation.
JeanSe´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 ineﬃcient algorithm Requires aroundnarithmetic operations. 128 30 Ifnarithmetic operations. If 2has 256 bits, then 2 22 operations/s, this takes 10 years !
JeanS´ebastienCoron
Th´eoriealgorithmiquedesnombres
Probabilistic primality testing
Goal: describe an eﬃcient probabilistic primality test. Can test primality for a 512bit integernin less than a second. Probabilistic primality testing. The algorithm does not ﬁnd 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 diﬀerence in practice.
JeanSe´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) Letpndenote thenth prime number. Thenpnnlogn. More explicitely,
nlogn<pn<n(logn+ log logn) forn6
JeanS´ebastienCoron
The´oriealgorithmiquedesnombres
The Fermat test
Fermat’s little theorem Ifnis prime andais an integer between 1 andn1, then n1 a1 modn. Therefore, if the primality ofnis unknown, ﬁnding n1 a[1,n1] such thata6= 1 modnproves thatnis composite. Fermat primality test with security parametert. Fori= 1 totdo Choose a randoma[2,n2] n1 Computer=amodn Ifr6= 1 then return “composite” Return “prime’
JeanS´ebastienCoron
Th´eoriealgorithmiquedesnombres
Analysis of Fermat’s test
n1 LetLn={a[1,n1] :a1 modn} Theorem: ∗ ∗ Ifnis prime, thenL=Z. Ifnis composite andL n n n( Zn, then|Ln| ≤(n1)/2. Proof: Ifnis prime, Ln=Znfrom Fermat. s a subgroup ofZ Ifnis composite, sinceLninand the order of a subgroup divides the order of the group,|Z|=m∙ |Ln| n for some integerm.
1 1n1 ∗ ∗ =|| ≤ Z| |Ln|Zn|nm2 2
JeanSe´bastienCoron
The´oriealgorithmiquedesnombres
Analysis of Fermat’s test
Ifnis comZ posite andLn(n n1 thena= 1 modnwith probability at most 1/2 for a randoma[2,n2]. t The algorithm outputs “prime” wih probability at most 2 . Unfortunately, there are odd composite numbersnsuch that Ln=Z. n Such numbers are called Carmichael numbers. The smallest Carmichael number is 561. Carmichael numbers are rare, but there are an inﬁnite number of them, so we cannot ignore them.
JeanSe´bastienCoron
Th´eoriealgorithmiquedesnombres
The MillerRabin test
The MillerRabin test is based on the following fact: s Letnbe a prime>2, letn1 = 2rwhereris odd. Leta r be any integer such that gcd(a,nThen either) = 1. a1 j 2r modnora≡ −1 modnfor somej, 0js1. Proof: n1 Sincenis prime,a1 modn. j+1 r2 Consider the minimum 0js1 such thata1 j r2 modn. Letβ:=amodn 2 Thenβ1 modnmust have. We β=±1 because a polynomial of degree 2 has at most two roots overZnforn prime.
JeanSe´bastienCoron
The´oriealgorithmiquedesnombres
The MillerRabin test
s Writen1 = 2rfor oddr. Fori= 1 totdo r Generate a randoma[2,n2]. Letβa Ifβ6= 1 andβ6=1 do j1. Whilejs1 andβ6=1 do 2 Letββmodn Ifβ= +1 return “composite” jj+ 1 Ifβ6=1 return “composite” Return “prime”
JeanS´ebastienCoron
modn.
The´oriealgorithmiquedesnombres
The MillerRabin test
Property Ifnis prime, then the MillerRabin test always declaresnas prime. Ifn3 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)
JeanSe´bastienCoron
The´oriealgorithmiquedesnombres