Nueva prueba de primalidad determinista para números de la forma $p\cdot 2^n + 1$

Question

Edición: Lo siento, hubo un error.

Antigua reclamación (no es cierto porque hay un contraejemplo):

Dejemos que $p$ sea primo. Sea $n \in \left\{1, 2, 3, ...\right\}$ . Entonces $N = p\cdot 2^n+1$ es primo, si y sólo si mantiene la congruencia $3^{N-1} \equiv 1\ ($ mod $N)$ .

El derecho a reclamar es lo siguiente

Dejemos que $p$ sea primo. Sea $n \in \left\{1, 2, 3, ...\right\}$ . Entonces $N = p\cdot 2^n+1$ es primo, si y sólo si mantiene la congruencia $3^{(N-1)/2} \equiv \pm1\ ($ mod $N)$ .

Si la afirmación es cierta, tendríamos una prueba determinista rápida para números de la forma $p\cdot2^n + 1$ . Eso significa que, con pequeñas $p$ y grandes $n$ Podríamos generar números primos enormes, similares a los primos de Mersenne o de Fermat.

Hay muchas preguntas:

• ¿Es posible una prueba?
• En caso afirmativo, ¿puede la expresión $3^{(N-1)/2}$ ¿se evalúa más rápido que el test de Mersenne?
• Informática $3^{(N-1)/2}$ : ¿Existen métodos más rápidos que la exponenciación modular binaria?

Answer 1

Contraejemplo : $N=356387\cdot 2^{11}+1=12289\cdot 59393\;$ mientras que $\;3^{N-1}\equiv 1\pmod{N}$

Es interesante observar

• $\;2^{N-1}\not\equiv 1\pmod{N}\;$
• $\;12289=3\cdot 2^{12}+1\;$ mientras que $\;59393=29\cdot 2^{11}+1\;$ para que ambos factores primos sean (mínimos)
  $2^n$ safe-primes : OEIS A051900 .

Answer 2

Afirmación modificada (pseudoprima de Euler a base $3$ )

Considere $\,N =p\cdot 2^n+1\,$ con $p$ una prima impar y $n$ un número entero positivo, entonces según

El criterio de Euler que tenemos para $N$ una prima impar y $a$ coprima a $N$ : $$a^{(N-1)/2} \equiv \left(a\over N\right)\pmod{N}$$

con el Símbolo de Legendre en el lado derecho $\pm 1$ como se reclama en nuestro caso $a=3$ .

Lo contrario no es tan fácil, pero un buen comienzo puede ser Teorema de Lucas reforzado por Kraitchik y Lehmer (de Las páginas principales ) :

Dejemos que $N>1$ . Si para cada factor primo $q\,$ de $\;N-1$ hay un entero $a$ tal que

• $\displaystyle a^{N-1}\equiv 1\pmod{N},\quad$ y
• $\displaystyle a^{(N-1)/q}\not\equiv 1\pmod{N}$

entonces $\; N$ es primo.

Los únicos factores primos $q$ de $\,N-1\,$ son $2$ y $p$ . Si nos limitamos a la evaluación de las potencias de $a=3$ obtenemos :

si

• $\;\displaystyle 3^{(N-1)/2}\equiv -1\pmod{N}\;$ (lo que implica $\;3^{N-1}\equiv 1\pmod{N}$ ) $\quad$ y
• $\;\displaystyle 3^{(N-1)/p}\not\equiv 1\pmod{N}\;$

entonces $N$ es primo.

Obsérvese que los cálculos son bastante eficientes en este caso, ya que $\;(N-1)/p=2^n$ para poder evaluar $\;r:=3^{\large{2^{n-1}}}\pmod{N}$ sólo elevando al cuadrado y luego calcular $\;r^p\pmod{N}$ para la primera prueba y $\;r^2\pmod{N}$ para el segundo.

Esto es, por supuesto, más débil que su afirmación con el importante inconveniente de excluir $\;\displaystyle 3^{(N-1)/2}\equiv 1\pmod{N}\;$ cuando $3$ es un residuo cuadrático módulo $N$ que es aproximadamente la mitad de los casos interesantes para valores "no demasiado grandes" de $N$ ¡! (y el pequeño inconveniente de añadir una segunda prueba...)

Sin embargo, un examen más detallado muestra que $3$ será un residuo cuadrático módulo $N$ sólo si $n=1$ o $p=3$
(Creo que a partir de este resultado de la teoría de los residuos cuadráticos : $\left(3\over N\right)=+1\;$ si $\;N\equiv \pm 1\pmod{12}\;$ sin verificar todos los casos, lo admito...).
Por lo tanto, las condiciones anteriores deben aplicarse a todos los primos $\,N =p\cdot 2^n+1\,$ con $p$ prime $>3\;$ y $n>1$ .

El caso restante de primo $\,N =2\,p+1\,$ ("prima segura") fue estudiada por Sophie Germain mientras que el primer $\,N =3\cdot 2^n+1\,$ OEIS A039687 fue estudiado por Golomb .

Este resultado está incompleto pero debería ser al menos un comienzo...