Aide à propos de Miller-Rabin et du temps d'exécution des tests de primalité en

Signaler
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007
-
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007
-
Bonjour,

Deux questions :

1°) Pour calculer le nombre d'opérations nécessaires à la réalisation d'un test probabiliste de Miller-Rabin, j'ai entendu dire qu'il fallait calculer "O(t*log(n))", avec t le nombre donné à tester, et n le "nombre de tours" réalisé avec le test de Miller-Rabin. Sachant que le test de Miller-Rabin est considéré comme très fiable ) à partir de 20 tours (dans ce cas, la probabilité pour que le nombre testé ne soit pas premier est égale à 1/(4^20), soit environ 10^(-12).), fixons "n = 20". Donc on a la formule "O(t*log(20))".
J'aimerai qu'une personne compétente en la matière me confirme ces propos et qu'elle m'explique, surtout, à quoi correspond la fonction "O()".

2°) Est-ce que le test de Miller-Rabin est, en terme de nombre d'opérations à effectuer donc de temps d'exécution, l'algorithme le plus rapide pour déterminer la primalité d'un nombre ? Je précise qu'à mes yeux, un test probabiliste dont la marge d'erreur est inférieure à 10^(-9) est considéré comme sûr. Je précise aussi que je travaille avec de très grands nombres (comportants plus de 100 000 chiffres).

Merci pour votre aide,

ScelW

1 réponse

Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007

nobody knows ?