7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
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=pe11pe22  pkekd'un certain nombrek0 de facteurs premiersp1<p2<  <pkde ´ multiplicit´ese1e2    ek1. 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 dansZn. 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.Lecriterede´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 106 .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 natureln2 Sortie:le plus petit facteur premier den r← ⌊npourdde2arfaire 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 natureln2 ree: Sortie:l'unique de´compositionn=pe11pe22  pkeken facteurs premiers p1<p2<  <pkavtlpiceum´tseilice1e2    ek1 r← ⌊n,p2 ,e0 tant queprfaire tant quep|nfairennp,ee+1 sie>0alorsrajouterpea la factorisation, puis recalculerr← ⌊n,e0 pp+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=pe11pe22  pkeket renvoie le vecteur(p1e1;p2e2;  ;pkek). Pour faire joli, vous pouvez ajouter une fonctionvoid affiche( vector<Integer>& dec )peuiqemmoncositiompod´ecurenceh'dfamrte 2^33^2517. Optimisation. —Voptimisatnterlesomilpe´emsuopvuzeecicrexet-aY.2.1diinnsioenes´eque´ednepo-iluilitssib n'effectuer qu'une seule division euclidienne pour testerp|niuereluqtoeitnetd´ednple 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 Mk=2k1 aveck2. De´composer les nombresM2    M60en facteurs premiers. Que se passe-t-il pourM61? Expliquer le ralentissement observe´. (On reprendra cet exemple dans l'exercice 2.34 plus bas). MAE22 juin 2009