Primalite et factorisation d'entiers

Publié par

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


Publié le : lundi 18 juin 2012
Lecture(s) : 126
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 25
Voir plus Voir moins
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
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.