Número primo de Sophie Germain

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.

Números individuales

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 + 11⁶⁰⁰.

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 × 2^1290000 − 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 × 2^666667 − 1	200.701	abril de 2012	Philipp Bliedung en una búsqueda distribuida PrimeGrid utilizando los programas TwinGen y el LLR^[4]​
183027 × 2^265440 − 1	79.911	marzo de 2010	Tom Wu usando LLR^[5]​
648621027630345 × 2^253824 − 1 y 620366307356565 × 2^253824 − 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 × 2^211088 − 1	63.553	mayo de 2020	Michael Kwok^[8]​
99064503957 × 2^200008 − 1	60.220	abril de 2016	S. Urushihata^[9]​
607095 × 2^176311 − 1	53.081	septiembre de 2009	Tom Wu^[10]​
48047305725 × 2^172403 − 1	51.910	enero de 2007	David Underbakke utilizando TwinGen y LLR^[11]​
137211941292195 × 2^171960 − 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.

Propiedades

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 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 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]​

Infinitud y densidad

 

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]​

${\displaystyle 2C{\frac {n}{(\ln n)^{2}}}\approx 1.32032{\frac {n}{(\ln n)^{2}}}}$ 

donde

${\displaystyle C=\prod _{p>2}{\frac {p(p-2)}{(p-1)^{2}}}{\text{aprox. }}0.660161}$ 

es la constante prima gemela de Hardy-Littlewood. Para n = 10⁴, 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 = 10⁷, 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]​

Primos fuertes

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.

Aplicaciones

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 2¹²⁸ + 12451, para contrarrestar las debilidades del Modo Galois/Contador usando el campo finito binario GF(2¹²⁸). 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(log¹²n) a O(log⁶n). Se muestra que una versión posterior del documento tiene una complejidad de tiempo O(log^7.5n) que también se puede reducir a O(log⁶n) usando la conjetura.^[24]​ Se ha demostrado que las variantes posteriores del Test AKS tienen una complejidad de O(log⁶n) 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.

En la cultura popular

Los primos de Sophie Germain se mencionan en la obra de teatro La Prueba^[26]​ y la película del mismo nombre.^[27]​

Referencias

1. Específicamente, Germain demostró que el primer caso del último teorema de Fermat, en el que el exponente divide una de las bases, es cierto para todos los números primos de Sophie Germain, y usó argumentos similares para demostrar lo mismo para todos los demás números primos hasta el 100. Para más detalles véase Edwards, Harold M. (2000), Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory, Graduate Texts in Mathematics 50, Springer, pp. 61-65, ISBN 9780387950020 ..
2. The Top Twenty Sophie Germain Primes — from the Prime Pages. Retrieved 17 May 2020.
3. «PrimeGrid's Sophie Germain Prime Search» (PDF). PrimeGrid. Consultado el 29 de febrero de 2016. 
4. «PrimeGrid's Sophie Germain Prime Search» (PDF). PrimeGrid. Consultado el 18 de abril de 2012. 
5. The Prime Database: 183027*2^265440-1. From The Prime Pages.
6. The Prime Database: 648621027630345*2^253824-1.
7. The Prime Database: 620366307356565*2^253824-1
8. The Prime Database: 1068669447*2^211088-1 From The Prime Pages.
9. The Prime Database: 99064503957*2^200008-1 From The Prime Pages.
10. The Prime Database: 607095*2^176311-1.
11. The Prime Database: 48047305725*2^172403-1.
12. The Prime Database: 137211941292195*2^171960-1.
13. Krantz, Steven G. (2010), An Episodic History of Mathematics: Mathematical Culture Through Problem Solving, Mathematical Association of America, p. 206, ISBN 9780883857663 ..
14. Shoup, Victor (2009), «5.5.5 Sophie Germain primes», A Computational Introduction to Number Theory and Algebra, Cambridge University Press, pp. 123-124, ISBN 9780521516440 ..
15. Ribenboim, P. (1983), «1093», The Mathematical Intelligencer 5 (2): 28-34, MR 737682, doi:10.1007/BF03023623 ..
16. Dubner, Harvey (1996), «Large Sophie Germain primes», Mathematics of Computation 65: 393-396, MR 1320893, doi:10.1090/S0025-5718-96-00670-9, «citeseerx: 10.1.1.106.2395 » ..
17. Ribenboim, Paulo (1999), Fermat's Last Theorem for Amateurs, Springer, p. 141, ISBN 9780387985084 ..
18. Wells, David (2011), Prime Numbers: The Most Mysterious Figures in Math, John Wiley & Sons, p. 35, ISBN 9781118045718, «Si la conjetura de las "k"-tuplas de primos fuertes es cierta, entonces las cadenas de Cunningham pueden alcanzar cualquier longitud. » .
19. Löh, Günter (1989), «Long chains of nearly doubled primes», Mathematics of Computation 53 (188): 751-759, MR 0979939, doi:10.1090/S0025-5718-1989-0979939-8 ..
20. Rivest, Ronald L.; Silverman, Robert D. (22 de noviembre de 1999), Are 'strong' primes needed for RSA? .
21. Cheon, Jung Hee (2006), «Security analysis of the strong Diffie–Hellman problem», 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'06), St. Petersburg, Russia, May 28 – June 1, 2006, Proceedings, Lecture Notes in Computer Science 4004, Springer-Verlag, pp. 1-11, doi:10.1007/11761679_1 ..
22. Gordon, John A. (1985), «Strong primes are easy to find», Proceedings of EUROCRYPT 84, A Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, April 9–11, 1984, Lecture Notes in Computer Science 209, Springer-Verlag, pp. 216-223, doi:10.1007/3-540-39757-4_19 ..
23. Yap, Wun-She; Yeo, Sze Ling; Heng, Swee-Huay; Henricksen, Matt (2013), «Security analysis of GCM for communication», Security and Communication Networks, doi:10.1002/sec.798 ..
24. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004), «PRIMES is in P», Annals of Mathematics 160 (2): 781-793, JSTOR 3597229, doi:10.4007/annals.2004.160.781 .
25. Matthews, Robert A. J. (1992), «Maximally periodic reciprocals», Bulletin of the Institute of Mathematics and its Applications 28 (9-10): 147-148, MR 1192408 ..
26. Peterson, Ivars (Dec 21, 2002), «Drama in numbers: putting a passion for mathematics on stage», Science News, «[Jean E.] Taylor señaló que al ejemplo de un primo de Germain dado en el texto preliminar le faltaba el término "+ 1". "Cuando fui por primera vez a ver 'La Prueba' y ese momento surgió en la obra, me alegró escuchar claramente el 'más uno'", dice Taylor. » .
27. Ullman, Daniel (2006), «Movie Review: Proof», Notices of the American Mathematical Society 53 (3): 340-342, «Hay un par de rupturas con el realismo en "La Prueba", donde los personajes hablan de una manera que beneficia a la audiencia en lugar de ajustarse a la forma en que los matemáticos hablarían entre ellos. Cuando Hal (Harold) recuerda lo que es un primo de Germain, le habla a Catherine de una manera que sería condescendiente con otro matemático. » .

Enlaces externos

• Safe prime en PlanetMath.
• Milton Abramowitz, Irene Stegun, ed. (1972). Handbook of Mathematical Functions. Applied Math. Series 55 (Tenth Printing edición). National Bureau of Standards. p. 870. 

•   Datos: Q624025