[PDF] Primalité des nombres de Mersenne - La minerve de lENS Rennes PDF Dvt

Si Mq est un nombre premier, alors q est premier Démonstration Si q n'est pas premier, q = mn, avec m, n > 2 Et alors Mq = 2mn − 1 qui est divisible par 2n

Si a > 2 alors an − 1 n'est pas un nombre premier Définition 1 Les entiers de la forme Mn = 2n − 1 sont appelés nombres de Mersenne Du théorème, on peut

[PDF] Primalité des nombres de Mersenne - La minerve de lENS Rennes

Si Mq est un nombre premier, alors q est premier Démonstration Si q n'est pas premier, q = mn, avec m, n > 2 Et alors Mq = 2mn − 1 qui est divisible par 2n

[PDF] NOMBRES de MERSENNE (1588-1648)

Donc l'ensemble des nombres premiers est infini Démonstration du petit théorème de Fermat a) Lemme 1 Soit p un entier naturel quelconque Montrons que

[PDF] Nombres premiers - Thierry Sageaux

Les 25 premiers nombres premiers a retrouver en moins d'une minute 2 ;3 ;5 ;7 ; 11 ;13 ;17 ;19 Démonstration : Existence : Si n est premier, c'est fini Si n n'est pas premier, Nombres de Mersenne – Nombres de Fermat On rappelle que M

[PDF] TESTS DE PRIMALITÉ, NOMBRES DE MERSENNE 1 Introduction

fini quadratique sur Fp (p étant un nombre premier) pour le test de primalité et 3 3 ci-dessous, auxquels la démonstration du théor`eme 3 1 s'applique, avec

[PDF] Les nombres parfaits - Cours - Université Laval

On appelle nombre de Mersenne un nombre de la forme Mn = 2n − 1; si ce nombre est premier, on Pour une démonstration, voir le Théor`eme 1 plus bas 3

[PDF] Fermat, Mersenne, factorisation et nombres parfaits - Département

Soit p un nombre premier ≡ −1 (mod 4) et soit a premier `a p On suppose que a est un carré modulo p Alors, a est d'ordre impair modulo p Démonstration D'

[PDF] Arithmétique

Connaissez-vous une autre démonstration (encore) ? (cf exercice 2) Que pouvez-vous dire sur les diviseurs premiers d'un nombre de Mersenne? (cf exercice

[PDF] a^n-1 premier alors a=2

[PDF] le tourisme des français en 2016

[PDF] français vacances statistiques 2016

[PDF] tourisme français ? l'étranger

[PDF] ou partent les français en vacances

[PDF] pourcentage de français qui partent en vacances ? l'étranger

[PDF] nombre marche tour eiffel 2 etage

[PDF] hauteur tour eiffel 1er etage

[PDF] 1 etage combien de marches

[PDF] combien de marches pour monter au deuxième étage de la tour eiffel

[PDF] fonction logarithme bac pro exercice

[PDF] nombre de molécules dans 1 litre d'air

[PDF] exercices fonctions logarithmes et exponentielles

[PDF] nombre d'atomes sur terre

[PDF] pv=nrt

[PDF] Primalité des nombres de Mersenne - La minerve de lENS Rennes

Primalité des nombres de Mersenne

Référence : Cours de calcul formel. Corps finis, systèmes polynomiaux, applications.

PhilippeSaux Picart, ÉricRannou

2011-2012

On appellenombres de Mersenneles

M q= 2q-1 pourq?N

On a d"abord le lemme :

Lemme 1

SiMqest un nombre premier, alorsqest premier.

Démonstration.Siqn"est pas premier,q=mn, avecm,n >2.

Et alorsMq= 2mn-1 qui est divisible par 2n-1.

On a une caractérisation :

Théorème 2

Pour tout nombre premier impairq:

M qest premier???

2 +⎷

3? 2q-1 ≡ -1 modMq.

On remarque qu"il faut se placer dans un corps où 3 admet une racine carrée. Dans la suite, on explicitera : on

prendraFMqou une de ses extensions.

Démonstration du sens direct.

Lemme 3

Pour tout entierknon nul,M2k+1est congru à 7 modulo 12.

Démonstration.Par récurrence :

(k= 1) : On a bien 22×1+1= 7. 1 (k→k+ 1) : On a modulo 12 : 2

2(k+1)+1-1≡4×22k+1-1

≡?22k+1-1?×4 + 3 ≡7×4 + 3 ≡7

Donc, pour toutqimpair,Mq≡7 mod 12.

Montrons maintenant que 3 n"est pas résidu quadratique moduloMq.

Pour cela, on montre le

Lemme 4

3 est résidu quadratique modulo un entier premierpsi, et seulement sip≡ ±1 mod 12.

Démonstration.Par la loi de réciprocité quadratique, on a : p 3? ?3p? = (-1)p-1 2.

Ainsi, par définition du symbole de Legendre :

3 résidu modulop??p

3? = (-1)p-1 2.

On remarque que le seul carré non nul deF3est 1, et donc 3 est résidu quadratique modulopsi, et seulement

sil"une des conditions est vérifiée : (i)p≡1 mod 3 etp-1

2est pair.

(ii)p≡2 mod 3 etp-1

2est impair.

Dans le premier cas,pest congru à 1 modulo 3 et 4, et donc modulo 12.

Dans le second cas,pest congru à 2 modulo 3, et 3 modulo 4, et donc par théorème chinois, à -1 modulo 12.♦

CommeMqn"est congru ni à 1, ni à -1 modulo 12, 3 n"est pas résidu quadratique moduloMq.X2-3 est donc

irréductible surFMq, et doncA=FMq[X]/(X2-3)est un corps, et on note la classe deXdansA⎷ 3.

On remarque de plus que 2

q+1≡2 modMq, et donc 2 admet une racine carrée⎷

2 := 2q+12.

On définit les quantités

ρ=1 +⎷

3⎷2etρ=1-⎷3⎷2.

On montre facilement queρ2= 2 +⎷

3 etρρ=-1.

De plus, on remarque que comme⎷

3 n"est pas résidu quadratique moduloMq, par petit théorème de Fermat :

Mq= 3M

q-12⎷3 =-⎷3. CommeAest de caractéristiqueMq, on a par morphisme de Frobénius : a+b⎷ 3?

Mq=a-b⎷3.

2 De même, on aρMq=ρCommeAest de caractéristiqueMq, on a par morphisme de Frobénius : a+b⎷ 3?

Mq=a-b⎷3.

De même, on a

2M q=⎷2, et doncρMq=ρ. On multiplie à gauche et à droite, et on obtient :

2 +⎷

3? 2q-1

2 +⎷3?

Mq+1 2=-1. Démonstration du sens réciproque.On note dans la suiteZnl"anneauZ/nZ.

On note encoreAune extension deZMqcontenant une racine de 3 : plus précisemment, siZMqcontient une

racine de 3, on prendA=ZMq, et sinon on prendA=ZMq[X]/(X2-3). On supposeMqnon premier, et on appellepun de ses diviseurs premiers.

pest donc un diviseur de 0 dansA, et a fortiori n"est pas inversible. Il est donc contenu dansun idéal maximal

MdeA. Alors A/Mest un corps, de caractéristiquep(pnon nul dansM).

On appelleα(resp.β) la classe de 2 +⎷

3 (resp. 2-⎷3) dansA/M.

Notre hypothèse s"écrit doncα2q-1≡ -1 modMq, et on en déduit queαest d"ordre 2qdansA/M.

On pose maintenantQ= (X-α)(X-β) =X2-4X+1. C"est un polynôme à coefficient dans le corps premier

A/M,Fp.

Donc, commeαest racine deQ,αpaussi, et doncαp=αouαp=β.

Dans le premier cas, comme l"ordre deαest 2q, 2qdivisep-1. OrpdiviseMq= 2q-1, doncp <2q. D"où une

contradiction.

Dans le second cas,αp=β=α-1=αMq. On a alorsp≡2q-1 mod 2q, et ceci imposep=Mq. Encore une

contradiction. Remarque- On peut citer un corollaire direct de ce théorème :

Théorème 5 : Test de Lehmer-Lucas

On définit la suite(Ln)?ZNMqpar

0= 4etLn+1=L2n-2 modMq.

Alors on a :

M qpremier??Lq-2≡0 modMq.

Cet algorithme permet de calculer directement dansZMqplutôt que dans une extension. Au final, il est de

complexitéO(q3) (on peut accélerer un peu avec la transformée de Fourier discrète). 3quotesdbs_dbs2.pdfusesText_2

[PDF] [PDF] Primalité des nombres de Mersenne - La minerve de lENS Rennes

Primalité des nombres de Mersenne

PhilippeSaux Picart, ÉricRannou

2011-2012

On appellenombres de Mersenneles

On a d"abord le lemme :

Lemme 1

SiMqest un nombre premier, alorsqest premier.

Et alorsMq= 2mn-1 qui est divisible par 2n-1.

On a une caractérisation :

Théorème 2

Pour tout nombre premier impairq:

2 +⎷

Démonstration du sens direct.

Lemme 3

Démonstration.Par récurrence :

2(k+1)+1-1≡4×22k+1-1

Donc, pour toutqimpair,Mq≡7 mod 12.

Pour cela, on montre le

Lemme 4

3 est résidu quadratique modulo un entier premierpsi, et seulement sip≡ ±1 mod 12.

Ainsi, par définition du symbole de Legendre :

3 résidu modulop??p

2est pair.

2est impair.

On remarque de plus que 2

2 := 2q+12.

On définit les quantités

ρ=1 +⎷

3⎷2etρ=1-⎷3⎷2.

On montre facilement queρ2= 2 +⎷

3 etρρ=-1.

De plus, on remarque que comme⎷

3 n"est pas résidu quadratique moduloMq, par petit théorème de Fermat :

Mq= 3M

Mq=a-b⎷3.

Mq=a-b⎷3.

De même, on a

2 +⎷

2 +⎷3?

On appelleα(resp.β) la classe de 2 +⎷

3 (resp. 2-⎷3) dansA/M.

A/M,Fp.

Théorème 5 : Test de Lehmer-Lucas

On définit la suite(Ln)?ZNMqpar

0= 4etLn+1=L2n-2 modMq.

Alors on a :