Voilà mon professeur de maths m'a dit qu'il existait un algorithme pour trouver plus rapidement les nombres premiers et que celui-ci s'appelait le test de primalité, si vous pouviez me le donner ce serait gentil ;-).
Merci.
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
[Algo] Test de primalité
Voilà mon professeur de maths m'a dit qu'il existait un algorithme pour trouver plus rapidement les nombres premiers et que celui-ci s'appelait le test de primalité, si vous pouviez me le donner ce serait gentil ;-).
Merci.
http://cermics.enpc.fr/polys/oap/node91.html
Merci
Le problème du test de primalité en un temps polynomial a été résolu l'année dernière par 3 indiens, après 3000 années d'efforts (
Cet algo est certes le premier à pouvoir resoudre le problème de la primalité en un temps polynomial. Mais est-il vraiment performant ? Je demande ça parce qu'un algo en O(1,2^n) qui bien que exponentiel n'est pas moins intéressant qu'un algo en O(n^100) pour les relativement petite valeur de n. Qu'en est-il de cet algo ?
Cet algorithme à surtout le mérite de répondre à la question: "Prime is in P" par OUI. Cela reste un gros résultat THEORIQUE.Envoyé par Nemerle!
En pratique, on utilise toujours Miller-Rabin (par exemple pour la génération des clés RSA) malgré son caractère probabiliste: il se peut qu'il indique un résultat comme 'Le nombre est premier' alors que c'est faux.
Pour les paranos, il y a aussi l'algo ECPP (Elliptic Curve Primality Proving: complexité O((lnN)^5 ou 6, je me rappelle pas): il est polynomial, probabiliste mais dans le sens ou il se peut qu'il ne réponde pas (mais c'est TRES,TRES rare) . Mais la réponse est toujours vraie (avec certificat de primalité ou non-primalité). C'est cet algorithme qui détient le record du plus grand nombre premier général (ie sans forme particulière comme les nombres de mersennes pour lequels il existe d'autres algorthimes).
Bref, contrairement à ECPP, AKS est simple à développer mais il trés, trés loin de le concurrencer. De plus, Miller-Rabin est amplement suffisant. Notre maître D.E Knuth à écrit: si un nombre aléatoire "passe" 25 tests de MR indépendant alors la probabiilité que celui-ci ne soit pas premier est inférieur à la probabilité d'un disfonctionnement du processeur dû à un rayon cosmique (D.E Knuth, The Art of Computer Programming. Volume2: Semi-Numerical Algorithms, p395).
A+
PS: Tout sur ECPP à http://www.lix.polytechnique.fr/~morain/Articles/articles.francais.html Attention ! De solides connaissances en géométrie algébrique et théorie des nombres sont requises pour lire ces publications.
Amilin>> Quand tu parles de "très très loin de le concurrencer", tu peux développer? Ancien matheux, je m'intéresse à l'AKS de façon ludique...
Autre remarque: l'AKS actuel n'est pas optimisé; ils pensent réduire à une complexité en t^5...
En fait, je me basais sur
http://www.lix.polytechnique.fr/Labo/Francois.Morain/aks-f.pdf
mais effectivement, le monde va vite et je n'avais pas vu les développements récents
http://developer.apple.com/hardware/ve/pdf/aks3.pdf
http://www-math.uni-paderborn.de/~preda/papers/myaks1.ps
http://cr.yp.to/papers/quartic.pdf
je verrais ça d'un peu plus près quand j'aurais le temps...
Apparement, sous certaines conditions (notamment la GRH), ils sont descendu à O(log(n)^(4+o(1)) (supposer la GRH n'étant pas un problème: si l'algorithme échoue, on a un contre exemple et la GRH est fausse ce qui seraît un résultat bien plus important que la primalité d'un entier... ). Le problème est (comme toujours) la constante dans le grand O...
Mais ECPP evolue aussi: ftp://lix.polytechnique.fr/pub/submissions/morain/Preprints/large.ps.gz... complexité heuristique O((log(n)^4). Détient actuellemnt le record de 10041 chiffres.
Et il faut aussi tenir compte de la complexité en MEMOIRE (qui apparement pose des problèmes dans l'AKS à cause de polynôme de degré gigantesque).
Bref, il faut laisser murir l'algo (par exemple, en factorisation, il a fallut attendre quelques années avant d'avoir un GNFS "rentable" par rapport au MPQS malgré une complexité inférieure et il ne l'est d'ailleurs toujours pas pour des nombres de moins d'~110 chiffres).
Moi aussi, même si mon intérêt pour la factorisation est supérieur.
Idem (enfin matheux... juste un DEA Algébre et géométrie)
A+
Merci de ces précisions! Moi ça a été un odctorat en représentations des gropues réductifs et cohomologie de Yoneda....
J'ai par ailleurs développé un générateur de nombres aléatoires superastronomique (de période 2^10281), avec juste une initialisation par 256 bits. Tu sais si les générateurs superastronomiques sont utilisés en pratique?
Le Caltech http://www.ugcs.caltech.edu/info/gsl/rng_8.html en conseille pour les simulations (il ne dise pas de quoi).Tu sais si les générateurs superastronomiques sont utilisés en pratique?
A+
Généralement quand un algo est polynomial, le degré est relativement faible. Et puis O(n^100) pour une entrée de taille 1000000 c'est toujours plus rapide que O(2^n) :-)
Par contre l'algo de primalité est un algo randomisé avec une probabilité d'erreur de 1/2 avec certaines propriétés. Du coup pour réduire la probabilité d'erreur on exécute plusieurs fois l'algo et à chaque fois on divise par 2 la probabilité d'erreur. Genre si on appelle 100 fois l'algo on a une probabilité de (1/2)^100 ce qui fait environ 1/(1000^10) ce qui est relativement correct.
Pour reprendre la question de la complexité de cet algo : même avec 100 voire 1000 appels de l'algo on reste en temps raisonnable pour une grande entrée.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager