À propos de l'algorithme de Miller-Rabin
Bonjour
J'ai une question simple. Combien de temps mon pc (i5 2,4 Ghz) prendra environ pour tester avec le test de Miller-Rabin la primalité du nombre $ 2^{p}-1 $ avec $p$ nombre premier à 10 millions de chiffres en base décimale.
Je sais que l'algorithme a une complexité de $O(\log^3(n))$. C'est juste que ça reste ambigu pour moi car une université américaine à découvert dans le début des années 2000 un nombre premier de plus de 10 millions de chiffres en une vingtaine de jours. Ce qui me semble trop rapide pour une test déterministe alors que celui de Miller-Rabin aurait pris plus de temps sans être sûr à 100% de la primalité du nombre.
Merci pour vos réponses.
J'ai une question simple. Combien de temps mon pc (i5 2,4 Ghz) prendra environ pour tester avec le test de Miller-Rabin la primalité du nombre $ 2^{p}-1 $ avec $p$ nombre premier à 10 millions de chiffres en base décimale.
Je sais que l'algorithme a une complexité de $O(\log^3(n))$. C'est juste que ça reste ambigu pour moi car une université américaine à découvert dans le début des années 2000 un nombre premier de plus de 10 millions de chiffres en une vingtaine de jours. Ce qui me semble trop rapide pour une test déterministe alors que celui de Miller-Rabin aurait pris plus de temps sans être sûr à 100% de la primalité du nombre.
Merci pour vos réponses.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
il te faut déjà regarder sur le site du projet GIMPS ;
https://gaz.wiki/wiki/fr/GIMPS
en décembre 2018 Leur dernier nombre de Mersenne prime trouvé est M51 avec l'exposant 82589933 ce nombre premier a
24 862 048 chiffres décimaux...
Ce n'est pas tellement le temps mis par ton pc avec le logiciel du GIMPS pour savoir si ton nombre serra premier probable, c'est qu'ensuite il faut le valider et cela prend environ 3 semaines à 1 mois avec de grands calculateurs parmi les plus puissants... ce que tu ne pourras pas faire...
ils utilisaient le test de Lucas-Lehmer ... peut être ont ils changé avec d'autres tests déterministes ..
pour info : Le 4 décembre 2020, le projet a franchi une étape importante après que tous les exposants inférieurs à 100 millions aient été vérifiés au moins une fois.
Ce qui sous entend qu'il te faut prendre un exposant remier > à 100 000 000. par exemple un de cela :
102039269 le deuxième nombre, c'est sa position dans la suite des nombres premiers 29 modulo 30
102039299 734014
102039449 734015
102039689 734016
102039869 734017
102040079 734018
102040319 734019
102040649 734020
102040769 734021
102040889 734022
102040979 734023
102041339 734024
102041399 734025
102041519 734026
102041669 734027
102041699 734028
102041759 734029
102041909 734030
102041969 734031
102041999 etc etc...
Bonne chance
Je ne connais pas la taille des nombres premiers exigées pour les chiffrements de type RSA par exemple ! Donc si tu pouvais m'éclairer la dessus ca serait bien et peut être que mon algorithme serait utile finalement.
Ces nombres sont ils premiers, temps mis pour les tester.?
673332671497482768501774531057586931009132156874577164996728337447925630978
421555644107311043460437666753948314136356644562650399725304938329133773289
30374723386866581321
16674885570614132090543945739720241056167331649658646262566037062680981802
46561617212759870289981436810020072001478859690358093048731490464920972462
087040456385051225337357
16674885570614132090543945739720241056167331649658646262566037062680981802
46561617212759870289981436810020072001478859690358093048731490464920972462
087040456385051225337327
16674885570614132090543945739720241056167331649658646262566037062680981802
46561617212759870289981436810020072001478859690358093048731490464920972462
087040456385051225337201
67333267149748276850177453105758693100913215687457716499672833744792563097
84215556441073110434604376667539483141363566445626503997253049383291337732
8930374723386866581413
67333267149748276850177453105758693100913215687457716499672833744792563097
84215556441073110434604376667539483141363566445626503997253049383291337732
8930374723386866581497
et un petit dernier
714987423907879999547175353583460069520910132380956486551334455295468427705175175364129
330657434690927653159476815653100126525874296179246129370976808281237552403930613612626
396223197669365035941332131016243252563303112882253752159065422770555642729852427045984
263635220160126555322389770738537449446681580906998791255082404758482521226412721424621
661879587443433980872584618145313011315198383080145295246453499379683495317641031542972
0290250412302577
112277452481764409089921796077601584519957107405139435484582814155
205900974601247477639327625773800240085171550709486825248770500852
786179681041120730126129842903571105675811105546658606945435902420
165139784967530572801823342442073191415721859697621463211326059715
398310249457220635164351922729117082878714191309429783773594306605
333159083429
Ce n'est pourtant pas le but de ta question "un peu ridicule", comment alors peux-tu avancer des complexités sur ton soi-disant algorithme...
Donc tu demandes des choses que tu es incapable de résoudre... une fois mis au pied du mur ! Autrement dit programmer du vent ce n'est pas spécifique...(td)
Complexité d'un algorithme : se calcule de manière théorique. ( pas besoin de savoir coder pour connaître la complexité d'un algorithme).
j'ai un algorithme ultra-rapide pour déterminer si un nombre est premier ou pas. Mais il " fonctionne avec des nombres particuliers (et qui peuvent avoir 10 millions de chiffres voir plus ). ". Et je sais même le programmer.
Vous aussi, d'ailleurs, puisqu'il ne fonctionne qu'avec les nombres pairs :-D
Bon, je plaisantais, mais Amine82 tu n'es pas sérieux toi non plus. Tu demandes combien de temps mettrait un algorithme généraliste alors que ton programme ne l'est pas !!
Je ne cours pas très vite, mais dans une course avec un cul de jatte sans appareil, j'arrive à gagner !!
Donc soit tu exposes ce que tu sais faire et on peut continuer une discussion utile, en sachant quels "nombres particuliers" sont en cause. Pour les nombres de Mersenne, dont tu parles au départ, on utilise des méthodes adaptées, et la comparaison est à faire avec le test de Lucas-Lehmer.
Cordialement.
Quand je rappelais dans mon dernier message le "10 millions de chiffres" c'étais en réponse à LEG suite à une longue discussion ...L'algorithme que j'ai trouvé ne teste pas si "un nombre particulier est premier ou pas "; il teste plusieurs nombres qui ont une forme particulière jusqu'à ce qu'il trouve un nombre premier avec une forte probabilité ( probabilité de le trouver non pas qu'il soit premier ...le nombre qu'il trouve, si il le trouve, est forcément premier ). Et tout ca avec la même complexité de l'algorithme de Miller-Rabin.
Je voulais juste avoir une idée sur combien de temps prend en pratique un tel test.
Si je peux me permettre, comment est-il possible de connaître certaines caractéristiques d'un algorithme sans connaître son code ?
C'est par ouï-dire ? Estimation au doigt mouillé ? Oracle ?
Merci de préciser car ce point m'intéresse pour les futurs algorithmes que je compte développer sans avoir à trop les connaître.
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
https://fr.wikipedia.org/wiki/Analyse_de_la_complexité_des_algorithmes
Je sais que mon algo à une complexité de $O(\log^3(n))$ même si je ne l'ai pas encore codé.
Comme ce genre de question se traite dans les milieux spécialisés, tu vas perdre ton temps ici, ce n'est pas un forum de spécialistes de la cryptographie.
Et encore une fois, la comparaison n'a pas de vrai sens.
Un algorithme, c'est une succession d'instructions, éventuellement en français,
Construire tableau avec les nombres premiers entre 2 et 100
n=101
Tester si n a un diviseur parmi les éléments du tableau
Si oui alors .. sinon ....
Boucler avec n=n+2, tant que n< 10^10
Et comme on n'a pas installé de compilateur, ni quoi que ce soit, on a juste cet algorithme.
Et on est en mesure de donner une bonne approximation du nombre de boucles qu'il faudra pour cette boucle.
Bonne continuation.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Et pour savoir combien de temps prendrait l'ordinateur de Amine82, des tests sur des nombres premiers à 100 ou 500 chiffres avec une implémentation de Miller-Rabin permet d'avoir une idée. Et ça, Amine82 peut le faire, nous pas.
Que vient foutre la spécificité d'un algorithme déterministe pour tester des entiers, s'il n'est pas capable de les tester ...
Et au vue de la taille de l'exposant il veut commencer avec des nombres de plusieurs milliards de chiffres ...:-S , rien que pour taper l'exposant il lui faudrait une semaine (:P)