Sur la complexité de calcul du test de Pepin

Question

Laisser $F_{n} = 2^{2^{n}} + 1$, où $n > 0$.

Le test de Pepin affirme que $F_{n}$ est premier si et seulement si $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.

QUESTION: Quel est le grand$\mathcal O$ complexité de ce test s'il est implémenté dans un algorithme avec `` squaring répété ''?

AUSSI: Y a-t-il d'autres tests pour déterminer la primalité d'un nombre de Fermat plus efficaces que le test de Pepin?

Answer 1

Le test équivaut à tester si $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. Cela signifie que vous manipulez des nombres entiers de taille à peu près$\log_2(F_n) \simeq 2^n$. Par quadrillage répété, vous devez effectuer$O(\log(\frac{F_n-1}{2})) = O(2^n)$ opérations sur de tels entiers, et chacun a un coût $O(n2^n)$en utilisant l'algorithme de multiplication d'entiers connu le plus rapide. Dans l'ensemble, la complexité est$O(n4^n)$.

Je ne connais pas de test plus rapide.