Primalite et factorisation d'entiers

Description

CHAPITRE XI Primalite et factorisation d'entiers Distinguer nombres premiers et nombres composes, et decomposer ces derniers en facteurs premiers, est un des problemes les plus importants et les plus utiles en arithmetique. C.F. Gauss, Disquisitiones Arithmeticae, 1801 Objectifs Le theoreme fondamental de l'arithmetique garantit que tout entier positif n s'ecrit de maniere unique comme produit n = pe11 p e2 2 · · · p ek k d'un certain nombre k ≥ 0 de facteurs premiers p1 < p2 < · · · < pk de multiplicites e1,e2, . . . ,ek ≥ 1. Etant donne un entier n, trois problemes pratiques se posent : (1) Determiner rapidement si n est premier ou compose. (2) Si n est premier, en trouver une preuve concise et facilement verifiable. (3) Si n est compose, trouver rapidement sa decomposition en facteurs premiers. Pour les petits entiers ces problemes sont faciles a resoudre. Par contre pour les grands entiers, deja a partir de 30 decimales, les methodes naıves echouent de maniere catastrophique. Ce chapitre discutera quelques methodes plus efficaces. Contrairement a ce que l'on pourrait penser, les trois problemes sont bien distincts. Il se trouve que le premier admet de solutions efficaces, le deuxieme aussi pourvu que l'on sache factoriser n?1, tandis que le troisieme est en general tres difficile.

• critere deterministe selon agrawal-kayal-saxena


• critere probabiliste selon miller-rabin


• base sur les idees fondamentales de riemann


• test de fermat


• factorisation


• methode evidente de factorisation

Sujets

• Factorisation
• multiplication
• exercice
• mathe
• cours
• exercices

Informations

• Publié par: pefav
• Nombre de lectures: 143
• Langue: Français

Extrait

Distinguernombrespremiersetnombrescompos´es, et decomposer ces derniers en facteurs premiers, ´ est un des problemes les plus importants etlesplusutilesenarithm´etique. C.F. Gauss,Disquisitiones Arithmeticae, 1801

CHAPITRE XI

Primalit ´ eetfactorisationd'entiers

Objectifs Le th´ eme fondamental de l'arithme´tique garantit quetout entier positifneuqins´'emtdrieceuerian eor comme produitn=p e 1 1 p e 2 2   p k e k d'un certain nombrek≥0 de facteurs premiersp 1 <p 2 <  <p k de ´ multiplicit´ese 1 e 2     e k ≥1. Etant donne´ un entiern, trois problemes pratiques se posent : (1)D´eterminerrapidementsins´poomuce.etseiorrpme (2) Sinest premier, en trouver une preuve concise et facilement ve´ riable. (3) Sinsreimerpsruetcaf.tnasedemaripvureonensitiompod´ectsepmoce´soort, Pourlespetitsentierscesproblemessontfacilesare´suodre.Parcontrepourlesgrandsentiers,d´ejaapartir de30de´cimales,lesm´ethodes¨´echouentdemanirecatastrophique. Ce chapitre discutera quelques na ves methodes plus efcaces. Contrairement a ce que l'on pourarit penser, les trois problemes sont bien distincts. ´ Il se trouve que le premier admet de solutions efcaces, le deuxieme aussi pourvu que l'on sache factoriser n−´tiemroisidfrseartlnee´.leciuqsitele,1dnat e es en g Sommaire 1. Me´thodes  exhaustives.e.1.1rPmilati´e.1.2.Factorisanoit3.1.moC.xelp´eit.4.1ec.Lblri ´ d'Eratosthene.1.5.Factorisationlimit´ee.1.6.Lethe´oremedesnombrespremiers. ´ 2. Le  critere probabiliste selon Miller-Rabin. 2.1. Ele´ments non inversibles dansZ n ∗ . 2.2. Le testdeFermat.2.3.NombresdeCarmichael.2.4.L'astucedelaracinecarr´ee.2.5.Letest de Miller-Rabin. 2.6. Probabilite´ d'erreur. 2.7. Un test o ptimise´. 2.8. Imple´mentation du test. 2.9. Comment trouver un nombre premier ? 2.10. Comment prouver un nombre premier ? 3. Factorisation  par la me´thode Λde Pollard. 3.2. Le3.1. De´tection de cycles selon Floyd. paradoxe des anniversaires. 3.3. Polyn ˆomes et fonctions polynomiales. 3.4. L'heuristique de Pollard. 3.5. L'algorithme de Pollard. 3.6. Imple´mentati on et tests empiriques. 3.7. Conclusion. 4.Lecrite  rede ´ terministeselonAgrawal-Kayal-Saxena.4.1. Une belle caracte´risation des nombres premiers. 4.2. Polyn ˆomes cycliques. 4.3. Une imple´mentation basique. 4.4. Analyse de com- plexite´.4.5.Lad´ecouverted'Agrawal-Kayal-Saxena.4.6.Versuntestpratique? 5. Re´sume´  et perspectives. Voicitroisquestionspr´eliminairesquinousservirontdelconducteur: Question 0.1.mmentproCon´onetnendreirevuu'uqnest premier ? On pourrait tester tous les diviseurs possibles, . . . mais c'est hors de question sinest grand, comme 1 299 808 706 099 639 584 492 326 223 873. Existe-t-ilunepreuvedeprimalite´quisoitconciseetfacileav´erier?Voustrouv´u§2.10. erez une reponse a Le§4euisqteohed´rssueen´massezspeecenteet´riuq,erialucatcmeeblroeptlouesthe´oriquement. Question 0.2.compose´ ? C'est fac ile, dites-vous, il suft d'enComment prouver qu'un entier donne´ est exhiber un facteur. Certes, de petits facteurs sont faciles a trouver par des essais successifs . . . mais ce n'est plus praticable pour des facteurs grands. Ainsi pour d es cas commen=24!−1 on constate que la recherche exhaustive est trop co ˆuteuse. Nous regarderons des criteres plus efcaces au§2. Question 0.3.onvaincuqu'unenteidrno´n,eidossnpAsereˆ'scertn=24!−1, est compose´ de grands facteurs,onrevientalaquestiondefactorisation:commenttrouverefcacementlad´ecompositionen facteurs premiers ? Ceci peut ˆetre une tˆache tres dure. Au§3 nous pre´sentons une ide´e simple et amusante, 12 qui permet de trouver des facteurs de taille moyenne, disons entre 10 6  .et 10 187

188

ChapitreXI—Primalit´eetfactorisationd'entiers

1. Me´thodes  exhaustives 1.1.Primalit ´ e.tepourtee´evidenmilatie´tsrealrpomCncmee´madohtsno¸lrapitnenu'd:re Algorithme XI.1itpo´sim)eil´tiramseasperahausisex(nontifseptdesT Entre´e: un nombre natureln≥2 Sortie:le plus petit facteur premier den r← ⌊n⌋ pourdde2 a rfaire sid|nalors retournerd retournern Exercice/M 1.1.Justier cet algorithme : bien quedpneruocrapresbrometrsieems,pourqucompos´eio peut-on assurer que le facteur trouve´ soit premier ? Que se passe-t-il pournpremier ? Exercice/P1.2.Vous pouvez de´ja e´crire une fonctionbool estPremier( const Integer& n )qui teste sinest un nombre premier par des essais successifs. Veillez tout particulierement aux casn=0±1±2. Optimisation. —On peut e´conomiser 50% du temps, en procedant, a partir ded=3, par pas de+2. On peut encore ´ ´economiser33%dutempsenproce´dant,apartirded=5, par pas de+2+4+2+4   . D'autres optimisations analoguessontpossiblesmaisdeplusenpluscomplexesetdemoinsenmoinsefcaces(led´etailler).Onde´veloppera ´ une optimisation plus syste´matique avec le crible d' Eratosthene plus bas (§1.4). Exercice/M1.3.ontira´eemslansdoneltselti'derbmpirensleas?Jdescuedriell?sadseacuqsuqa'leueuQnenviron cetestest-ilraisonnable?Peut-onainsid´eterminerlanaturede1219326331002895961oude1219326331002895901? (On les analysera dans l'exercice 2.32 et 3.17 plus bas.) 1.2. Factorisation.:noirotctasilRemgaeer´ahotdsnneustientedefaode´evid Algorithme XI.2Factorisation par essais exhaustifs (non optimise´) Ent ´ un nombre natureln≥2 ree: Sortie:l'unique de´compositionn=p e 1 1 p e 2 2   p ke k en facteurs premiers p 1 <p 2 <  <p k avtlpiceum´tseilice 1 e 2     e k ≥1 r← ⌊n⌋,p←2 ,e←0 tant quep≤rfaire tant quep|nfairen←np,e←e+1 sie>0alorsrajouterp e a la factorisation, puis recalculerr← ⌊n⌋,e←0 p←p+1 n tant que sin>1alorsrajouter le facteur premierna la factorisation Exercice/M 1.4. Pourquoi un ?Justier cet algorithme : pourquoi ne produit-il que des facteurs premiers ´ventuel f t stantn>1 est-il premier ? e ac eur re Exercice/P1.5.Vous pouvez de´ja e´crire une fonction n Integer )vector<Integer> factorisation(qui cal- cule la factorisationn=p e 1 1 p e 2 2   p ke k et renvoie le vecteur(p 1 e 1 ;p 2 e 2 ;  ;p k e k ). Pour faire joli, vous pouvez ajouter une fonctionvoid affiche( vector<Integer>& dec )peuiqemmoncositiompod´ecurenceh'dfamrte 2^3∙3^2∙5∙17. Optimisation. —Voptimisatnterlesomilpe´emsuopvuzeecicrexet-aY.2.1diinnsioenes´eque´ednepo-iluilitssib n'effectuer qu'une seule division euclidienne pour testerp|niuereluqtoeitnetd´ednple cas e´che´ant ? (Est-ce une ´ optimisation importante ?) Plus bas on optimisera par le crible d' Eratosthene§(1.4), et plus tard on ajoutera le test de primalit´edeMiller-Rabin(§2.5). Exercice/M1.6.ocalelpmlleutseeQd:sesnavisseccussnoisivdiarnpioatisorctalafsnedtaoi´treed'iombreennxit´ le meilleur des cas ? dans le pire des cas ? Jusqu'a quelnenviron cette me´thode est-elle raisonnable ? Peut-on ainsi factoriser 24!− 3.16.)par exemple ? (On factorisera cet exemple dans l'exercice1 Exercice/P1.7.On appellenombre de Mersenne M k =2 k −1 aveck≥2. De´composer les nombresM 2     M 60 en facteurs premiers. Que se passe-t-il pourM 61 ? Expliquer le ralentissement observe´. (On reprendra cet exemple dans l'exercice 2.34 plus bas). MAE22 juin 2009