-
@DarkRedman fiable, mais lente.On twitter.com
Mood 0
-
@DarkRedman C’est inapplicable sur des nombres aussi grand que 2^4096.Permalink On twitter.com
Mood +3 🙂
-
@DarkRedman Donc on fait du test de prime probabilistes (rapide) et quand on pense qu’on en tient un bon, on relance des tests plus lourds.Permalink On twitter.com
Mood 0
-
@DarkRedman La méthode naïve demanderait de tester tous les nombres impaires entre 3 et N/2, ce qui fait ~2^4094 tests.Permalink On twitter.com
Mood -2 🙁
-
@DarkRedman Ça prendrait des dizaines de milliards d’années.Permalink On twitter.com
Mood 0
-
@DarkRedman Ne faire que 3000 tests, ça serait laisser quasiment tous les tests de côté (2^4094-3000 ~= 2^4094)Permalink On twitter.com
Mood 0
-
@DarkRedman Alors que Miller-Rabin permet une probabilité de primalité à 1/(4^n) si tu fais n essais.Permalink On twitter.com
Mood 0
-
@DarkRedman Donc par exemple, tu vas commencer par écrémer avec n=10000, et dès que tu trouves un candidat, tu relances avec n=1000000.Permalink On twitter.com
Mood 0