Cette publication est accessible gratuitement
Télécharger
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
§´M—1thodesexhaustive e s
1.3. Complexite´.ice´lresmocaxelpsaEsnsyoprdeeuqitotpmysae´tiesodth´exmeusddeevssuitxeah ci-dessus. Soulignons d'abord qu'il est facile deposerurpon:iouronprpmilatilbeemedctorisat´eoudefa celailsuftdepr´esenterlenombrenebemaiin.Sre´eontirceeruiatsdisnealysaansinored,sytessn longueur=len(n)avec 21n<2C.teetnglouruetuesemeneruse´datauqepourlacomplexite´ud nombrenmoeamtlce´eeniroperiasscotselrutauskeretempsileecssnse´opruiaerrtte.ertelmsna:'cse ´ Proposition 1.8.Soit c()ripelsnadsnoitarlippnadoanquasecseuqlemolpxetilcared'it´e´eennomb me´thodes exhaustives de´crites ci-dessus aux entiers de longueur. Alors c()est exponentielle en. Exercice/M 1.9.elcratlirppoteetD´e,noixeetetserlin.ioitosr´esrAplastionsuremnuqeeuuodtmeeˆ r´epartitiondesnombrespremiers:est-cequelepiredescasseproduitr´eellementpourunelongueur tveeetsiCe'cef?fc´aelnendntomeel:s«postulat de Bertrand»mont,d´eracT´rpehcfeehybn1fe0,85 afrme qu'il existe au moins un nombre premier dans l'interv alle]a2a]quel que soita1. (Il en existe mˆemebeaucoupplus,commevouspouvezd´eduireduthe´oreme1.17ci-dessous.) ´ 1.4. Le crible d'Eratosthene.:seuqitadeesemremh´atsmnaiclpsu´hoenetsppelRandesonsu The´oreme1.10.spremires.erennintie´edonbmIlexisteu Vous ˆetes cordialement invite´s a rede´montrer ce joliers´ultat. Apres ce constat fondamental, conside´rons ´ la question pratique : comment construire la liste detousles nombres premiersm? Eratosthene de Kyrene(environ275–194avantnotreere)de´veloppaunee´tmhodequiestconnuesouslenomdecrible ´ d' Eratosthene. Dans la version originale on e´crit 2345    npuis on raye les multiples de 235   . Sur ordinateur ceci occupe trop d'espace. L'algorithme XI.3 ci-dessous en est une variante plus e´conome : ´ Algorithme XI.3Une variante du crible d' Eratosthene Entr´ee:la liste(p0=2p1=3    pk1)deskplus petits nombres premiers, aveck2 Sortie:la liste(p0=2p1=3    pk1pk)desk+1 plus petits nombres premiers ppk1+2,i1 tant quepi2pfaire sipipalorsii+1sinonpp+2,i1 n tant que retournerla liste prolonge´e(p0=2p1=3    pk1p) Exercice/P 1.11. XI.3 puis l'imple´menter en une fonctionProuver la correction de l'algorithmevoid ajoutePremier( vector<int>& liste ). Peut-on ainsi construire, dans un temps raisonnable, la liste des nombres premiers jusqu'a 106? jusqu'a 107? jusqu'a 108? jusqu'a 109? Exercice 1.12.PournNon noteϑ(n)le nombre des entiers premiers dans l'intervalle[1n]erircE´.nu programme qui litnau clavier et qui afcheϑ(n)la mesure du possible ve´rier les valeurs du tableau. Dans suivant (dans lequel au moins une erreur s'est glisse´e). kϑ(10k)kϑ(10k)kϑ(10k)kϑ(10k) 1 4 6 78 498 11 4 118 054 813 16 279 238 341 033 925 2 25 7 664 579 12 37 607 912 018 17 2 623 557 157 654 233 3 168 8 5 761 455 13 346 065 536 839 18 24 739 954 287 740 860 4 1 129 9 50 847 534 14 3 204 941 750 802 19 234 057 667 276 344 607 5 9 592 10 455 052 511 15 29 844 570 422 669 20 2 220 819 602 560 918 840 1.5.Factorisationlimit´ee.Dans un programme on procede typiquement comme suit : on xeune bornemet construit, une fois pour toute, la liste des petits nombres premiersp0    pkm. Selon le tableau ci-dessus, un choix entre 107et 108semble raisonnable, donc le typeintsufra. Exercice/M 1.13.En reprenant les algorithmes XI.1 et XI.2, expliquer pourquoi il est avantageux de par-courir seulement la listep0    pktuottcerruopecorrestit´eimaledrpettseueleqrri´e.Vnm2. De mˆeme, la factorisation est complete si le facteur restant satisafitnm2. Sin>m2on peut au moins garantir que nn'a pas de petits facteurs, mais on ne peut pas conclure quensoit premier.
189
MAE22 juin 2009