Número primo de Sophie Germain
De Wikipedia, la enciclopedia libre
En teoría de números, un número primo p es un primo de Sophie Germain si 2p + 1 también es primo. El número 2p + 1 asociado con un número primo de Sophie Germain se denomina número primo seguro. Por ejemplo, 11 es un primo de Sophie Germain y 2 × 11 + 1 = 23 es su primo seguro asociado. Los números primos de Sophie Germain llevan el nombre de la matemática francesa Sophie Germain (1776-1831), quien los usó en sus investigaciones sobre el último teorema de Fermat.[1] Los números primos de Sophie Germain y los números primos seguros tienen aplicaciones en criptografía asimétrica y en pruebas de primalidad. Se ha conjeturado que hay infinitos primos de Sophie Germain, pero sigue sin probarse.
Los primeros números primos de Sophie Germain (los menores de 1000) son
- 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, ... A005384
Por lo tanto, los primeros primos seguros son
- 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, ... A005385
En criptografía se requieren números primos de Sophie Germain mucho más grandes como 1.846.389.521.368 + 11600.
Dos proyectos de computación distribuida, PrimeGrid y Twin Prime Search, incluyen búsquedas de grandes números primos de Sophie Germain. Algunos de los primos de Sophie Germain más grandes conocidos se dan en la siguiente tabla.[2]
| Valor | Número de dígitos | Fecha del descubrimiento | Descubridor |
|---|---|---|---|
| 2618163402417 × 21290000 − 1 | 388.342 | febrero de 2016 | Dr. James Scott Brown en una búsqueda distribuida PrimeGrid utilizando los programas TwinGen y el LLR[3] |
| 18543637900515 × 2666667 − 1 | 200.701 | abril de 2012 | Philipp Bliedung en una búsqueda distribuida PrimeGrid utilizando los programas TwinGen y el LLR[4] |
| 183027 × 2265440 − 1 | 79.911 | marzo de 2010 | Tom Wu usando LLR[5] |
| 648621027630345 × 2253824 − 1 y 620366307356565 × 2253824 − 1 | 76.424 | noviembre de 2009 | Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza and Antal Járai[6][7] |
| 1068669447 × 2211088 − 1 | 63.553 | mayo de 2020 | Michael Kwok[8] |
| 99064503957 × 2200008 − 1 | 60.220 | abril de 2016 | S. Urushihata[9] |
| 607095 × 2176311 − 1 | 53.081 | septiembre de 2009 | Tom Wu[10] |
| 48047305725 × 2172403 − 1 | 51.910 | enero de 2007 | David Underbakke utilizando TwinGen y LLR[11] |
| 137211941292195 × 2171960 − 1 | 51.780 | mayo de 2006 | Járai et al.[12] |
El 2 de diciembre de 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé y Paul Zimmermann anunciaron el cálculo de un módulo de logaritmo discreto de número primo de 240 dígitos (795 bits) RSA-240 + 49204 (el primer número primo seguro anterior era RSA-240) utilizando un algoritmo de criba general del cuerpo de números; véase récords en logaritmos discretos.
No existe una prueba de primalidad especial para los primos seguros como la que existe para los números de Fermat y los primos de Mersenne. Sin embargo, el criterio de Pocklington puede usarse para probar la primalidad de 2p + 1 una vez que se ha probado la primalidad de p.
Así como todos los términos excepto el último de una cadena de Cunningham del primer tipo son primos de Sophie Germain, todos los términos excepto el primero de dicha cadena son primos seguros. Los primos seguros terminados en 7, es decir, de la forma 10n + 7, son los últimos términos de dichas cadenas cuando se presentan, ya que 2(10n + 7) + 1 = 20n + 15 es divisible por 5.
Si un primo seguro q es congruente a 7 módulo 8, entonces es un divisor de un número primo de Mersenne con su primo de Sophie Germain correspondiente como exponente.
Si q > 7 es un primo seguro, entonces q divide a 3(q−1)/2 - 1. Esto se deriva del hecho de que 3 es un residuo cuadrático mod q.
Restricciones modulares
Con la excepción de 7, un primo seguro q tiene la forma 6k − 1 o, de manera equivalente, q ≡ 5 (módulo 6) como p > 3. De manera similar, con la excepción de 5, un primo seguro q tiene la forma 4k + 1 o, de manera equivalente, q ≡ 3 (mod 4), un hecho trivialmente cierto ya que (q − 1) / 2 debe evaluarse como un número natural impar. Combinando ambas formas mediante el mcm(6, 4) se determina que un primo seguro q > 7 también debe ser de la forma 12k - 1 o, de manera equivalente, q ≡ 11 (mod 12). De ello se deduce que 3 (también 12) es un residuo cuadrático módulo q para cualquier primo seguro q > 7. (Así, 12 no es una raíz primitiva de ningún primo seguro q > 7, y los únicos números primos seguros que también son primos largos en sistema duodecimal son 5 y 7).
Si p es un primo de Sophie Germain mayor que 3, entonces p debe ser congruente con 2 mod 3. Porque si no, sería congruente con 1 mod 3 y 2p + 1 sería congruente con 3 mod 3, imposible para un número primo.[13] Se aplican restricciones similares para módulos primos más grandes y son la base para la elección del "factor de corrección" 2C en la estimación de Hardy-Littlewood sobre la densidad de los números primos de Sophie Germain.[14]
Si un primo de Sophie Germain p es congruente a 3 (mod 4) ((sucesión A002515 en OEIS), primos lucasianos), entonces su primo seguro coincidente 2p + 1 será un divisor del primo de Mersenne 2p - 1. Históricamente, este resultado de Leonhard Euler fue el primer criterio conocido para que un número de Mersenne con un índice primo fuera compuesto.[15] Se puede usar para generar los números de Mersenne más grandes (con índices primos) que se sabe que son compuestos.[16]
Problemas no resueltos de la matemática: ¿Hay infinitos números primos de Sophie Germain?
Se ha conjeturado que hay infinitos números primos de Sophie Germain, pero esta proposición todavía no ha sido probada.[14] Varias otras conjeturas famosas en teoría de números generalizan este cuestión y la conjetura de los primos gemelos, como la conjetura de Dickson, la hipótesis H de Schinzel y la conjetura de Bateman-Horn.
Una estimación heurística para el número de primos de Sophie Germain menores que n es[14]
donde
es la constante prima gemela de Hardy-Littlewood. Para n = 104, esta estimación predice 156 números primos de Sophie Germain, lo que tiene un error del 20 % en comparación con el valor exacto de 190. Para n = 107, la estimación predice 50822, que todavía tiene un 10 % de déficit sobre el valor exacto de 56032. La forma de esta estimación se debe a Godfrey Harold Hardy y John Edensor Littlewood, quienes aplicaron una estimación similar a los primos gemelos.[17]
Una secuencia (p, 2p + 1, 2(2p + 1) + 1, ...) en la que todos los números son primos se llama cadena de Cunningham de primera clase. Cada término de tal secuencia, excepto el último, es un primo de Sophie Germain, y cada término, excepto el primero, es un primo seguro. Ampliando la conjetura de que existen infinitos números primos de Sophie Germain, también se ha conjeturado que existen cadenas de Cunningham arbitrariamente largas,[18] aunque se sabe que las cadenas infinitas son imposibles.[19]
Un número primo q es un número primo fuerte si tanto q + 1 como q − 1 tienen algunos factores primos grandes (alrededor de 500 dígitos). Para un primo seguro q= 2p + 1, el número q − 1 naturalmente tiene un factor primo grande, a saber, p, por lo que un primo seguro q cumple parte de los criterios para ser un primo fuerte. Los tiempos de ejecución de algunos métodos de factorizar un número con q como factor primo dependen en parte del tamaño de los factores primos de q − 1. Esto es cierto, por ejemplo, para el método p − 1.
Criptografía
Los números primos seguros también son importantes en criptografía debido a su uso en técnicas basadas en logaritmos discretos como el cambio de clave de Diffie-Hellman. Si 2p + 1 es un primo seguro, el grupo multiplicativo de los enteros módulo 2p + 1 tiene un subgrupo de orden primo grande. Por lo general, este subgrupo de orden primo es deseable, y la razón para usar primos seguros es que el módulo sea lo más pequeño posible en relación con p.
Un número primo p = 2q + 1 se llama primo seguro si q es primo. Por lo tanto, p = 2q + 1 es un primo seguro si y solo si q es un primo de Sophie Germain, por lo que encontrar primos seguros y encontrar los números primos de Sophie Germain son equivalentes en dificultad computacional. La noción de un primo seguro puede reforzarse a un primo fuerte, para el cual tanto p − 1 como p + 1 tienen factores primos grandes. Los números primos seguros y fuertes fueron útiles como factores de claves secretas en el sistema criptográfico RSA, porque evitan que el sistema se rompa con algunos algoritmos de factorización como el algoritmo p − 1 de Pollard. Sin embargo, con la tecnología de factorización actual, la ventaja de usar números primos fuertes y seguros parece ser insignificante.[20]
También se aplican problemas similares en otros criptosistemas, incluidos el sistema de cambio de clave de Diffie-Hellman y sistemas similares que dependen de la seguridad de un logaritmo discreto en lugar de la factorización de enteros.[21] Por esta razón, los protocolos de generación de claves para estos métodos a menudo se basan en algoritmos eficientes para generar números primos fuertes, que a su vez se basan en la conjetura de que estos números primos tienen una densidad suficientemente alta.[22]
En el Modo Contador de Sophie Germain se propuso usar la aritmética en el cuerpo finito de orden igual al número primo de Sophie Germain 2128 + 12451, para contrarrestar las debilidades del Modo Galois/Contador usando el campo finito binario GF(2128). Sin embargo, se ha demostrado que SGCM es vulnerable a muchos de los mismos ataques criptográficos que GCM.[23]
Prueba de primalidad
En la primera versión del documento Test de primalidad AKS, se utilizó una conjetura sobre los números primos de Sophie Germain para reducir la complejidad del peor de los casos de O(log12n) a O(log6n). Se muestra que una versión posterior del documento tiene una complejidad de tiempo O(log7.5n) que también se puede reducir a O(log6n) usando la conjetura.[24] Se ha demostrado que las variantes posteriores del Test AKS tienen una complejidad de O(log6n) sin conjeturas ni uso de números primos de Sophie Germain.
Generación de números pseudoaleatorios
Los primos seguros que obedecen a ciertas congruencias se pueden usar para generar números pseudoaleatorios de uso en el método de Montecarlo.
De manera similar, los números primos de Sophie Germain pueden usarse en la generación de números pseudoaleatorios. La expansión decimal de 1/q producirá un flujo de q − 1 dígitos pseudoaleatorios, si q es el primo seguro de un primo de Sophie Germain p, con p congruente con 3, 9 u 11 módulo 20.[25] Así, los números primos "propios" q son 7, 23, 47, 59, 167, 179, etc. ((sucesión A000353 en OEIS)) (correspondiente a p = 3, 11, 23, 29, 83, 89, etc.) ((sucesión A000355 en OEIS)). El resultado es una secuencia de longitud q − 1 dígitos (incluidos los ceros iniciales). Entonces, por ejemplo, usar q= 23 genera los dígitos pseudoaleatorios 0, 4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2 , 1, 7, 3, 9, 1, 3. Se debe tener en cuenta que estos dígitos no son apropiados para fines criptográficos, ya que el valor de cada uno puede deducirse de su predecesor en el flujo de dígitos.
Los primos de Sophie Germain se mencionan en la obra de teatro La Prueba[26] y la película del mismo nombre.[27]
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
