Primalite et factorisation d'entiers
25
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
25
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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.
Voir
- 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
Distinguernombrespremiersetnombrescompos´es, et decomposer ces derniers en facteurs premiers, ´ est un des probl emes 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´'emtdrieceueri an eor comme produitn=pe11pe22 pkekd'un certain nombrek≥0 de facteurs premiersp1<p2< <pkde ´ multiplicit´ese1e2 ek≥1. Etant donne´ un entiern, trois probl emes 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, Pourlespetitsentierscesprobl emessontfaciles are´suodre.Parcontrepourlesgrandsentiers,d´ej a apartir de30de´cimales,lesm´ethodes¨´echouentdemanir ecatastrophique. Ce chapitre discutera quelques na ves methodes plus efcaces. Contrairement a ce que l'on pourarit penser, les trois probl emes sont bien distincts. ´ Il se trouve que le premier admet de solutions efcaces, le deuxi eme aussi pourvu que l'on sache factoriser n−´ti emroisidf rseartlnee´.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'Eratosth ene.1.5.Factorisationlimit´ee.1.6.Lethe´or emedesnombrespremiers. ´ 2. Le crite re 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.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´quisoitconciseetfacile av´erier?Voustrouv´u§2.10. erez une reponse a Le§4euisqteohed´rssueen´massezspeecenteet´riuq,erialucatcme eblroeptlouesthe´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 crit eres plus efcaces au§2. Question 0.3.onvaincuqu'unenteidrno´n,eidossnpAse reˆ'scertn=24!−1, est compose´ de grands facteurs,onrevient alaquestiondefactorisation:commenttrouverefcacementlad´ecompositionen facteurs premiers ? Ceci peut ˆetre une tˆache tr es 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
ChapitreXIPrimalit´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⌋ pourdde2a 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´j a e´crire une fonctionbool estPremier( const Integer& n )qui teste sinest un nombre premier par des essais successifs. Veillez tout particuli erement 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' Eratosth ene 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=pe11pe22 pkeken facteurs premiers p1<p2< <pkavtlpiceum´tseilice1e2 ek≥1 r← ⌊n⌋,p←2 ,e←0 tant quep≤rfaire tant quep|nfairen←np,e←e+1 sie>0alorsrajouterpe a la factorisation, puis recalculerr← ⌊n⌋,e←0 p←p+1 n tant que sin>1alorsrajouter le facteur premiern a 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´j a 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^3∙3^2∙5∙17. 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' Eratosth ene§(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=2k−1 aveck≥2. 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
