Computing factorials modulo p^N 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$.
 A: 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. 
A: 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/.)
