Proth principal

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}$$Estilo de visualización 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.

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]$Estilo de visualización N=k2^{n}+1}$${\estilo de visualización k}$$Estilo de visualización 2^{n}>k$$Estilo de visualización 2^{n}>k$

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 ${\estilo de visualización p}$${\estilo de visualización 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". ${\estilo de visualización a}$${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$${\estilo de visualización a}$${\estilo de visualización 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})}$${\estilo de visualización 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.

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. ${\estilo de visualización t}$

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]${\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]

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]