Proth prime - Proth prime

Proth prime

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

Un número Proth es un número natural N de la forma donde 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 . Los primeros primos de Proth son ${\ Displaystyle N = k \ cdot 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, 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

Número A Proth toma 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. ${\ Displaystyle N = k2 ^ {n} +1}$${\ Displaystyle k}$${\ Displaystyle 2 ^ {n}> k}$

Sin la condición de que , todos los enteros impares mayores que 1 serían números de Proth. ${\ Displaystyle 2 ^ {n}> k}$

Prueba de primordialidad

La primacía 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 el cual ${\ Displaystyle p}$${\ Displaystyle a}$

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

Este teorema se puede utilizar como una prueba probabilística de primalidad, comprobando muchas opciones aleatorias de si esto no se cumple para varias aleatorias , entonces es muy probable que el número sea compuesto . 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". ${\ 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 la mayor parte del tiempo, donde Õ es la notación Soft-O . 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 de primos de Cullen ). En estos casos, el algoritmo se ejecuta como máximo , o el tiempo para todos . También hay un algoritmo que se ejecuta en el tiempo. ${\ 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})}$

Grandes números primos

A partir de 2019, la prima de Proth más grande conocida es . Tiene 9.383.761 dígitos de longitud. Fue encontrado por Szabolcs Peter en el proyecto de computación distribuida PrimeGrid que lo anunció el 6 de noviembre de 2016. También es el principal no Mersenne más grande conocido . ${\ displaystyle 10223 \ cdot 2 ^ {31172165} +1}$

El proyecto Seventeen o Bust , que busca números primos de Proth con una certeza para 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. ${\ Displaystyle t}$

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 (búsqueda de primos de la forma , también llamados primos de Thabit del segundo tipo )${\ Displaystyle 3 \ times 2 ^ {n} +1}$
• 27121 Prime Search (buscando números 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 primarias 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, 202705, 209611, 222113, 225931, 227723, 229673, 237019, 238411}

A diciembre de 2019, los primos de Proth más grandes descubiertos son:

rango	principal	digitos	cuando	Cullen prime ?	Descubridor (Proyecto)	Referencias
1	10223 · 2 31172165 + 1	9383761	31 de octubre de 2016		Szabolcs Péter (Problema de Sierpinski)
2	168451 · 2 19375200 + 1	5832522	17 de sep. De 2017		Ben Maloney (Problema de Prime Sierpinski)
3	19249 · 2 13018586 + 1	3918990	26 de marzo de 2007		Konstantin Agafonov (diecisiete o busto)
4	193997 · 2 11452891 + 1	3447670	3 de abril de 2018		Tom Greer (Problema extendido de Sierpinski)
5	3 · 2 10829346 + 1	3259959	14 de ene. De 2014		Sai Yik Tang (321 Prime Search)
6	27653 · 2 9167433 + 1	2759677	8 de junio de 2005		Derek Gordon (diecisiete o busto)
7	90527 · 2 9162167 + 1	2758093	30 de junio de 2010		Desconocido (Problema de Prime Sierpinski)
8	28433 · 2 7830457 + 1	2357207	30 de diciembre de 2004		Team Prime Rib (diecisiete o busto)
9	161041 · 2 7107964 + 1	2139716	6 de enero de 2015		Martin Vanc (Problema extendido de Sierpinski)
10	27 · 2 7046834 + 1	2121310	11 de octubre de 2018		Andrew M. Farrow (Búsqueda Prime 27121)
11	3 · 2 7033641 + 1	2117338	21 de febrero de 2011		Michael Herder (321 Prime Search)
12	33661 · 2 7031232 + 1	2116617	17 de octubre de 2007		Sturle Sunde (diecisiete o busto)
13	6679881 · 2 6679881 + 1	2010852	25 de julio de 2009	sí	Magnus Bergman (Búsqueda de Cullen Prime)
14	1582137 · 2 6328550 + 1	1905090	20 de abril de 2009		Dennis R. Gesker (Búsqueda de Cullen Prime)
15	7 · 2 5775996 + 1	1738749	2 de noviembre de 2012		Martyn Elvy (Búsqueda de Proth Prime)
dieciséis	9 · 2 5642513 + 1	1698567	29 de noviembre de 2013		Serge Batalov
17	258317 · 2 5450519 + 1	1640776	28 de julio de 2008		Scott Gilvey (Problema de Prime Sierpinski)
18	27 · 2 5213635 + 1	1569462	9 de marzo de 2015		Hiroyuki Okazaki (27121 Prime Search)
19	39 · 2 5119458 + 1	1541113	23 de noviembre de 2019		Scott Brown (búsqueda principal de Fermat Divisor)
20	3 · 2 5082306 + 1	1529928	3 de abril de 2009		Andy Brady (321 Prime Search)

Usos

Los números primos de Proth pequeños (menos de 10 ²⁰⁰ ) 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 ¹¹ ) 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 principales construidas a partir de primos Proth. (La conjetura fue probada más tarde por Harald Helfgott ).

Además, los 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 ²⁸⁶  + 1 se ha utilizado de esta forma.

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 .

Referencias