Take the 2-minute tour ×

Can one compute $(p-1)!$ modulo $p^2$ in time polynomial in $\log p$? I can do it modulo $p$! (The last one is an exclamation point, not a factorial.)

More generally, I would like to be able to compute $d!$ modulo $p^N$ in time polynomial in $N \log p$.

share|improve this question
How do you compute $(p-1)!$ modulo $p$ in time $\log p$? –  Michael Lugo Mar 25 '11 at 19:53
For $(p-1)!$ modulo $p$: Wilson's theorem and Primes is in P? –  Daniel Litt Mar 25 '11 at 20:11

2 Answers 2

I believe that the question whether $(p-1)! \bmod p^2$ is computable in polynomial time is still open. The best I am aware of is $O(p^{1/2+\epsilon})$, but I am not a specialist on this issue.

The computation of $(p-1)! \bmod p^2$ plays a role in certain p-adic algorithms to compute zeta functions of hypersurfaces in $\mathbb{P}^n$. There is an algorithm of David Harvey for zeta functions of hypersurfaces, where your question plays a role. I.e., the fact that this is not known that $(p-1)! \bmod p^2$ can be computed in less than $O(p^{1/2+\epsilon})$ is an obstruction to improve the complexity of this algorithm. (See the slides "Computing zeta functions of projective surfaces in large characteristic" on http://www.cims.nyu.edu/~harvey/.)

share|improve this answer

As you may know, a Wilson prime is a prime $p$ such that $(p-1)!\equiv-1\pmod{p^2}$. Only three are known (5, 13, and 563), despite searches going up to $5\times10^8$. Presumably, the people doing these searches have looked into your question, so maybe it's a good idea to go through the literature on Wilson primes. The Wikipedia article will get you started.

share|improve this answer
Regarding the search for Wilson primes, I have the impression that the distributed search in ibercivis.net is currently at around $2\times10^9$. I don't know much about the subject, but I would start by reading Crandall, Dilcher and Pomerance: A search for Wieferich and Wilson primes, ams.org/journals/mcom/1997-66-217/S0025-5718-97-00791-6/…. –  Tapio Rajala Mar 25 '11 at 22:31

Your Answer


