While teaching number theory this quarter, I have come across a phenomenon which was already addressed in another MO posting, but I have new questions. Let $p$ be a prime congruent to 3 mod 4. Then an elementary refinement of Wilson's theorem says that $\frac{p-1}2!$ is congruent to $\pm 1$ mod $p$. In fact, a published result of Mordell says that it is congruent to $(-1)^{(h+1)/2}$, where $h$ is the class number of the imaginary quadratic number field $\mathbb{Q}(\sqrt{-p})$. Mordell's identity is taken to mean that (1) you cannot expect $\frac{p-1}2! \in \mathbb{Z}/p$ to be governed by any very simple property of $p$ such as a congruence, and (2) we can conjecture but not prove that the density of both values is $\frac12$. So I wonder about the following:
(1) What is fastest known algorithm to compute $\frac{p-1}2! \in \mathbb{Z}/p$? I read somewhere that you can compute $h$ in time $O(p^{1/5})$, but for this question (actually for the interest of the class) I only care about $h$ mod 4.
(2) Never mind the density, is it known that both values occur infinitely often?
(3) If it is known that both values occur infinitely often, then is it known, for each $\text{gcd}(n,a) = 1$, that they occur infinitely often when $p = kn+a$? (It is of course Dirichlet's theorem that there are infinitely many such primes.)
Update: There as an subexponential time algorithm of McCurley to compute the class number $h$. I can believe that computing $h$ mod 4 wouldn't be any faster.