Proth principal

Número primo de la forma k*(2^n)+1

Un número de Proth es un número natural N de la forma donde k y n son números enteros positivos , k es impar y . Un primo de Proth es un número de Proth que es primo . Reciben su nombre del matemático francés François Proth . ^[2] Los primeros primos de Proth son ${\displaystyle N=k\times 2^{n}+1}$ ${\displaystyle 2^{n}>k}$

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 7, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857 ( OEIS : A080076 ).

Aún no se sabe si existe un número infinito de primos de Proth. En 2022 se demostró que la suma recíproca de los primos de Proth converge a un número real cercano a 0,747392479, sustancialmente menor que el valor de 1,093322456 para la suma recíproca de los números de Proth. ^[1]

La primalidad de los números de Proth se puede probar más fácilmente que la de muchos otros números de magnitud similar.

Definición

Un número de Proth tiene la forma donde k y n son números enteros positivos, es impar y . Un primo de Proth es un número de Proth que es primo. ^{[2] [3]} Sin la condición de que , todos los números enteros impares mayores que 1 serían números de Proth. ^[4] ${\displaystyle N=k2^{n}+1}$ ${\displaystyle k}$ ${\displaystyle 2^{n}>k}$ ${\displaystyle 2^{n}>k}$

Prueba de primalidad

La primalidad de un número de Proth se puede probar con el teorema de Proth , que establece que un número de Proth es primo si y solo si existe un entero para el cual ${\displaystyle p}$ ${\displaystyle a}$

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$^{[3] [5]}

Este teorema se puede utilizar como una prueba probabilística de primalidad, verificando para muchas elecciones aleatorias si Si esto no se cumple para varias elecciones aleatorias , entonces es muy probable que el número sea compuesto . ^{[ cita requerida ]} Esta prueba es un algoritmo de Las Vegas : nunca devuelve un falso positivo pero puede devolver un falso negativo ; en otras palabras, nunca informa un número compuesto como " probablemente primo ", pero puede informar un número primo como "posiblemente compuesto". ${\displaystyle a}$ ${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$ ${\displaystyle a}$ ${\displaystyle p}$

En 2008, Sze creó un algoritmo determinista que se ejecuta en como máximo tiempo, donde Õ es la notación O suave . Para búsquedas típicas de primos de Proth, normalmente es fijo (por ejemplo, la búsqueda de primos 321 o el problema de Sierpinski) o de orden (por ejemplo,  la búsqueda de primos de Cullen ). En estos casos, el algoritmo se ejecuta en como máximo , o tiempo para todos los . También hay un algoritmo que se ejecuta en tiempo. ^{[2] [6]} ${\displaystyle {\tilde {O}}((k\log k+\log N)(\log N)^{2})}$ ${\displaystyle k}$ ${\displaystyle O(\log N)}$ ${\displaystyle {\tilde {O}}((\log N)^{3})}$ ${\displaystyle O((\log N)^{3+\epsilon })}$ ${\displaystyle \epsilon >0}$ ${\displaystyle {\tilde {O}}((\log N)^{24/7})}$

Los números de Fermat son un caso especial de los números de Proth, donde k = 1. En tal escenario, la prueba de Pépin demuestra que solo es necesario comprobar la base a = 3 para verificar o refutar de manera determinista la primalidad de un número de Fermat.

Primos grandes

A partir de 2022 ^[actualizar], el primo de Proth más grande conocido es . Tiene 9.383.761 dígitos de longitud. ^[7] Fue descubierto por Szabolcs Peter en el proyecto de computación voluntaria PrimeGrid que lo anunció el 6 de noviembre de 2016. ^[8] También es el segundo primo no Mersenne más grande conocido . ^[9] ${\displaystyle 10223\times 2^{31172165}+1}$

El proyecto Seventeen or Bust , que buscaba primos de Proth con una certeza tal que demostrara que 78557 es el número de Sierpinski más pequeño ( problema de Sierpinski ), encontró 11 primos de Proth grandes hasta 2007. Resoluciones similares al problema de Sierpinski de los primos y al problema de Sierpinski ampliado han producido varios números más. ${\displaystyle t}$

Dado que los divisores de los números de Fermat siempre tienen la forma , se acostumbra determinar si un nuevo primo de Proth divide un número de Fermat. ^[10] ${\displaystyle F_{n}=2^{2^{n}}+1}$ ${\displaystyle k\times 2^{n+2}+1}$

A partir de julio de 2023, PrimeGrid es el proyecto informático líder para la búsqueda de números primos de Proth. Entre sus principales proyectos se incluyen:

• Búsqueda general de Proth Prime
• 321 Búsqueda de primos (búsqueda de primos de la forma , también llamados primos de Thabit del segundo tipo ) ${\displaystyle 3\times 2^{n}+1}$
• 27121 Búsqueda de primos (búsqueda de primos de la forma y ) ${\displaystyle 27\times 2^{n}+1}$ ${\displaystyle 121\times 2^{n}+1}$
• Búsqueda de primos de Cullen (búsqueda de primos de la forma ) ${\displaystyle n\times 2^{n}+1}$
• Problema de Sierpinski (y sus generalizaciones primos y extendidas): búsqueda de primos de la forma donde k está en esta lista: ${\displaystyle k\times 2^{n}+1}$

k ∈ {21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 209611, 222113, 225931, 227723, 229673, 237019, 238411}

A partir de junio de 2023, los primos de Proth más grandes descubiertos son: ^[11]

Usos

Los primos de Proth pequeños (menores de 10 ²⁰⁰ ) se han utilizado para construir escaleras de primos, secuencias de números primos tales que cada término está "cerca" (dentro de aproximadamente 10 ¹¹ ) del anterior. Estas escaleras se han utilizado para verificar empíricamente conjeturas relacionadas con los primos . Por ejemplo, la conjetura débil de Goldbach se verificó en 2008 hasta 8,875 × 10 ³⁰ utilizando escaleras de primos construidas a partir de primos de Proth. ^[18] (La conjetura fue demostrada posteriormente por Harald Helfgott . ^{[19] [20] [ se necesita una mejor fuente ]} )

Además, los primos de Proth pueden optimizar la reducción de Den Boer entre el problema de Diffie-Hellman y el problema del logaritmo discreto . El número primo 55 × 2 ²⁸⁶  + 1 se ha utilizado de esta manera. ^[21]

Como los primos de Proth tienen representaciones binarias simples , también se han utilizado en una reducción modular rápida sin necesidad de cálculo previo, por ejemplo, por Microsoft . ^[22]

Referencias

1. Borsos, Bertalán; Kovács, Atila; Tihanyi, Norbert (2022), "Límites superiores e inferiores ajustados para la suma recíproca de los primos de Proth", Ramanujan Journal , 59 , Springer: 181–198, doi : 10.1007/s11139-021-00536-2 , hdl : 10831/83020 , S2CID  246024152
2. Sze, Tsz-Wo (2008). "Demostración de primalidad determinista en números de Proth". arXiv : 0812.2596 [math.NT].
3. Weisstein, Eric W. "Proth Prime". mathworld.wolfram.com . Consultado el 6 de diciembre de 2019 .
4. Weisstein, Eric W. "Número de Proth". mathworld.wolfram.com . Consultado el 7 de diciembre de 2019 .
5. Weisstein, Eric W. "Teorema de Proth". MathWorld .
6. Konyagin, Sergei; Pomerance, Carl (2013), Graham, Ronald L.; Nešetřil, Jaroslav; Butler, Steve (eds.), "Sobre los primos reconocibles en tiempo polinomial determinista", The Mathematics of Paul Erdős I , Springer Nueva York, págs. 159–186, doi :10.1007/978-1-4614-7258-2_12, ISBN 978-1-4614-7258-2
7. Caldwell, Chris. "Los veinte mejores: Proth". Las páginas principales .
8. Van Zimmerman (30 de noviembre de 2016) [9 de noviembre de 2016]. "¡Se descubre el número de Colbert récord mundial!". PrimeGrid .
9. Caldwell, Chris. "Los veinte números primos más grandes conocidos". The Prime Pages .
10. "El glosario de primos: divisor de Fermat". primes.utm.edu . Consultado el 14 de noviembre de 2021 .
11. Caldwell, Chris K. "Los veinte mejores: Proth". Los veinte mejores . Consultado el 6 de diciembre de 2019 .
12. Goetz, Michael (27 de febrero de 2018). "Seventeen or Bust". PrimeGrid . Consultado el 6 de diciembre de 2019 .
13. "Búsqueda de Prime del problema de Sierpinski extendido de PrimeGrid" (PDF) . primegrid.com . PrimeGrid . Consultado el 28 de diciembre de 2021 .
14. «Nuevos factores GFN». www.prothsearch.com . Consultado el 14 de noviembre de 2021 .
15. "Descubrimiento oficial del número primo 168451×219375200+1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
16. "Estado de la factorización de Fermat". www.prothsearch.com . Consultado el 14 de noviembre de 2021 .
17. "Descubrimiento oficial del número primo 99739×214019102+1" (PDF) . PrimeGrid . 24 de diciembre de 2019 . Consultado el 14 de noviembre de 2021 .
18. Helfgott, HA; Platt, David J. (2013). "Verificación numérica de la conjetura ternaria de Goldbach hasta 8.875e30". arXiv : 1305.3062 [math.NT].
19. Helfgott, Harald A. (2013). "La conjetura ternaria de Goldbach es verdadera". arXiv : 1312.7748 [math.NT].
20. "Harald Andrés Helfgott". Alexander von Humboldt-Professur . Consultado el 8 de diciembre de 2019 .
21. Brown, Daniel RL (24 de febrero de 2015). "CM55: curvas elípticas especiales de campo primo que casi optimizan la reducción de Den Boer entre Diffie-Hellman y logaritmos discretos" (PDF) . Asociación Internacional de Investigación Criptológica : 1–3.
22. Acar, Tolga; Shumow, Dan (2010). "Reducción modular sin cálculo previo para módulos especiales" (PDF) . Microsoft Research .