|
14
|
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$. |
||||||||
|
|
10
|
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/.) |
|||
|
|
|
4
|
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. |
|||
|
