Sobre la complejidad computacional de la prueba de Pepin
Dejar $F_{n} = 2^{2^{n}} + 1$, dónde $n > 0$.
La prueba de Pepin afirma que $F_{n}$ es primo si y solo si $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.
PREGUNTA: ¿Cuál es la gran$\mathcal O$ complejidad de esta prueba si se implementa en un algoritmo con `` cuadratura repetida ''?
TAMBIÉN: ¿Existen otras pruebas para determinar la primacía de un número de Fermat más eficiente que la Prueba de Pepin?
Respuestas
La prueba es equivalente a probar si $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. Esto significa que manipulas enteros de tamaño aproximadamente$\log_2(F_n) \simeq 2^n$. Al cuadrar repetidamente, debe realizar$O(\log(\frac{F_n-1}{2})) = O(2^n)$ operaciones en tales enteros, y cada uno tiene un costo $O(n2^n)$utilizando el algoritmo de multiplicación de enteros más rápido conocido. En conjunto, la complejidad es$O(n4^n)$.
No conozco una prueba más rápida.