# On the computational complexity of Pepin's test

Let $$F_{n} = 2^{2^{n}} + 1$$, where $$n > 0$$.

Pepin's Test asserts that $$F_{n}$$ is prime if and only if $$F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$$.

QUESTION: What is the big-$$\mathcal O$$ complexity of this test if it is implemented in an algorithm with repeated squaring''?

ALSO: Are there any other tests for determining the primality of a Fermat number more efficient than Pepin's Test?

The test is equivalent to testing whether $$3^{\frac{F_n-1}{2}} = -1\bmod F_n$$. This means that you manipulate integers of size roughly $$\log_2(F_n) \simeq 2^n$$. By repeated squaring, you have to perform $$O(\log(\frac{F_n-1}{2})) = O(2^n)$$ operations on such integers, and each one has cost $$O(n2^n)$$ using the fastest known integer multiplication algorithm. Altogether, the complexity is $$O(n4^n)$$.
• Repeated squaring takes $O(\log(\frac{F_n-1}2))=O(2^n)$ operations, not $O(\log(3^{\dots}))$. – Emil Jeřábek Oct 17 at 8:20