MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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

share|cite|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|cite|improve this answer
Regarding the search for Wilson primes, I have the impression that the distributed search in 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,…. – Tapio Rajala Mar 25 '11 at 22:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.