Quel est le test de primalité déterministe le plus rapide pour les nombres dans la gamme de 2^1024 à 2^4096?
j'écris une implémentation d'un protocole de cryptographie. Jusqu'à présent, j'ai eu de la difficulté à trouver le test de primalité déterministe le plus rapide pour les entiers de 1024 bits à 4096 bits (nombres de 308 à 1233 chiffres). Je suis au courant de plusieurs options, mais je n'ai pas été en mesure de trouver des comparaisons de vitesse dans le monde réel.
plus précisément, comment le test AKS se compare-t-il à la version déterministe du test Rabin-Miller et du test elliptique de vérification de la primalité (et d'autres) pour générale des nombres aléatoires de cette taille ?
3 réponses
Cet article est de répondre à votre question:
test de primalité par Richard P. Brent: http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf
il compare en complexité et en "vitesse du monde réel" les 3 algorithmes.
je suis nouveau, donc je ne peux pas commenter sur le lien ci-dessus, mais ici, c'est l'internet archive lien vers l'article: