TEST DE PRIMALITÉ OPTIMISÉ
cs_jojolemariole
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
-
15 févr. 2010 à 09:40
cs_Julien39 Messages postés 6414 Date d'inscription mardi 8 mars 2005 Statut Modérateur Dernière intervention 29 juillet 2020 - 10 juin 2010 à 17:09
cs_Julien39 Messages postés 6414 Date d'inscription mardi 8 mars 2005 Statut Modérateur Dernière intervention 29 juillet 2020 - 10 juin 2010 à 17:09
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/51292-test-de-primalite-optimise
https://codes-sources.commentcamarche.net/source/51292-test-de-primalite-optimise
10 juin 2010 à 17:09
Java test la primalité mais je crois que le test est effectué jusqu'à un certain seuil (à vérifier)
10 juin 2010 à 13:38
non, on n'a pas besoin de super grands nombres pour les algorithmes probabilistes. En utilisant l'algorithme de l'exponentiation modulaire, tu gardes les calculs aussi petits que le nombre premier à tester, et en plus tu fais l'exponentiation en un temps logarithmique en P.
Evidemment, pour tester des "gros premiers" il te faudra une librairie de grands nombres (même si Java fait déjà ça non ?) mais ça restera viable, tu pourras tester du 4096 bits en un temps raisonnable. Enfin normalement, je ne connais pas les performances du Java.
Cordialement, Bacterius !
19 févr. 2010 à 19:15
15 févr. 2010 à 13:24
Alors oui le mathématicien dira que l'algo ne donne pas une réponse sûre à 100%, mais avec 50 itérations, la probabilité que le programme se trompe est inférieure à la probabilité que l'ordinateur fasse une erreur donc, on peut l'utiliser comme on utiliserait un algorithme déterministe.
Le principal soucis est qu'il faut pour utiliser un algorithme probabiliste faire des calculs qui donnent des résultats très volumineux puisqu'ils sont exponentiels, il faut calculer a^N-1 avec a un nombre choisi au hasard entre 2 et N-1 et N le nombre premier à tester.
Ce qui donne pour savoir si 100 est premier un nombre à 200 chiffres, et ce qui entraine un dépassement des variable évident. Alors qu'avec un algo bien optimisé, il suffit de faire 4 calculs pour savoir si 100 et premier...
L'algorithme probabiliste peut être utilisé sur des nombres très très grands, qui dépasseraient largement les capacité des types long
C'est pour toutes ces raisons que je n'ai pas présenté d'algorithme probabiliste ici. C'est il est vrai bien dommage parce que les méthodes de monté carlo sont toujours plutot séduisantes sur le papier.
Sinon, il y a une autre méthode qui est utilisée par certains logiciels qui est de tester la primalité pour un grand nombre de valeurs mais pas des valeurs aléatoires, par exemple, on teste pour tout les nombres premiers entre 2 et 10^10, mais ca, ce n'est pas une méthode probabiliste bien qu'elle en soit proche, mais il n'y a aucun aléa dans cette méthode et donc les résultats sont très mauvais dès l'instant ù on dépasse un certain seuil.
15 févr. 2010 à 09:40
Evidemment, tout dépend de l'utilisation, mais il me semblait qu'un algorithme probabiliste (donc pas sûr à 100%) donnait de meilleurs résultats. Ça pourrait être une alternative intéressante?