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