Sobre a complexidade computacional do teste de Pepin

Question

Deixar $F_{n} = 2^{2^{n}} + 1$, Onde $n > 0$.

O teste de Pepin afirma que $F_{n}$ é primo se e somente se $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.

PERGUNTA: Qual é o grande$\mathcal O$ complexidade deste teste se ele é implementado em um algoritmo com `` quadratura repetida ''?

TAMBÉM: Existem outros testes para determinar a primalidade de um número de Fermat mais eficiente do que o teste de Pepin?

Answer 1

O teste é equivalente a testar se $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. Isso significa que você manipula inteiros de tamanho aproximadamente$\log_2(F_n) \simeq 2^n$. Por quadratura repetida, você tem que executar$O(\log(\frac{F_n-1}{2})) = O(2^n)$ operações em tais números inteiros, e cada um tem um custo $O(n2^n)$usando o algoritmo de multiplicação de inteiro mais rápido conhecido. Ao todo, a complexidade é$O(n4^n)$.

Não conheço um teste mais rápido.