О вычислительной сложности теста Пепина

Question

Позволять $F_{n} = 2^{2^{n}} + 1$, где $n > 0$.

Тест Пепина утверждает, что $F_{n}$ прост тогда и только тогда, когда $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.

ВОПРОС: Что такое большой-$\mathcal O$ сложность этого теста, если он реализован в алгоритме с `` повторным возведением в квадрат ''?

ТАКЖЕ: Существуют ли другие тесты для определения простоты числа Ферма, более эффективные, чем тест Пепина?

Answer 1

Тест эквивалентен проверке того, $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. Это означает, что вы манипулируете целыми числами размера примерно$\log_2(F_n) \simeq 2^n$. Путем повторного возведения в квадрат вы должны выполнить$O(\log(\frac{F_n-1}{2})) = O(2^n)$ операции с такими целыми числами, и каждая из них имеет стоимость $O(n2^n)$используя самый быстрый из известных алгоритмов умножения целых чисел. В целом сложность$O(n4^n)$.

Я не знаю более быстрого теста.