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?

New contributor
J. Bogdan Yaromir is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

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.

| cite | improve this answer | |
  • $\begingroup$ Repeated squaring takes $O(\log(\frac{F_n-1}2))=O(2^n)$ operations, not $O(\log(3^{\dots}))$. $\endgroup$ – Emil Jeřábek Oct 17 at 8:20
  • $\begingroup$ Of course! Sorry for that, and I correct! $\endgroup$ – Bruno 2 days ago

Your Answer

J. Bogdan Yaromir is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.