Teorema de prot

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de febrero de 2017; las comprobaciones requieren 6 ediciones .

En teoría de números, el teorema de Proth es una prueba de primalidad para los números de Proth .

Redacción

El teorema de Proth dice:

Si p es un número Prota de la forma , donde k es impar y , entonces p es primo (llamado Prota primo ) si y solo si para algún no residuo cuadrático a se hace la comparación: $k\cdot 2^{n}+1$ ${\displaystyle k<2^{n))$

a^{(p-1)/2}\equiv -1{\pmod {p))

Prueba

(a) Sea p primo. Entonces, para cualquier no residuo cuadrático a : por el criterio de Euler . $a^{(p-1)/2}\equiv -1{\pmod {p))$

(b) Sea para algún no residuo cuadrático a . Usamos el criterio de Pocklington , donde . Entonces es el único divisor primo . Comprobemos el cumplimiento de las condiciones del criterio: $a^{(p-1)/2}\equiv -1{\pmod {p))$ ${\ estilo de visualización n = 2 ^ {k} + 1}$ $q=2$ $n-1$

$a^{n-1}=(a^{(n-1)/2})^{2}\equiv 1{\pmod {n))$ - realizado.
números n y coprimos — hecho. ${\ estilo de visualización a^{(n-1)/q}-1}$

Como se cumple la condición, n es primo. [una] $2^{k}>{\sqrt {n}}-1$

Probando números de Proth para primalidad

El teorema de Proth se puede utilizar para probar la primalidad de los números de Proth. El algoritmo de prueba probabilística basado en el teorema es el siguiente: Se selecciona aleatoriamente un número entero tal que y calcula . Los siguientes resultados son posibles: $a$ $a\not \equiv 1{\pmod {p}}\$ $b\equiv a^{(p-1)/2}{\pmod {p}}\$

$b\equiv -1{\pmod {p}}\$ , entonces es primo por el teorema de Proth. $pags$
$b\not \equiv \pm 1{\pmod {p}}\$ y , entonces es compuesto, ya que son divisores no triviales de . $b^{2}\equiv 1{\pmod {p}}\$ $pags$ $mcd(b\pm 1,p)$ $pags$
$b^{2}\no \equiv 1{\pmod {p}}\$ , entonces p es compuesta por el pequeño teorema de Fermat .
$b\equiv 1{\pmod {p}}\$ , entonces el resultado de la prueba es desconocido.

El resultado (4) es la razón por la cual la prueba es probabilística. En el caso (1) , es un módulo cuadrático sin residuos . El procedimiento se repite hasta que se establece la simplicidad. Si es primo, entonces la prueba lo confirmará con una probabilidad en una iteración, ya que el número de módulos cuadráticos sin residuos es exactamente . [2] $a$ $pags$ $pags$ $pags$ $1/2$ $pags$ ${\ estilo de visualización (p-1)/2}$

Ejemplos

para p = 3, 2 1 + 1 = 3 es múltiplo de 3, por lo que 3 es primo.
para p = 5, 3 2 + 1 = 10 es un múltiplo de 5, por lo que 5 es primo.
p = 13, 5 6 + 1 = 15626 es divisible por 13, 13 es primo.
para p = 9, que no es primo, no existen b tales que a 4 + 1 sea divisible por 9.

Primos prota

Los primos Prot forman una secuencia:

3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449, 577, 641, 673, 769, 929, 1153… ( secuencia OEIS A080076 )

En mayo de 2017, el proyecto Primegrid ha encontrado el primo más grande conocido de Proth, 10223 2 31172165 + 1 . Tiene 9383761 dígitos decimales y es el número primo no Mersenne más grande conocido . [3]

Teorema de Proth generalizado

Lema. Deje para algunos primos l y . Sea la potencia de un número primo, donde . Si y , entonces n es primo . ${\ Displaystyle n = l ^ {k}}$ $k\geqslant 1$ ${\ Displaystyle r^{e}}$ ${\ estilo de visualización r \ neq l}$ $r^{e}{\mathcal {j}}\phi (n)$ $r^{e}>{\sqrt {n))$

Prueba. es un divisor , entonces . Si , entonces es una contradicción. Por lo tanto , y es simple.

{\ Displaystyle r^{e}}

{\ estilo de visualización \ phi (n) = (l-1) l^{k-1))

r^{e}{\mathcal {j}}l-1

{\ estilo de visualización k> 1}

{\ estilo de visualización \ phi (n) \ geqslant (l-1) l> r ^ {2} e> n}

{\ estilo de visualización k = 1}

norte

Teorema (teorema de Proth generalizado). Deje para algunos números primos y enteros . deja _ Si y para algún número entero , entonces es primo. $N=r^{e}t+1$ $r$ ${\ Displaystyle e, t \ geqslant 1}$ $r^{e}>t$ $a^{N-1}\equiv 1(modN)$ $a^{(N-1)/r}\no \equiv 1(modN)$ $a$ $norte$

La demostración del teorema generalizado se puede encontrar en Sze [4] .

Historia

François Prot (1852-1879) publicó el teorema alrededor de 1878.

Véase también

Número de Sierpinski

Notas

↑ Criptografía de clave pública: aplicaciones y ataques Archivado el 18 de diciembre de 2013 en Wayback Machine .
↑ Demostración de primalidad determinista en números de Proth Archivado el 7 de mayo de 2021 en Wayback Machine .
↑ Los veinte números primos más grandes conocidos Archivado el 16 de julio de 2012 en Wayback Machine .
↑ Tamaño, 2007 .

Enlaces

Weisstein, Eric W. Proth's Theorem (inglés) en el sitio web de Wolfram MathWorld .
"Revisión de controles de primalidad" , Kuchin, 2005
Sze, T. W. Sobre la resolución de ecuaciones polinómicas univariadas sobre campos finitos y algunos problemas relacionados . - Universidad de Maryland, College Park, 2007. - ISBN 9780549451037 .