À propos de l'algorithme de Miller-Rabin

amine82 · August 2021

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.

LEG · August 2021

Tu veux prendre un exposant de 10 million de chiffres ...? c'est une plaisanterie ? :)o

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

amine82 · August 2021

Merci LEG. (tu)

LEG · August 2021

Mais à ta place je testerai déjà avec ""ton algorithme de nombre premier "" que tu penses avoir trouvé, voir le temps que cela te prend et si un de ces nombres est indiqué comme premier , rien ne t'empêche de le déclarer sur le GIMPS il y a une prime...:-D

amine82 · August 2021

Oui sauf que le mien a une complexité de $O(\log^3(n))$ voir $ O(\log^4(n))$pour trouver un nombre premier (avec une bonne probabilité de le trouver) :-D
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.

LEG · August 2021

dans les nombres du RSA il y en a quelques un en attente environ 250 chiffres

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

LEG · August 2021

Si tu veux tester ce nombre RSA P*q :

112277452481764409089921796077601584519957107405139435484582814155
205900974601247477639327625773800240085171550709486825248770500852
786179681041120730126129842903571105675811105546658606945435902420
165139784967530572801823342442073191415721859697621463211326059715
398310249457220635164351922729117082878714191309429783773594306605
333159083429

amine82 · August 2021

Merci Leg mais l'algorithme dont je parle est un algorithme spécifique...de plus je n'ai pas encore le code :-D.

LEG · August 2021

Bonjour

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)

amine82 · August 2021

Spécifique : veut dire fonctionne avec des nombres particuliers (et qui peuvent avoir 10 millions de chiffres voir plus ).

Complexité d'un algorithme : se calcule de manière théorique. ( pas besoin de savoir coder pour connaître la complexité d'un algorithme).

gerard0 · August 2021

Moi,
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.

amine82 · August 2021

Gerard,

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.

Dreamer · August 2021

Bonjour.

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.

amine82 · August 2021

Dreamer je parlais du code source ..en réponse à LEG qui me demandais de tester de grands nombres.
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é.

gerard0 · August 2021

Ton test ne sera utilisable pour l'utilisation concrète de grands premiers que si la forme particulière reste secrète. Et encore ... es-tu sûr que ce n'est pas déjà utilisé ?
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.

lourrran · August 2021

On peut avoir un algorithme, et ne pas avoir le code correspondant.
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.

Dreamer · August 2021

Voici donc une explication du test en question.

Bonne continuation.

gerard0 · August 2021

Pour en revenir au premier message, tester ce genre de nombre avec Miller-Rabin ne semble pas raisonnable, et le reste du message est du baratin sans rapport.

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.

LEG · August 2021

Je pense que si il n'est pas capable de tester les petits nombres que je lui ai donnés, "" car son algorithme est spécifique "" ::o c'est une plaisanterie ...

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)

À propos de l'algorithme de Miller-Rabin

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 20