2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .