Cálculo de factoriales modulo p^N

Question

¿Se puede calcular $(p-1)!$ modulo $p^2$ en polinomio de tiempo en $\log p$? ¡Puedo hacerlo modulo $p$! (El último es un signo de exclamación, no un factorial).

De manera más general, me gustaría poder calcular $d!$ modulo $p^N$ en polinomio de tiempo en $N \log p$.

Answer 1

Como sabrás, un primo de Wilson es un primo $p$ tal que $(p-1)!\equiv-1\pmod{p^2}$. Solo se conocen tres (5, 13 y 563), a pesar de que las búsquedas suben a $5\times10^8$. Presumiblemente, las personas que hacen estas búsquedas han investigado su pregunta, por lo que tal vez sea una buena idea revisar la literatura sobre los números primos de Wilson. El artículo de Wikipedia te ayudará a comenzar.