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
- 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]
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
- [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".
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]
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 encontrado 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 tercer primo no Mersenne más grande conocido . [9]
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 primos y al problema de Sierpinski extendido han producido varios números más.
Dado que los divisores de números de Fermat siempre tienen la forma , se acostumbra determinar si un nuevo primo de Proth divide un número de Fermat. [10]
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 )
- 27121 Búsqueda de primos (búsqueda de primos de la forma y )
- Búsqueda de primos de Cullen (búsqueda de primos de la forma )
- Problema de Sierpinski (y sus generalizaciones primos y extendidas): búsqueda de primos de la forma donde k está en esta lista:
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 200 ) se han utilizado para construir escaleras de primos, secuencias de números primos tales que cada término está "cerca" (dentro de aproximadamente 10 11 ) 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 30 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 286 + 1 se ha utilizado de esta manera. [21]
Como los primos de Proth tienen representaciones binarias simples , también se han utilizado en reducciones modulares rápidas sin necesidad de cálculo previo, por ejemplo, por Microsoft . [22]
Referencias
- ^ ab 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
- ^ abc Sze, Tsz-Wo (2008). "Demostración de primalidad determinista en números de Proth". arXiv : 0812.2596 [math.NT].
- ^ de Weisstein, Eric W. "Proth Prime". mathworld.wolfram.com . Consultado el 6 de diciembre de 2019 .
- ^ Weisstein, Eric W. "Número de Proth". mathworld.wolfram.com . Consultado el 7 de diciembre de 2019 .
- ^ Weisstein, Eric W. "Teorema de Proth". MathWorld .
- ^ 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
- ^ Caldwell, Chris. "Los veinte mejores: Proth". Las páginas principales .
- ^ Van Zimmerman (30 de noviembre de 2016) [9 de noviembre de 2016]. "¡Se descubre el número de Colbert récord mundial!". PrimeGrid .
- ^ Caldwell, Chris. "Los veinte números primos más grandes conocidos". The Prime Pages .
- ^ "El glosario de primos: divisor de Fermat". primes.utm.edu . Consultado el 14 de noviembre de 2021 .
- ^ abcdefghijk Caldwell, Chris K. "Los veinte mejores: Proth". Los veinte mejores . Consultado el 6 de diciembre de 2019 .
- ^ ab Goetz, Michael (27 de febrero de 2018). "Seventeen or Bust". PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Búsqueda de Prime del problema de Sierpinski extendido de PrimeGrid" (PDF) . primegrid.com . PrimeGrid . Consultado el 28 de diciembre de 2021 .
- ^ abcdef «Nuevos factores GFN». www.prothsearch.com . Consultado el 14 de noviembre de 2021 .
- ^ "Descubrimiento oficial del número primo 168451×219375200+1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Estado de la factorización de Fermat". www.prothsearch.com . Consultado el 14 de noviembre de 2021 .
- ^ "Descubrimiento oficial del número primo 99739×214019102+1" (PDF) . PrimeGrid . 24 de diciembre de 2019 . Consultado el 14 de noviembre de 2021 .
- ^ Helfgott, HA; Platt, David J. (2013). "Verificación numérica de la conjetura ternaria de Goldbach hasta 8.875e30". arXiv : 1305.3062 [math.NT].
- ^ Helfgott, Harald A. (2013). "La conjetura ternaria de Goldbach es verdadera". arXiv : 1312.7748 [math.NT].
- ^ "Harald Andrés Helfgott". Alexander von Humboldt-Professur . Consultado el 8 de diciembre de 2019 .
- ^ 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 logaritmos discretos y de Diffie-Hellman" (PDF) . Asociación Internacional de Investigación Criptológica : 1–3.
- ^ Acar, Tolga; Shumow, Dan (2010). "Reducción modular sin cálculo previo para módulos especiales" (PDF) . Microsoft Research .