Cómo calcular $\left(\frac{n-1}{2}\right)!\pmod{n}$ rápido?

Question

Dado $n$ es un entero impar positivo ¿cuál es la manera más rápida para calcular $\left(\frac{n-1}{2}\right)!\pmod{n}$ ?

---

He observado que:

$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}$

Y por lo tanto:

$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}$

Así que esto reduce el número de multiplicaciones necesarias por $5$ y puede reducirse aún más si se siguen multiplicando los números así. Pero no sé cómo conseguir una fórmula de ella. Es posible?

Answer 1

Esta no es una respuesta completa, solo un par de observaciones: ciertamente no necesitamos que como una prueba de primalidad. En su lugar, hay polinomio de primalidad pruebas, de modo que podamos decidir si $n$ es compuesto, y luego, el resultado es $0$, esencialmente, con la excepción que se menciona en @Ian respuesta. Así que vamos a concentrarnos en el caso de que $n=p$ es una extraña prime. Es casi trivial corolario a Wilson no teorema que $$\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$, por lo que $$\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, y, una vez más, no sé de un método rápido para determinar que firmar.

Answer 2

Suponga $n$ es impar, compuesto, y no el cuadrado de un primo. A continuación, $n=dD$ con $1<d<D<n/2$. $d$ y $D$ están representados tanto en el producto $\left ( \frac{n-1}{2} \right )!$. Por lo que el resultado es cero.

Ahora imagine $n$ es el cuadrado de un primer $p$, entonces usted necesita $2p \leq \frac{p^2-1}{2}$ a sacar la misma conclusión, al asegurar que la $p$ $2p$ están representados tanto en el producto $\left ( \frac{n-1}{2} \right )!$. Para un entero positivo $p$ esto es equivalente a $p^2-4p>0$$p>4$. Por lo que el resultado es cero para las plazas de todos los impares primos excepto $3$.

En general, esto nos dice que el resultado es cero si $n$ es cualquier extraño compuesto con la excepción de $9$.

Es bastante fácil de calcular que el $4! \equiv -3 \pmod 9$, por lo que el caso puede ser manejado por cálculo directo. Para el prime $n$ no conozco una forma rápida de hacerlo (es decir, más rápido que el de $O(n)$). De hecho, yo soy escéptico de que hay una forma de hacerlo mucho más rápido que $O(n)$ (por ejemplo, el polinomio en $\log(n)$), porque si existiera, entonces esta sería una buena prueba de primalidad.