Un número de Proth es un número natural N de la formadonde k y n son positivos enteros , k es impar y. Un primo de Proth es un número de Proth que es primo . Llevan el nombre del matemático francés François Proth . [1] Los primeros primos de Proth son
Lleva el nombre de | François Proth |
---|---|
Año de publicación | 1878 |
Autor de la publicación | Proth, Francois |
No. de términos conocidos | Más de 1.500 millones por debajo de 2 70 |
Conjeturaba que no. de términos | Infinito |
Subsecuencia de | Proth números, números primos |
Fórmula | k × 2 n + 1 |
Primeros términos | 3, 5, 13, 17, 41, 97, 113 |
Término más grande conocido | 10223 × 2 31172165 + 1 (a diciembre de 2019) |
Índice OEIS |
|
- 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857 ( OEIS : A080076 ).
La primacía de los números de Proth se puede probar más fácilmente que muchos otros números de magnitud similar.
Definición
Un número de Proth toma la forma donde k y n son números enteros positivos, es extraño y . Un primo de Proth es un número de Proth que es primo. [1] [2]
Sin la condición de que , todos los enteros impares mayores que 1 serían números de Proth. [3]
Prueba de primordialidad
La primordialidad 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 número entero para cual
Este teorema se puede utilizar como una prueba probabilística de primalidad, comprobando muchas elecciones aleatorias de ya sea Si esto no se mantiene durante varios , entonces es muy probable que el número es 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 reporta un número compuesto como " probablemente primo " pero puede reportar un número primo como "posiblemente compuesto".
En 2008, Sze creó un algoritmo determinista que se ejecuta como máximotiempo, donde Õ es la notación O suave . Para búsquedas típicas de primos de Proth, normalmente es fijo (por ejemplo, 321 Prime Search o Problema de Sierpinski) o de orden (por ejemplo, búsqueda principal de Cullen ). En estos casos, el algoritmo se ejecuta como máximo, o tiempo para todos . También hay un algoritmo que se ejecuta enhora. [1] [5]
Grandes números primos
A partir de 2019[actualizar], la prima de Proth más grande conocida es . Tiene 9.383.761 dígitos de longitud. [6] Fue encontrado por Szabolcs Peter en el proyecto de computación distribuida PrimeGrid que lo anunció el 6 de noviembre de 2016. [7] También es el principal no Mersenne más grande conocido . [8]
El proyecto Diecisiete o Busto , en busca de primos de Proth con un ciertopara demostrar que 78557 es el número de Sierpinski más pequeño ( problema de Sierpinski ), ha encontrado 11 números primos de Proth grandes en 2007, de los cuales 5 son megaprimes . Resoluciones similares al problema principal de Sierpiński y al problema extendido de Sierpiński han arrojado varios números más.
A diciembre de 2019, PrimeGrid es el proyecto informático líder para la búsqueda de primos de Proth. Sus principales proyectos incluyen:
- búsqueda general de Proth prime
- 321 Prime Search (buscando números primos de la forma , también llamados primos Thabit de segundo tipo )
- 27121 Prime Search (búsqueda de números primos de la forma y )
- Búsqueda de primos de Cullen (búsqueda de primos de la forma )
- Problema de Sierpinski (y sus generalizaciones primarias 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, 202705, 209611, 222113, 225931, 227723, 229673, 237019, 238411}
A diciembre de 2019, los números primos de Proth más grandes descubiertos son: [9]
rango | principal | digitos | Cuándo | Cullen prime ? | Descubridor (Proyecto) | Referencias |
---|---|---|---|---|---|---|
1 | 10223 · 2 31172165 + 1 | 9383761 | 31 de octubre de 2016 | Szabolcs Péter (Problema de Sierpinski) | [10] | |
2 | 168451 · 2 19375200 + 1 | 5832522 | 17 de sep. De 2017 | Ben Maloney (Problema de Prime Sierpinski) | [11] | |
3 | 19249 · 2 13018586 + 1 | 3918990 | 26 de marzo de 2007 | Konstantin Agafonov (diecisiete o busto) | [10] | |
4 | 193997 · 2 11452891 + 1 | 3447670 | 3 de abril de 2018 | Tom Greer (Problema extendido de Sierpinski) | [12] | |
5 | 3 · 2 10829346 + 1 | 3259959 | 14 de ene. De 2014 | Sai Yik Tang (321 Prime Search) | [13] | |
6 | 27653 · 2 9167433 + 1 | 2759677 | 8 de junio de 2005 | Derek Gordon (diecisiete o busto) | [10] | |
7 | 90527 · 2 9162167 + 1 | 2758093 | 30 de junio de 2010 | Desconocido (Problema de Prime Sierpinski) | [14] [15] | |
8 | 28433 · 2 7830457 + 1 | 2357207 | 30 de diciembre de 2004 | Team Prime Rib (diecisiete o busto) | [10] | |
9 | 161041 · 2 7107964 + 1 | 2139716 | 6 de enero de 2015 | Martin Vanc (Problema extendido de Sierpinski) | [dieciséis] | |
10 | 27 · 2 7046834 + 1 | 2121310 | 11 de octubre de 2018 | Andrew M. Farrow (Búsqueda Prime 27121) | [17] | |
11 | 3 · 2 7033641 + 1 | 2117338 | 21 de febrero de 2011 | Michael Herder (321 Prime Search) | [18] | |
12 | 33661 · 2 7031232 + 1 | 2116617 | 17 de octubre de 2007 | Sturle Sunde (diecisiete o busto) | [10] | |
13 | 6679881 · 2 6679881 + 1 | 2010852 | 25 de julio de 2009 | sí | Magnus Bergman (Búsqueda de Cullen Prime) | [19] |
14 | 1582137 · 2 6328550 + 1 | 1905090 | 20 de abril de 2009 | sí | Dennis R. Gesker (Búsqueda de Cullen Prime) | [20] |
15 | 7 · 2 5775996 + 1 | 1738749 | 2 de noviembre de 2012 | Martyn Elvy (Búsqueda de Proth Prime) | [21] | |
dieciséis | 9 · 2 5642513 + 1 | 1698567 | 29 de noviembre de 2013 | Serge Batalov | [22] [23] [nb 1] | |
17 | 258317 · 2 5450519 + 1 | 1640776 | 28 de julio de 2008 | Scott Gilvey (Problema de Prime Sierpinski) | [14] [24] | |
18 | 27 · 2 5213635 + 1 | 1569462 | 9 de marzo de 2015 | Hiroyuki Okazaki (27121 Prime Search) | [25] | |
19 | 39 · 2 5119458 + 1 | 1541113 | 23 de noviembre de 2019 | Scott Brown (búsqueda principal de Fermat Divisor) | [26] | |
20 | 3 · 2 5082306 + 1 | 1529928 | 3 de abril de 2009 | Andy Brady (321 Prime Search) | [27] |
- ↑ No está claro a qué proyecto se unió Batalov para encontrar el mejor; sin embargo, se ha comprobado que no utilizó PrimeGrid.
Usos
Los números primos de Proth pequeños (menos de 10 200 ) se han utilizado en la construcción de escaleras de números 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 principales construidas a partir de primos Proth. [28] (La conjetura fue probada más tarde por Harald Helfgott . [29] [30] [se necesita una mejor fuente ] )
Además, los números primos de Proth pueden optimizar la reducción del den Boer entre el problema de Diffie-Hellman y el problema de logaritmo discreto . El número primo 55 × 2 286 + 1 se ha utilizado de esta forma. [31]
Dado que los números primos de Proth tienen representaciones binarias simples , también se han utilizado en la reducción modular rápida sin la necesidad de un cálculo previo, por ejemplo, por Microsoft . [32]
Referencias
- ↑ a b c Sze, Tsz-Wo (2008). "Demostración de la primacía determinista en números de protuberancias". arXiv : 0812.2596 [ matemáticas.NT ].
- ^ a b Weisstein, Eric W. "Proth Prime" . mathworld.wolfram.com . Consultado el 6 de diciembre de 2019 .
- ^ Weisstein, Eric W. "Proth Number" . 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.), "On Primes Recognizable in Deterministic Polynomial Time", The Mathematics of Paul Erdős I , Springer New York, pp. 159-186, doi : 10.1007 / 978-1-4614-7258-2_12 , ISBN 978-1-4614-7258-2
- ^ Caldwell, Chris. "Los veinte primeros: Proth" . Las Prime Pages .
- ^ Van Zimmerman (30 de noviembre de 2016) [9 de noviembre de 2016]. "¡Descubierto el número de Colbert récord mundial!" . PrimeGrid .
- ^ Caldwell, Chris. "Los veinte primeros: mayores premios conocidos" . Las Prime Pages .
- ^ Caldwell, Chris K. "Los veinte primeros: Proth" . Los veinte primeros . Consultado el 6 de diciembre de 2019 .
- ^ a b c d e Goetz, Michael (27 de febrero de 2018). "Diecisiete o busto" . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 168451 × 2 19375200 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 193997 × 2 11452891 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 3 × 2 10829346 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ a b "El problema de Prime Sierpinski" . mersenneforum.org . 18 de junio de 2004 . Consultado el 7 de diciembre de 2019 .
- ^ Caldwell, Chris K. "Patrice Salah" . Las Prime Pages . Consultado el 9 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 161041 × 2 7107964 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 27 × 2 7046834 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 3 × 2 7033641 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 6679881 × 2 6679881 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 6328548 × 2 6328548 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 7 × 2 5775996 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "Sugerencia: un proyecto de Proth 5-7-9" . PrimeGrid . El 25 de julio de 2019 . Consultado el 8 de diciembre de 2019 .
- ^ "9 · 2 5642513 +1 (Otro de los recursos de Prime Pages)" . La base de datos Prime . 1 de abril de 2014 . Consultado el 9 de diciembre de 2019 .
- ^ Caldwell, Chris K. "Scott Gilvey" . Las Prime Pages . Consultado el 9 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 27 × 2 5213635 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ "PrimeGrid Primes" . PrimeGrid . Consultado el 7 de diciembre de 2019 .
- ^ "Descubrimiento oficial del número primo 3 × 2 5082306 +1" (PDF) . PrimeGrid . Consultado el 6 de diciembre de 2019 .
- ^ Helfgott, HA; Platt, David J. (2013). "Verificación numérica de la conjetura ternaria de Goldbach hasta 8.875e30". arXiv : 1305.3062 [ matemáticas.NT ].
- ^ Helfgott, Harald A. (2013). "La conjetura ternaria de Goldbach es cierta". arXiv : 1312.7748 [ matemáticas.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 primario que casi optimizan la reducción de den Boer entre registros Diffie-Hellman y discretos" (PDF) . Asociación Internacional para la Investigación Criptológica : 1-3.
- ^ Acar, Tolga; Shumow, Dan (2010). "Reducción modular sin precálculo para módulos especiales" (PDF) . Investigación de Microsoft .