Sulla complessità computazionale del test di Pipino

Question

Permettere $F_{n} = 2^{2^{n}} + 1$, dove $n > 0$.

Il test di Pipino lo afferma $F_{n}$ è primo se e solo se $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.

DOMANDA: Qual è il grande$\mathcal O$ complessità di questo test se implementato in un algoritmo con `` quadratura ripetuta ''?

ANCHE: Esistono altri test per determinare la primalità di un numero di Fermat più efficienti del test di Pipino?

Answer 1

Il test equivale a verificare se $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. Ciò significa che si manipolano più o meno interi di dimensione$\log_2(F_n) \simeq 2^n$. Con la squadratura ripetuta, devi eseguire$O(\log(\frac{F_n-1}{2})) = O(2^n)$ operazioni su tali numeri interi, e ciascuno ha un costo $O(n2^n)$utilizzando l'algoritmo di moltiplicazione di numeri interi più veloce conosciuto. Complessivamente, la complessità è$O(n4^n)$.

Non conosco un test più veloce.