Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Primalite et factorisation d'entiers

25 pages
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


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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin