Tests de primalité : Miller-Rabin vs Test des 3 Indiens [Résolu]
scelw
- Messages postés
- 117
- Date d'inscription
- mercredi 3 septembre 2003
- Dernière intervention
- 17 février 2007
- Messages postés
- 706
- Date d'inscription
- mardi 30 décembre 2003
- Dernière intervention
- 27 janvier 2009
A voir également:
- Test de miller rabin
- Test miller rabin - Meilleures réponses
- Primalite - Meilleures réponses
- C / C++ / C++.NET : Test de primalité B: Miller-Rabin 32 bits - CodeS SourceS - Guide
- Teste si un tres grand nombre (plusieurs milliers de chiffres) est premier avec ntl et miller-rabin - Codes sources - C / C++ / C++.NET (Maths & Algorithmes)
- Java : Test de primalité optimisé - CodeS SourceS - Guide
- Power math: teste de vitesse entiers vs reels , class vs struct - Codes sources - C / C++ / C++.NET (Divers)
- Delphi / Pascal : Factorisation et test de primalité 32 bits ultra optimisé - CodeS So - Guide
1 réponse
Meilleure réponse
- Messages postés
- 706
- Date d'inscription
- mardi 30 décembre 2003
- Dernière intervention
- 27 janvier 2009
salut,
ce sont deux tests de nature différente.
celui de miller rabin est un test probabiliste, il retourne que n est
premier avec une probabilité d'erreur inférieure à 1/ 100 000 000 par
exemple. plus tu toleres une probabilité d'erreur importante plus le
test est rapide.
celui des trois indiens est un test deterministe, et il est en temps
polynomial. (pour n donné, l'algorithme ce termine en un temps en
O(log(n)^12)).
la réponse est donc ca dépend.
A mon avis miller rabin est plus rapide pour un seuil d'erreur de
l'ordre de 1/1million. apres il faudrait tester les résultats des deux
implémentations, ca peut etre interessant, mais je me souviens pas
avoir déja vu ca sur ce site (il est cependant possible que ca ait été
fait sans que je le remarque...)
en gros personnellement je connais pas la réponse, mais a mon avis miller rabin est plus rapide.
a++
ce sont deux tests de nature différente.
celui de miller rabin est un test probabiliste, il retourne que n est
premier avec une probabilité d'erreur inférieure à 1/ 100 000 000 par
exemple. plus tu toleres une probabilité d'erreur importante plus le
test est rapide.
celui des trois indiens est un test deterministe, et il est en temps
polynomial. (pour n donné, l'algorithme ce termine en un temps en
O(log(n)^12)).
la réponse est donc ca dépend.
A mon avis miller rabin est plus rapide pour un seuil d'erreur de
l'ordre de 1/1million. apres il faudrait tester les résultats des deux
implémentations, ca peut etre interessant, mais je me souviens pas
avoir déja vu ca sur ce site (il est cependant possible que ca ait été
fait sans que je le remarque...)
en gros personnellement je connais pas la réponse, mais a mon avis miller rabin est plus rapide.
a++
Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire
116 internautes nous ont dit merci ce mois-ci
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.