$\def\ZZ{\mathbb{Z}}$Estoy realmente desconcertado por las personas que lleguen a este sitio y escribir muy detallada de las conjeturas acerca de las variantes de la Pepin o de Lucas-Lehmer pruebas de primalidad, luego afirman que no hay antecedentes teóricos. (Antes de ejemplos 1 2 3.) ¿Cómo encontrar esta conjetura si usted no tiene idea de cómo estas pruebas de trabajo?
Como veremos a continuación, su prueba de identificar correctamente todos los casos en que $8 \cdot 3^n-1$ es primo. Es muy probable que no regrese falsos positivos, pero no veo ninguna razón teórica no. Esto implica un poco de algo profundo de la teoría de números. Sin embargo, si que puede ser un poco curmedgeonly, también hay un número de primaria manipulaciones que podría haberse realizado en el inicio para hacer esto mucho más legible, y estoy perplejo en cuanto a por qué no.
Vamos a descansar de su fórmula.
$$S_{n-1} = P_{4 \cdot 3^n}(4) = (2+\sqrt{3})^{4 \cdot 3^n} + (2-\sqrt{3})^{4 \cdot 3^n}$$
$$ = (2+\sqrt{3})^{4 \cdot 3^n} + (2+\sqrt{3})^{-4 \cdot 3^n} =(2+\sqrt{3})^{(N+1)/2} + (2+\sqrt{3})^{-(N+1)/2}.$$
Se está probando si o no $S_{n-1} \equiv 4 \bmod N$ o, en otras palabras,
$$(2+\sqrt{3})^{(N+1)/2} + (2+\sqrt{3})^{-(N+1)/2} \equiv 4 \bmod N. \quad (\ast)$$
Estos son los elementales de las manipulaciones de la que hablé. Seguramente, cualquiera que esta conjetura fue consciente de algo como $(\ast)$ -- ¿por qué no?
Si $N$ es el primer: (Esta sección se reescribe para utilizar algunas observaciones acerca de las raíces de la unidad. Por lo tanto, puede tener un aspecto un poco menos motivados.) El primer $N$$-1 \bmod 24$, lo $N^2 \equiv 1 \bmod 24$ y el campo finito $\mathbb{F}_{N^2}$ contiene una primitiva $24$-ésima raíz de la unidad, llame a $\eta$. Tenemos $(\eta+\eta^{-1})^2 = 2 + \sqrt{3}$, para una de las dos opciones de $\sqrt{3}$$\mathbb{F}_N$. (Desde $N \equiv -1 \bmod 12$,$\left( \frac{3}{N} \right) =1$.) Ahora, $\eta \not \in \mathbb{F}_N$. Sin embargo, calculamos el $(\eta+\eta^{-1})^N = \eta^N + \eta^{-N} = \eta^{-1} + \eta$, ya que el $N \equiv -1 \bmod 24$. Por lo $\eta+\eta^{-1} \in \mathbb{F}_N$ y podemos deducir que $2+\sqrt{3}$ es un cuadrado en $\mathbb{F}_N$.
Por lo $(2+\sqrt{3})^{(N-1)/2} \equiv 1 \bmod N$$(2 + \sqrt{3})^{(N+1)/2} \equiv (2 + \sqrt{3}) \bmod N$. Del mismo modo, $(2 + \sqrt{3})^{-(N+1)/2} \equiv (2+\sqrt{3})^{-1} \equiv 2 - \sqrt{3} \bmod N$ $(\ast)$ mantiene.
Si $N$ no es primo. Antes, me dijo que yo no veía la manera de controlar si o no $(\ast)$ al $N$ fue compuesto. Me dijo que no parecía haber ninguna razón por la que debe sostener y que, además, seguramente, fue muy raro, porque $N$ es exponencialmente grande, por lo que es poco probable que por un azar de la igualdad para sostener modulo $N$.
Desde entonces he tenido un par de ideas más sobre el problema, que no lo hacen parecer fácil, pero aclarar por qué es tan difícil. Para hacer la vida más fácil, vamos a suponer que $N = p_1 p_2 \cdots p_j$ es la plaza libre. Por supuesto, $(\ast)$ mantiene modulo $N$ si y sólo si contiene cada modulo $p_i$.
Deje $\eta$ ser una primitiva $24$-ésima raíz de la unidad en una extensión de $\mathbb{F}_{p_j}$. Las siguientes ecuaciones se llevan a cabo en esta extensión de $\mathbb{F}_{p_j}$. Resulta que $(\ast)$ factores un poco:
$$(2+\sqrt{3})^{(N+1)/2} + (2+\sqrt{3})^{-(N+1)/2}=4$$
$$ (2+\sqrt{3})^{(N+1)/2} = 2 \pm \sqrt{3}$$
$$ (\eta+\eta^{-1})^{(N+1)} = (\eta+\eta^{-1})^2 \ \mathrm{or} \ (\eta^5+\eta^{-5})^2$$
$$ (\eta+\eta^{-1})^{(N+1)/2} \in \{ \eta+\eta^{-1},\ \eta^3+\eta^{-3},\ \eta^5+\eta^{-5}, \eta^7+\eta^{-7} \}. \quad (\dagger)$$
Aquí es lo que me gustaría hacer en este momento, para seguir a las líneas de Lucas-Lehmer de prueba, pero no puede.
(1) me gustaría saber que $(\eta+\eta^{-1})^{(N+1)/2} = \eta+\eta^{-1}$, no una de las otras opciones en $(\dagger)$. (Esto es lo que realmente ocurre en la $N$ el primer caso, como se muestra anteriormente). Esto implicaría que $(\eta+\eta^{-1})^{(N-1)/2} =1 \in \mathbb{F}_{p_j}$.
(2) me gustaría saber que el orden de las $\eta+\eta^{-1}$ fue precisamente la de $(N-1)/2$, no un divisor de los mismos.
(3) me gustaría, por consiguiente, a la conclusión de que el grupo multiplicativo de a $\mathbb{F}_{p_j}$ fue de orden divisible por $(N-1)/2$, y por lo tanto $p_j \geq (N-1)/2$. Esto significaría que, básicamente, sólo hay lugar para uno $p_j$, y que sería capaz de concluir primalidad.
Ahora, (1) no es tan malo, porque directamente se podría calcular en el ring $\ZZ/(N \ZZ)[\eta]/(\eta^8-\eta^4+1)$, en lugar de tratar de ocultar este anillo con primaria polinomio de fórmulas. Así, aunque no creo que su algoritmo comprueba este punto, no sería difícil.
Y $(2) \implies (3)$ es correcta.
Pero usted tiene un verdadero problema con $(2)$. Esta forma en que esto funciona en el de Lucas-Lehmer prueba es que usted está tratando de demostrar que $2+\sqrt{3}$ ha pedido precisamente, $2^p$ en el campo de $\mathbb{F}_{2^p-1}[\sqrt{3}] \cong \mathbb{F}_{(2^p-1)^2}$. Ya sabes que $(2 + \sqrt{3})^{2^p}=1$. Por lo que es suficiente para comprobar que el $(2 + \sqrt{3})^{2^{p-1}}=-1$, no $1$.
En la situación actual, el análogo cosa sería comprobar que el $(\eta+\eta^{-1})^{(N-1)/(2q)} \neq 1$ por cada prime $q$ dividiendo $(N-1)/2$. Pero no tengo idea de que los números primos se dividen $q$! Esto parece como un gran obstáculo para una prueba de que $(\ast)$ implica $N$ es primo.
Para repetir: yo creo que bien puede ser cierto que $(\ast)$ implica $N$ es primo, simplemente porque no hay ninguna razón para que los $(\dagger)$ debe mantener una vez $N \neq p_j$, y las probabilidades de $(\dagger)$ ocurre por accidente son exponencialmente pequeño. Pero no veo el mundial principio de lo que esto implica.
