¡El valor$\pm 1$ para la raíz cuadrada del teorema de Wilson, ((p-1) / 2)! mod p

Question

Mientras que la enseñanza de la teoría de los números en este trimestre, me han llegado a través de un fenómeno que ya se había abordado en otro MO publicar, pero tengo nuevas preguntas. Deje $p$ ser un primer congruente a 3 mod 4. Luego de una escuela primaria refinamiento de Wilson, el teorema dice que el $\frac{p-1}2!$ es congruente a $\pm 1$ mod $p$. De hecho, la publicación de un resultado de Mordell dice que a es congruente a $(-1)^{(h+1)/2}$ donde $h$ es el número de clase del imaginario cuadrática campo de número de $\mathbb{Q}(\sqrt{-p})$. Mordell la identidad se refiere a que (1) usted no puede esperar $\frac{p-1}2! \in \mathbb{Z}/p$ a ser regidos por un muy simple propiedad de $p$ tales como la congruencia, y (2) podemos conjeturar, pero no demuestra que la densidad de ambos valores es $\frac12$. Lo que me pregunto acerca de lo siguiente:

(1) ¿Qué es más rápido que se conoce el algoritmo para calcular los $\frac{p-1}2! \in \mathbb{Z}/p$? Leí en alguna parte que usted puede calcular el $h$ en el tiempo $O(p^{1/5})$, pero para esta pregunta (en realidad para los intereses de la clase) lo único que importa $h$ mod 4.

(2) no importa la densidad, se sabe que ambos valores se producen infinitamente a menudo?

(3) Si se sabe que ambos valores se producen infinitamente a menudo, entonces se sabe, para cada una de las $\text{gcd}(n,a) = 1$, que se producen infinitamente a menudo al $p = kn+a$? (Es, por supuesto, del teorema de Dirichlet que hay infinitamente muchos de esos números primos.)

---

Actualización: como un subexponential tiempo algoritmo de McCurley para calcular el número de clase $h$. Yo puedo creer que la computación $h$ mod 4 no iba a ser más rápida.

Answer 1

Respecto a tu pregunta (1), aquí hay dos artículos sé lidiar con el problema de la informática factoriales :

Crandall, Dilcher, Pomerance. Una búsqueda de Wieferich y Wilson de los números primos. De matemáticas. Comp. 66 (1997), no. 217, 433--449. (MR1372002)

Costa, Gerbicz, Harvey. Una búsqueda de Wilson de los números primos.

(Recordemos que Wilson de los números primos son aquellos números primos $p$ tal que $(p-1)! \equiv -1 \mod{p^2}$.)

Resulta que existe un algoritmo para calcular el producto de $N$ términos en una progresión aritmética en no más de $O(N^{\alpha+\epsilon})$ multiplicaciones, con $\alpha = \frac{\sqrt{5}-1}{2} = 0.618...$ (ver pág. 441 en el primer artículo). También mencionar un algoritmo para calcular $(p-1)! \mod{p^2}$ en el tiempo $O(p^{1/2+\epsilon})$.

El segundo artículo, parece usar un método algo diferente y alcanza un promedio de tiempo polinomio algoritmo para calcular esta cantidad, haciendo uso del hecho de que no son redundantes productos cuando se considera que muchos de los valores de $p$.

Ambos artículos siempre el trabajo de mod $p^2$. Sin duda es más rápido para trabajar sólo mod $p$, pero no estoy seguro de si esto tiene un impacto en el teórico y el tiempo de ejecución de los algoritmos.

Answer 2

Como se sugiere en el comentario por Greg Martin, la determinación de la paridad de $(h + 1)/2$ se puede realizar de manera más eficiente que calcula el factorial de expresión de Lagrange del refinamiento de Wilson del teorema. Dirichlet, "Pregunta d'analyse indéterminée," Journal für die Reine und Angewandte Mathematik 3 (1828): 407-408; reimpreso en Werke 1:107-108, señaló que su paridad depende del número de cuadrática nonresidues de $p$ que se extiende entre los $1$ e $p/2$ (OEIS la secuencia. A178151). Este número es generalmente designado $m$ en la literatura.

Saltando sobre muchos de los resultados parciales, el valor de $m$ fue investigado en detalle por Louis C. Karpinski en su tesis de doctorado (Mathematischen und Naturwissenschaftlichen Facultät der Kaiser Wilhelm-Universität zu Strassburg, 1903), publicado como "Über die Verteilung der quadratischen Reste," Journal für die Reine und Angewandte Mathematik 127 (1904): 1-19. Karpinski resultó ser un conjunto de fórmulas que involucran sumas de Legendre símbolos, y demostró que la mayoría de los concisa sumas posible contener sólo $\lfloor p/6 \rfloor$ términos:

\begin{equation} m = \frac{p-1}{4} - \frac{1}{2} \sum_{k=1}^{(p-1)/2} \left(\frac{k}{p}\right) \quad (p \equiv 3 \bmod{4}; p > 3); \end{equation}

\begin{equation} m = \frac{p-1}{4} - \frac{2-\left( \frac{2}{p} \right)}{3-\left( \frac{3}{p} \right)} \sum_{k=1}^{\lfloor p/3 \rfloor} \left(\frac{k}{p}\right) \quad (p \equiv 3 \bmod{4}; p > 3); \end{equation}

\begin{equation} m = \frac{p-1}{4} - \frac{1}{2} \sum_{k=\lfloor p/4 \rfloor +1}^{(p-1)/2} \left(\frac{k}{p}\right) \quad (p \equiv 3 \bmod{8}; p > 3); \end{equation}

\begin{equation} m = \frac{p-1}{4} - \frac{1}{2} \quad \sum_{k=1}^{\lfloor p/4 \rfloor} \quad \left(\frac{k}{p}\right) \quad (p \equiv 7 \bmod{8}; p > 3); \end{equation}

\begin{equation} m = \frac{p-1}{4} - \frac{2-\left( \frac{2}{p} \right)}{1 + \left(\frac{2}{p}\right) + \left( \frac{3}{p}\right) - \left( \frac{6}{p} \right)} \sum_{k=1}^{\lfloor p/6 \rfloor} \left(\frac{k}{p}\right) \quad (p \equiv 7, 11, 23 \bmod{24}); \end{equation}

\begin{equation} m = \frac{-5p-1}{4} + \frac{3}{2} \sum_{k=1}^{\lfloor p/6 \rfloor} \left(\frac{k}{p}\right) \quad (p \equiv 19 \bmod{24}). \end{equation}