How to compute $\left(\frac{n-1}{2}\right)!\pmod{n}$ fast?

Question

Given $n$ is a positive odd integer what is the fastest way to compute $\left(\frac{n-1}{2}\right)!\pmod{n}$ ?

---

I've observed that:

$2 \cdot \left(\frac{n-1}{2}\right) \equiv -1 \pmod{n}$

$3 \cdot \left(\frac{n-1}{2} - 1\right) \equiv \frac{3n-9}{2} \pmod{n}$

$4 \cdot \left(\frac{n-1}{2} - 2\right) \equiv -10 \pmod{n}$

And therefore:

$2 \cdot 3 \cdot 4 \cdot \left(\frac{n-1}{2}\right) \cdot \left(\frac{n-1}{2} - 1\right) \cdot \left(\frac{n-1}{2} - 2\right) \equiv (-1) \cdot \left(\frac{3n-9}{2}\right) \cdot (-10) \equiv -45 \pmod{n}$

So this reduces the number of multiplications needed by $5$ and it can be reduced even more if we continue multiplying the numbers like that. But I don't know how to get a formula from it. Is it possible at all?

Answer 1

Assume $n$ is odd, composite, and not the square of a prime. Then $n=dD$ with $1<d<D<n/2$. $d$ and $D$ are both represented in the product $\left ( \frac{n-1}{2} \right )!$. So the result is zero.

Assume now $n$ is the the square of a prime $p$, then you need $2p \leq \frac{p^2-1}{2}$ to draw the same conclusion, by ensuring that $p$ and $2p$ are both represented in the product $\left ( \frac{n-1}{2} \right )!$. For positive integer $p$ this is equivalent to $p^2-4p>0$ so $p>4$. So the result is zero for squares of all odd primes except $3$.

Overall this tells us that the result is zero if $n$ is any odd composite except $9$.

It's easy enough to calculate that $4! \equiv -3 \pmod 9$, so that case can be handled by direct calculation. For prime $n$ I don't know a fast way to do it (i.e. faster than $O(n)$). In fact I am skeptical that there is a way to do this much faster than $O(n)$ (e.g. polynomial in $\log(n)$), because if there were then this would be a good primality test.

Answer 2

This is not a full answer, just a few observations: We certainly don't need that as a primality test. Instead, there are polynomial primality tests, so we can decide if $n$ is composite, and then, the result is $0$, essentially, with the exception mentioned in @Ian's answer. So let's concentrate on the case where $n=p$ is an odd prime. It's an almost trivial corollary to Wilson't theorem that $$\left[\left(\frac{p-1}2\right)!\right]^2=(-1)^{(p+1)/2}$$ The RHS is $1$ for $p=4m+3$, and $-1$ for $p=4m+1$, so $$\left(\frac{p-1}2\right)!=\pm1\pmod p$$ for $p=4m+3$, as @Michael Behrend noticed in his comment. The question is: $+1$ or $-1$? Good question. For $p=4m+1$, it's by no means difficult to find a solution of $x^2=-1\pmod p$, but our result can be $+x$ or $-x$, and once again, I don't know of a fast method to determine that sign.