Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
3  
For $(p-1)!$ modulo $p$: Wilson's theorem and Primes is in P? –  Daniel Litt Mar 25 '11 at 20:11
add comment

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
add comment

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
add comment

Your Answer

 
discard

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.