Prueba para la nueva prueba de primitiva determinista

Question

Reclamación:

Deje que$p$ sea una prima positiva. Dejar $n \in \left\{1, 2, 3, ...\right\}$. Entonces $ N = p \ cdot 2 ^ n +1$ is prime, if and only if it holds the congruence $ 3 ^ {(N-1) / 2} \ equiv \ pm1 \ ($mod $ N) $.

Si el reclamo es verdadero, tendríamos una prueba determinista rápida para los números de la forma$p\cdot2^n + 1$. Eso significa que con un pequeño$p$ y un gran$n$, podríamos generar números primos enormes, similares a los primos de Mersenne o los primos de Fermat.

Se necesita una prueba. Gracias por tu atención.

Answer 1

@Igor Rivin

Voy a responder a Su pregunta aquí. He hecho una investigación acerca de los números primos, y he encontrado una nueva determinista de la prueba de primalidad para la seguridad de los números primos. Esta prueba es el siguiente: Tenemos dos declaraciones:

1.) Deje $p=3$ (mod $4$) son primos. $2p+1$ es principal si y sólo si $2p+1$ divide $2^p−1$.

2.) Deje $p=1$ (mod $4$) son primos. $2p+1$ es principal si y sólo si $2p+1$ divide $2^p+1$.

(Instrucción 1. está comprobado por Lagrange en 1775, y la declaración 2. está demostrado por Batominovsky 2015)

Así que si un número $N=2\cdot p+1$ mantiene la congruencia $2^p\equiv \pm1\ ($mod $N)$ entonces definitivamente es el primer.

Desde este punto fui un paso más allá a $N=p\cdot2^n + 1$.

Answer 2

Pensé que podría probar que en el caso de un signo negativo, pero sólo puedo mostrar que en este caso, para que fija $n$, sólo puede haber un número finito de contraejemplos. Nada de mágico $3$ por el camino.

Deje $p$ ser el primer y $n$ un entero tal que $N=2^np + 1$ es tal que, para algún entero $a$ tenemos $a^{(N-1)/2} \equiv -1 \pmod N$. A continuación, $N$ es primo o $p \le a^{2^{n-1}}/2^n$.

Prueba: Supongamos $m$ ser el orden de $a$ modulo $N$,, a continuación,$m | 2^np$, lo $m = 2^k$ o $2^kp$ para algunos $k \le n$. Ya tenemos $-1$ en la congruencia en la hipótesis, llegamos a la conclusión de que $k=n$. Si $m = 2^np$,, a continuación, $N$ es el primer ($\phi(N)=N-1$ fib $N$ es primo). La única otra posibilidad es $m=2^n$. Suponga que es el caso. A continuación, $2^n | \phi(N)$ pero no podemos tener a $p|\phi(N)$, ya que obligaría a $\phi(N) \ge N-1$. Por lo $(p,\phi(N))=1$ y la congruencia $a^{(N-1)/2} \equiv -1 \pmod N$, implica entonces que $a^{2^{n-1}} \equiv -1 \pmod N$. Por lo $N \le a^{2^{n-1}} + 1$ dando el resultado.