Tests de primalité : Miller-Rabin vs Test des 3 Indiens
Résolu
scelw
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007
-
9 janv. 2005 à 14:47
cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 - 9 janv. 2005 à 16:42
cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 - 9 janv. 2005 à 16:42
A voir également:
- Miller rabin python
- Miller rabin - Meilleures réponses
- Miller-rabin - Meilleures réponses
- Test de primalité - Forum Visual Basic 6
- Tester un numéro de téléphone - Forum PHP
- Tests informatiques recrutement - Conseils pratiques -C# / .NET
- Test de bit ✓ - Forum VB.NET
- Testé la valeur du 7ème bit - Forum C
1 réponse
cosmobob
Messages postés
700
Date d'inscription
mardi 30 décembre 2003
Statut
Membre
Dernière intervention
27 janvier 2009
4
9 janv. 2005 à 16:42
9 janv. 2005 à 16:42
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++
