En teoría de números , un número primo p es un primo de Sophie Germain si 2 p + 1 también es primo. El número 2 p + 1 asociado con un primo de Sophie Germain se llama primo seguro . Por ejemplo, 11 es un primo de Sophie Germain y 2 × 11 + 1 = 23 es su primo seguro asociado. Los primos de Sophie Germain y los primos seguros tienen aplicaciones en criptografía de clave pública y pruebas de primalidad . Se ha conjeturado que hay infinitos primos de Sophie Germain, pero esto sigue sin demostrarse.
Los primos de Sophie Germain se llaman así por la matemática francesa Sophie Germain , quien los usó en sus investigaciones del Último Teorema de Fermat . [1] Un intento de Germain para probar el Último Teorema de Fermat fue dejar que p sea un número primo de la forma 8 k + 7 y dejar que n = p – 1. En este caso, es irresoluble. La prueba de Germain, sin embargo, quedó inconclusa. [2] [3] A través de sus intentos de resolver el Último Teorema de Fermat, Germain desarrolló un resultado ahora conocido como Teorema de Germain que establece que si p es un primo impar y 2 p + 1 también es primo, entonces p debe dividir a x , y o z. De lo contrario, . Este caso donde p no divide a x , y o z se llama primer caso. El trabajo de Sophie Germain fue el mayor progreso logrado en el último teorema de Fermat en ese momento. [2] El trabajo posterior de Kummer y otros siempre dividió el problema en primer y segundo caso.
Los primeros primos de Sophie Germain (aquellos menores que 1000) son
Por lo tanto, los primeros primos seguros son
En criptografía se requieren números primos de Sophie Germain mucho más grandes, como 1.846.389.521.368 + 11.600 .
Dos proyectos de computación distribuida, PrimeGrid y Twin Prime Search , incluyen búsquedas de números primos de Sophie Germain grandes. Algunos de los números primos de Sophie Germain más grandes conocidos se muestran en la siguiente tabla. [4]
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 logaritmo discreto módulo el primo de 240 dígitos (795 bits) RSA-240 + 49204 (el primer primo seguro por encima de RSA-240) utilizando un algoritmo de criba de campo numérico ; consulte Registros de logaritmos discretos .
No existe una prueba de primalidad especial para los números primos seguros, como sí la hay para los números primos de Fermat y los números primos de Mersenne . Sin embargo, el criterio de Pocklington se puede utilizar para demostrar la primalidad de 2 p + 1 una vez que se ha demostrado la primalidad de p .
Así como cada término excepto el último de una cadena de Cunningham de primera especie es un primo de Sophie Germain, así también cada término excepto el primero de dicha cadena es un primo seguro. Los primos seguros que terminan en 7, es decir, de la forma 10 n + 7, son los últimos términos de dichas cadenas cuando aparecen, ya que 2(10 n + 7) + 1 = 20 n + 15 es divisible por 5.
Para un primo seguro, cada residuo cuadrático no , excepto -1 (si el residuo no es [a] ), es una raíz primitiva . De ello se deduce que para un primo seguro, la raíz primitiva menos positiva es un número primo. [15]
Con excepción de 7, un primo seguro q es de la forma 6 k − 1 o, equivalentemente, q ≡ 5 ( mod 6) – como lo es p > 3. De manera similar, con excepción de 5, un primo seguro q es de la forma 4 k − 1 o, equivalentemente, q ≡ 3 (mod 4) – trivialmente cierto ya que ( q − 1) / 2 debe evaluarse como un número natural impar . Combinando ambas formas usando mcm (6, 4) determinamos que un primo seguro q > 7 también debe ser de la forma 12 k − 1 o, equivalentemente, q ≡ 11 (mod 12).
De ello se deduce que, para cualquier primo seguro q > 7:
Si p es un primo de Sophie Germain mayor que 3, entonces p debe ser congruente con 2 módulo 3. De lo contrario, sería congruente con 1 módulo 3 y 2 p + 1 sería congruente con 3 módulo 3, lo cual es imposible para un número primo. [16] Restricciones similares se aplican para módulos primos mayores, y son la base para la elección del "factor de corrección" 2 C en la estimación de Hardy–Littlewood sobre la densidad de los primos de Sophie Germain. [17]
Si un primo de Sophie Germain p es congruente con 3 (mod 4) ( OEIS : A002515 , Primos lucasianos ), entonces su primo seguro correspondiente 2 p + 1 ( congruente con 7 módulo 8) será un divisor del número de Mersenne 2 p − 1. Históricamente, este resultado de Leonhard Euler fue el primer criterio conocido para que un número de Mersenne con un índice primo sea compuesto . [18] Se puede utilizar para generar los números de Mersenne más grandes (con índices primos) que se sabe que son compuestos. [19]
Se conjetura que hay infinitos primos de Sophie Germain, pero esto no ha sido probado . [17] Varias otras conjeturas famosas en teoría de números generalizan ésta y la conjetura de los primos gemelos ; incluyen 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 [17]
dónde
es la constante de primos gemelos de Hardy-Littlewood . Para n = 10 4 , esta estimación predice 156 primos de Sophie Germain, lo que tiene un error del 20 % en comparación con el valor exacto de 190. Para n = 10 7 , la estimación predice 50822, que todavía está un 10 % por debajo del valor exacto de 56032. La forma de esta estimación se debe a GH Hardy y JE Littlewood , quienes aplicaron una estimación similar a los primos gemelos . [20]
Una secuencia ( p , 2 p + 1, 2(2 p + 1) + 1, ...) en la que todos los números son primos se denomina cadena de Cunningham de primera especie. Cada término de dicha secuencia, excepto el último, es un primo de Sophie Germain, y cada término, excepto el primero, es un primo seguro. Extendiendo la conjetura de que existen infinitos primos de Sophie Germain, también se ha conjeturado que existen cadenas de Cunningham arbitrariamente largas, [21] aunque se sabe que las cadenas infinitas son imposibles. [22]
Un número primo q es un primo fuerte si q + 1 y q − 1 tienen ambos algunos factores primos grandes (alrededor de 500 dígitos). Para un primo seguro q = 2 p + 1 , el número q − 1 naturalmente tiene un factor primo grande, a saber p , y por lo tanto un primo seguro q cumple parte de los criterios para ser un primo fuerte. Los tiempos de ejecución de algunos métodos de factorización de 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 .
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 intercambio de claves Diffie-Hellman . Si 2 p + 1 es un número primo seguro, el grupo multiplicativo de números enteros módulo 2 p + 1 tiene un subgrupo de orden primo grande . Por lo general, es este subgrupo de orden primo el que se desea, y la razón para usar números primos seguros es que el módulo sea lo más pequeño posible en relación con p .
Un número primo p = 2 q + 1 se llama primo seguro si q es primo. Por lo tanto, p = 2 q + 1 es un primo seguro si y solo si q es un primo de Sophie Germain, por lo que encontrar primos seguros y encontrar primos de Sophie Germain son equivalentes en dificultad computacional. La noción de primo seguro se puede reforzar a un primo fuerte, para el cual tanto p − 1 como p + 1 tienen factores primos grandes. Los primos seguros y fuertes fueron útiles como factores de claves secretas en el criptosistema RSA , porque evitan que el sistema sea roto por 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 primos seguros y fuertes parece ser insignificante. [23]
Problemas similares se aplican también en otros criptosistemas, incluyendo el intercambio de claves Diffie-Hellman y sistemas similares que dependen de la seguridad del problema del logaritmo discreto en lugar de la factorización de números enteros. [24] Por esta razón, los protocolos de generación de claves para estos métodos a menudo se basan en algoritmos eficientes para generar primos fuertes, que a su vez se basan en la conjetura de que estos primos tienen una densidad suficientemente alta. [25]
En el modo contador de Sophie Germain , se propuso utilizar la aritmética en el campo finito de orden igual al primo seguro 2 128 + 12451, para contrarrestar las debilidades del modo Galois/Contador utilizando el campo finito binario GF(2 128 ). Sin embargo, se ha demostrado que el SGCM es vulnerable a muchos de los mismos ataques criptográficos que el GCM. [26]
En la primera versión del artículo de prueba de primalidad de AKS , se utiliza una conjetura sobre los primos de Sophie Germain para reducir la complejidad del peor caso de O(log 12 n ) a O(log 6 n ) . Se muestra que una versión posterior del artículo tiene una complejidad temporal de O(log 7,5 n ) que también se puede reducir a O(log 6 n ) utilizando la conjetura. [27] Se ha demostrado que variantes posteriores de AKS tienen una complejidad de O(log 6 n ) sin ninguna conjetura o uso de primos de Sophie Germain.
Los números primos seguros que obedecen ciertas congruencias se pueden utilizar para generar números pseudoaleatorios que se utilizan en la simulación de Monte Carlo .
De manera similar, los primos de Sophie Germain pueden usarse en la generación de números pseudoaleatorios . La expansión decimal de 1/ q producirá una secuencia 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. [28] Por lo tanto, los números primos "adecuados" q son 7, 23, 47, 59, 167, 179, etc. ( OEIS : A000353 ) (correspondientes a p = 3, 11, 23, 29, 83, 89, etc.) ( OEIS : A000355 ). El resultado es una secuencia de longitud q − 1 dígitos (incluidos los ceros iniciales). Por ejemplo, si se utiliza q = 23 se generan 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. Tenga en cuenta que estos dígitos no son apropiados para fines criptográficos, ya que el valor de cada uno puede derivarse de su predecesor en el flujo de dígitos. [ cita requerida ]
Los números primos de Sophie Germain se mencionan en la obra de teatro Proof [29] y en la película posterior . [30]
las k
-tuplas primas fuertes es verdadera, entonces las cadenas de Cunningham pueden alcanzar cualquier longitud.
[Jean E.] Taylor señaló que en el ejemplo de un primo de Germain que se daba en el texto preliminar faltaba el término "+ 1". "Cuando fui a ver 'Proof' por primera vez y ese momento apareció en la obra, me alegré de oír claramente el 'más uno'", dice Taylor.
Hay un par de rupturas con el realismo en
Proof
donde los personajes hablan de una manera que es para el beneficio de la audiencia en lugar de la forma en que los matemáticos realmente hablarían entre ellos. Cuando Hal (Harold) recuerda qué es un primo de Germain, le habla a Catherine de una manera que sería condescendiente con otro matemático.
