Zur rechnerischen Komplexität von Pepins Test

Question

Lassen $F_{n} = 2^{2^{n}} + 1$, wo $n > 0$.

Pepins Test behauptet das $F_{n}$ ist genau dann Prime, wenn $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.

FRAGE: Was ist das große-$\mathcal O$ Komplexität dieses Tests, wenn er in einem Algorithmus mit "wiederholtem Quadrieren" implementiert ist?

AUCH: Gibt es andere Tests zur Bestimmung der Primalität einer Fermat-Zahl, die effizienter sind als der Pepin-Test?

Answer 1

Der Test entspricht dem Testen, ob $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. Dies bedeutet, dass Sie Ganzzahlen mit einer ungefähren Größe bearbeiten$\log_2(F_n) \simeq 2^n$. Durch wiederholtes Quadrieren müssen Sie ausführen$O(\log(\frac{F_n-1}{2})) = O(2^n)$ Operationen mit solchen ganzen Zahlen, und jede hat Kosten $O(n2^n)$unter Verwendung des schnellsten bekannten ganzzahligen Multiplikationsalgorithmus. Insgesamt ist die Komplexität$O(n4^n)$.

Ich kenne keinen schnelleren Test.