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?



On the computational complexity of 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)$.


I do not know of a faster test.


