Sujet Précédent Sujet Suivant

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

scelw Messages postés 117 Date d'inscription mercredi 3 septembre 2003 Statut Membre Dernière intervention 17 février 2007 - 14 déc. 2004 à 15:29
scelw Messages postés 117 Date d'inscription mercredi 3 septembre 2003 Statut Membre Dernière intervention 17 février 2007 - 23 déc. 2004 à 18:48
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

Réponse 1 / 1
scelw Messages postés 117 Date d'inscription mercredi 3 septembre 2003 Statut Membre Dernière intervention 17 février 2007
23 déc. 2004 à 18:48
nobody knows ?
0

Discussions similaires

Erreur d’exécution 424 : objet requis
luciol8 -
Marion8316 -

7 réponses
comment créer une interface web de gestion d'emploi du temps
cs_syrinemz -
Julien39 -

7 réponses
erreur d'execution 9
cs_getrare -
getrare -

7 réponses
erreur d'execution '9'
cs_tracto -
tracto -

10 réponses
Logiciels open source pour Tests de non-régression, robustesse, etc.
Chabossio -
Chabossio -

2 réponses
Rejoignez-nous