Teorema de Proth

En teoría de números , el teorema de Proth es un teorema que constituye la base de una prueba de primalidad para los números de Proth conocida como prueba de Proth . Los números de Proth, a veces llamados números de Proth de primera especie , son aquellos enteros p que toman la forma p = k²ⁿ + 1 con un k impar donde k < 2ⁿ ^. Para los números de Proth de segunda especie , véase el tema relacionado: ^números de Riesel . El teorema también recibe su nombre del matemático francés y su autor original, François Proth.

El teorema establece ^{[ 1 ]}^{[ 2 ]} que para cualquier número de Proth (de primera especie), p , entonces p es primo si existe un entero a para el cual el criterio de Euler produce –1, es decir,

a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

.

En este caso, p se denomina primo de Proth . La contrapositiva también es cierta: si p es compuesto de Proth, entonces no existe tal a .

Prueba de Proth

Basta con encontrar un único valor de a para que la prueba confirme de forma determinista la primalidad, siempre que p sea un número de Proth. Verificar que p sea un número de Proth es una tarea trivial.

Esta es una prueba práctica porque, si p es primo, cualquier valor de a elegido tiene aproximadamente un 50 % de probabilidad de funcionar, y si p no es primo, ningún valor de a elegido funcionará. Además, dado que el cálculo es módulo p , solo se deben considerar valores de a menores que p .

Variante ingenua sistemática

Si p es compuesto de Proth, entonces ninguna base a funcionará para dar testimonio de primalidad. Si alguna base a da testimonio, entonces se confirma la primalidad. Si ninguna lo hace, entonces se confirma la composición. Esto se debe a que el inverso del teorema de Proth también es cierto:

Si no existe ningún a tal que

a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

y p es un número de Proth, entonces p es compuesto.

La contrapositiva de esta afirmación es que si p es un número primo de Proth, se garantiza que tal valor de a existirá.

En efecto, si p es un número primo de Proth, cabe esperar que aproximadamente la mitad de los valores de a satisfagan la congruencia, en el caso general. Por otro lado, si no se cumple la segunda condición —si p no es un número de Proth—, no se puede garantizar la composición (lo contrario no suele ser cierto para números que no son de Proth), incluso si se cumple la primera condición de congruencia.

Por lo tanto, podemos comprobar sistemáticamente todos los valores base [2, p − 1] para verificar la composición (nótese que a = 0 y a = 1 nunca funcionarán), a menos que se encuentre uno que confirme la primalidad. Este proceso, como se indica, aunque es el más sencillo y trivial, puede hacerse más eficiente.

En principio, dado que si p es primo, hay aproximadamente un 50% de probabilidad de que un a elegido demuestre primalidad, podemos hacer el proceso un poco más eficiente comprobando aproximadamente la mitad de todos los posibles valores de a menores que p ; esperamos que la mitad de dichos valores satisfagan la congruencia. Una vez que se han probado más de p /2 valores distintos de a , la composición es determinista. Esto se debe a que, si p es primo, entonces esperamos que la mitad de todas las bases den testimonio; por el principio del palomar , una vez que se ha comprobado más de la mitad, podemos deducir que ninguna dará testimonio, y si ningún valor base a funciona, entonces p es compuesto. Si por otro lado p es primo, entonces al menos uno de los valores comprobados inevitablemente habría dado testimonio, al igual que todos los valores restantes no comprobados. Esta variación de la prueba es similar a la variante determinista de la prueba de primalidad de Fermat .

Ambas variantes ingenuas son sumamente ineficientes y nunca se emplean en la práctica. Cabe destacar que, en el peor de los casos, ambos enfoques requieren un esfuerzo computacional significativamente mayor que la simple división por ensayo y error (método Schoolhouse).

Variante probabilística de Monte Carlo

Dado que se espera que el 50% de las bases a demuestren primalidad, si p es realmente primo, podemos formular una prueba probabilística de Monte Carlo de la siguiente manera: si la prueba se realiza repetidamente m veces, cada iteración con un a aleatorio , y cada vez no se confirma la primalidad, podemos inferir que p es probablemente compuesto . Esto contrasta con los resultados de "probablemente primo" típicos de otros algoritmos de Monte Carlo, como la prueba de Miller-Rabin . También se puede inferir una probabilidad de error aproximada del límite superior $ε < 2 - m$ de que un primo se identifique erróneamente como compuesto. Sin embargo, un compuesto nunca se identificará erróneamente como primo.

Esta implementación probabilística no se realiza habitualmente. Si bien es mucho más eficiente que la prueba ingenua determinista, con una eficiencia computacional comparable a la de la prueba de Miller-Rabin, aún se puede mejorar tanto en tiempo de ejecución como en precisión (o definitividad).

Variante de Las Vegas

La formulación de Las Vegas de la prueba de Proth es, con diferencia, la más eficiente de las variantes, y tan concluyente como la variante determinista. Esta es la variante que se suele emplear, aunque aún existen algunos matices en el método de implementación.

En la práctica, se encuentra un no residuo cuadrático de p y se toma como el valor de a . Dado que, si a es un no residuo cuadrático módulo p, entonces el recíproco del teorema de Proth también es cierto (si el criterio de Euler no produce –1, entonces p es compuesto) y la prueba se vuelve concluyente (bidireccional). El teorema puede reformularse:

Para todos los números de Proth p , y para cualquier no residuo cuadrático a de p , p es primo si y solo si

a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

.

Un no residuo cuadrático a de p puede identificarse cuando el símbolo de Legendre es –1, por lo tanto, para tal valor de a :

\left({\frac {a}{p}}\right)=-1.

Para tal valor de a , la prueba es determinista tanto para la primalidad como para la composición; por lo tanto, para tal a, la verificación contra los criterios de Proth/Euler solo requiere una iteración: la congruencia o no congruencia con -1 describe completamente la primalidad. La dificultad radica en encontrar tal valor de a .

Determinación de la base

El valor de a puede hallarse mediante la comprobación sistemática de valores en el intervalo [2, p − 1], mediante selección y verificación aleatorias, o mediante un cálculo más directo (la opción más eficiente), comparándolo con el símbolo de Legendre. En cualquier caso, cuando un valor de a se verifica con el símbolo de Legendre como un candidato válido, y por lo tanto un residuo cuadrático no residual, puede aplicarse en el criterio de Proth/Euler para determinar de forma concluyente la primalidad o la composición.

En general, una verificación sistemática no es excesivamente ineficiente; los candidatos son bastante comunes y es probable encontrar uno en pocos intentos, independientemente de si p es primo o compuesto. Si bien los no residuos cuadráticos son comunes tanto si p es primo como si no, hipotéticamente solo pueden ser raros o inexistentes cuando p es compuesto. Podemos deducir de forma concluyente que p es compuesto si no se encuentra ningún no residuo cuadrático. Cualquier búsqueda exhaustiva es computacionalmente costosa.

La selección aleatoria tampoco es excesivamente ineficiente en el caso general; la probabilidad de encontrar un candidato es de aproximadamente el 50 % por iteración. Si bien encontrar un candidato de esta manera es un problema probabilístico, una vez encontrado, la solución es determinista. Podemos inferir la composición probabilística (Monte Carlo) con un umbral de confianza si, mediante selección aleatoria, no se encuentra ningún no residuo que satisfaga el símbolo de Legendre en un número razonable de intentos, aunque siempre existe una probabilidad distinta de cero de obtener un resultado falso.

Por las razones expuestas, se suele emplear un cálculo más directo mediante un algoritmo euclidiano modificado . Esto se hace para garantizar una prueba determinista (y eficiente). Si el cálculo directo de un no residuo cuadrático falla —debido a su inexistencia—, entonces la composición puede deducirse con absoluta certeza.

Así, a diferencia de muchas pruebas de primalidad de Monte Carlo (algoritmos aleatorios que pueden devolver un falso positivo o un falso negativo ), esta variante determinista del algoritmo de prueba de primalidad es un algoritmo de Las Vegas , que siempre devuelve la respuesta correcta pero con un tiempo de ejecución que varía aleatoriamente .

La comprobación contra el criterio de Proth, una simple operación de exponenciación modular , una vez que se ha determinado a , tiene un tiempo de ejecución del orden de la longitud en bits de p ; por lo tanto, la variabilidad aleatoria en el tiempo de ejecución general de la prueba es principalmente el resultado de la búsqueda de un valor de a apropiado , sea cual sea la forma en que se realice.

Formas simplificadas

Dado un número de Proth p = k²n + 1, se han identificado formas particulares de p , k y ⁿ que corresponden a valores cuadráticos no residuales predeterminados que son apropiados para su uso. Se ha demostrado que :

Si $p>3$ y $3\nmid k$ , entonces $a=3$ es siempre un no residuo cuadrático (candidato) y, por lo tanto, una base válida para comprobar, y así:

3^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

si y solo si p es primo.

Esta es la base de la prueba de Pépin para los números de Fermat y sus primos correspondientes, en la que k = 1 es indivisible por 3.

Si $p>8$ y p es 3 o 5 módulo 8, entonces $a=2$ es siempre un no residuo cuadrático (candidato) y, por lo tanto, una base válida para comprobar, y así:

2^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

si y solo si p es primo.

Si $p>5$ y p es 2 o 3 módulo 5, entonces $a=5$ es siempre un no residuo cuadrático (candidato) y, por lo tanto, una base válida para comprobar, y así:

5^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

si y solo si p es primo.

Aunque no existe una regla tan simple para el caso en que p sea 1 o 4 módulo 5, en este último caso (4 módulo 5) se pueden aumentar sistemáticamente las probabilidades de encontrar un candidato a no residuo cuadrático comprobando valores en las proximidades de las dos raíces cuadradas distintas de 5 módulo p . Si no hay precisamente dos raíces cuadradas distintas (véase el algoritmo de Tonelli-Shanks ), entonces p no es primo. El cálculo directo del no residuo sigue siendo probablemente más eficiente.

Ejemplos numéricos

Algunos ejemplos del teorema son:

para p = 3 = 1(2 ¹ ) + 1, tenemos que 2 ^(3−1)/2 + 1 = 3 es divisible por 3, por lo que 3 es primo.
para p = 5 = 1(2 ² ) + 1, tenemos que 3 ^(5−1)/2 + 1 = 10 es divisible por 5, por lo que 5 es primo.
para p = 13 = 3(2 ² ) + 1, tenemos que 5 ^(13−1)/2 + 1 = 15626 es divisible por 13, por lo que 13 es primo.
Para p = 9, que no es primo, no existe ningún a tal que a ^(9−1)/2 + 1 sea divisible por 9.

El hecho de que p = 9 no sea primo puede verificarse de forma determinista comprobando que no existe ningún a (en módulo 9) que cumpla esta condición. Esto puede hacerse comprobando sistemáticamente cada valor de a desde 2 hasta 8 ( a = 0 y a = 1 nunca funcionarán para ningún p ). Sin embargo, basta con comprobar los valores del 2 al 5, es decir, la mitad de todos los valores posibles menores que 9. Si 9 fuera primo, entonces, por el principio del palomar, al menos uno de estos valores de a confirmaría la primalidad, puesto que se espera que la mitad de ellos lo hicieran.

Alternativamente, si empleamos la variante determinista en la que el no residuo cuadrático se calcula directamente, el trabajo requiere menos iteraciones para confirmar tanto la composición como la primalidad:

para p = 97 = 3(2 ⁵ ) + 1, tenemos un no residuo cuadrático de a = 5, y 5 ^(97−1)/2 + 1 = 3552713678800500929355621337890626 es divisible por 97, por lo que 97 es primo.
para p = 1537 = 3(2 ⁹ ) + 1, tenemos un no residuo cuadrático de a = 5, y 5 ^(1537−1)/2 + 1 = 1052 (mod 1537) no es divisible por 1537, por lo que 1537=29×53 no es primo.

En cada uno de los dos ejemplos anteriores, se calculó directamente un valor apropiado de a mediante un cálculo de no residuo cuadrático, de modo que los resultados de la prueba fueran concluyentes: un no residuo cuadrático válido tanto en el caso primo como en el compuesto. No era necesario buscar sistemáticamente un valor de a para observar el caso primo, ni repetir la prueba un número suficiente de veces para el caso compuesto. Si no se encuentra un no residuo cuadrático, o si no existe, podemos interpretarlo como una confirmación de la composición.

Resultados de pruebas alternativas

El criterio de Euler proporciona información adicional sobre un número p , que no necesariamente forma parte del teorema de Proth. Se trata de hechos secundarios atribuidos en gran medida a otros teoremas, cuya evaluación es trivial durante cualquier aplicación del criterio de Proth. El número p no tiene por qué ser un número de Proth para que el criterio sea útil. Dado un entero p , elijamos un valor arbitrario para a . Evalúe el criterio de Euler:

a^{\frac {p-1}{2}}\equiv b{\pmod {p}}.

Generalmente existen cinco resultados distintos. Algunos de estos resultados no dependen de que p sea un número de Proth y, por lo tanto, son válidos para cualquier tipo de candidato primo.

Primalidad de p :

b = −1, en cuyo caso se cumple el criterio de Proth y se confirma que p es un primo de Proth, según el teorema de Proth, si efectivamente p es un número de Proth.

Si p no es un número de Proth pero b = −1, entonces esto es indicativo, pero no concluyente, de primalidad. Consulte la prueba de primalidad probabilística de Solovay-Strassen y la prueba de Miller-Rabin .

Resultado no concluyente:

b = 1, en cuyo caso la prueba no es concluyente y debe repetirse con un nuevo valor de a .

Esta condición es la que requiere reiteración y hace que la prueba sea probabilística, como si p fuera primo, entonces b = ±1 ocurre con una probabilidad aproximadamente igual, aunque la condición b = 1 aún puede cumplirse con p compuesto o no Proth.

Esto es cierto a menos que a resulte ser también un no residuo cuadrático de un número de Proth p , en cuyo caso se indica la composición.

La composición de p , según el criterio de Euler y el símbolo de Legendre , que ofrecen condiciones de salida temprana cuando b ≠ ±1. En cada uno de estos casos, p no es primo y tampoco tiene por qué ser un número de Proth:

b ² = 1, siendo los divisores no triviales de p el MCD( b ± 1, p ).
b ² ≠ 1, donde p se demuestra compuesto por la prueba de Fermat, base a .
b = 0, donde p tiene un divisor no trivial MCD( a , p ).

Certificado Proth

Un certificado de Proth es un certificado de primalidad asociado a los números de Proth y, específicamente, a la prueba de Proth. Es un documento o prueba digital que verifica cualquier condición que demuestre primalidad (o composición). Generalmente contiene los valores k y n que componen el número de Proth, p , lo que prueba que se trata de un número de Proth, así como el valor a que prueba la primalidad. También puede probar la composición, si procede. El certificado suele mostrar el trabajo de prueba, incluyendo evidencia de que a es un no residuo cuadrático, etc., si es necesario.

Búsqueda Prime

Los primeros números primos de Proth son (secuencia A080076 en el OEIS ) :

3, 5, 13, 17, 41 , 97 , 113 , 193 , 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ....

El primo Proth más grande conocido hasta 2016es 10223 × 2 ^31172165 + 1, y tiene 9.383.761 dígitos de longitud. ^{[ 3 ]} Fue descubierto por Peter Szabolcs en el proyecto de computación voluntaria PrimeGrid , que lo anunció el 6 de noviembre de 2016. ^[⁴^] Es el undécimo número primo conocido más grande a partir de enero de 2024, fue el primo no-Mersenne más grande conocido hasta ser superado en 2023, ^[⁵^] y es el número Colbert más grande . El segundo primo Proth conocido más grande es 202705 × 2 ^21320516 + 1, descubierto por PrimeGrid. ^[⁶^]

Prueba

La demostración de este teorema utiliza el criterio de primalidad de Pocklington-Lehmer . Es un caso particular relativamente sencillo demostrar el teorema de Proth a partir de él. Además, guarda un gran parecido con la demostración del criterio de Pépin . La demostración se encuentra en la página 52 de ^{[ 1 ] .}

Generalización

Cuando k = n , el número de Proth toma la forma p = n²n + 1. Si relajamos la condición que exige que ^k ( o n ) sea impar, estos se conocen como números de Cullen , con primos de Cullen correspondientes . Aunque la prueba de Proth funciona cuando n es impar, los números de Cullen tienen sus propias pruebas de primalidad para cualquier n .

Además, las pruebas de primalidad de Cullen pueden generalizarse a números de la forma p = nc ⁿ + 1, para bases arbitrarias c .

Historia

François Proth (1852–1879) publicó el teorema en 1878. ^{[ 7 ]}^{[ 8 ]}

Véase también

Prueba de Pépin (el caso especial k = 1, donde se elige a = 3)
Número de Sierpiński

Referencias

^ Paulo Ribenboim (1996) . El nuevo libro de registros de números primos . Nueva York, Nueva York: Springer. pag. 52 . ISBN 0-387-94457-5.
↑ Hans Riesel (1994). Números primos y métodos informáticos para la factorización (2.ª ed.). Boston, MA: Birkhauser. p . 104. ISBN 3-7643-3743-5.
↑ "PrimePage Primes: Los veinte primeros" . t5k.org . Consultado el 29 de junio de 2026 .
↑ "¡Se ha descubierto el récord mundial del número Colbert! "
↑ "PrimePage Primes: los primos más grandes conocidos" . t5k.org . Consultado el 29 de junio de 2026 .
↑ Caldwell, Chris K. "Los veinte primeros: los primos más grandes conocidos" .
↑ François Proth (1878). "Teoremas sobre los nombres premiers". Cuentas rendus de la Academia de Ciencias de París . 87 : 926.
↑ Leonard Eugene Dickson (1966). Historia de la teoría de los números . Vol. 1. Nueva York, NY: Chelsea. pág. 92.

Enlaces externos

Weisstein, Eric W. "Teorema de Proth" . MathWorld .

[:0-1] Paulo Ribenboim (1996) . El nuevo libro de registros de números primos . Nueva York, Nueva York: Springer. pag. 52 . ISBN 0-387-94457-5.

[2] Hans Riesel (1994). Números primos y métodos informáticos para la factorización (2.ª ed.). Boston, MA: Birkhauser. p . 104. ISBN 3-7643-3743-5.

[3] "PrimePage Primes: Los veinte primeros" . t5k.org . Consultado el 29 de junio de 2026 .

[4] "¡Se ha descubierto el récord mundial del número Colbert! "

[5] "PrimePage Primes: los primos más grandes conocidos" . t5k.org . Consultado el 29 de junio de 2026 .

[6] Caldwell, Chris K. "Los veinte primeros: los primos más grandes conocidos" .

[7] François Proth (1878). "Teoremas sobre los nombres premiers". Cuentas rendus de la Academia de Ciencias de París . 87 : 926.

[8] Leonard Eugene Dickson (1966). Historia de la teoría de los números . Vol. 1. Nueva York, NY: Chelsea. pág. 92.

[ 2 ]

[ 3 ]

[

[

[

[ 7 ]

[ 8 ]