stringtranslate.com

Safe y Sophie Germain son los protagonistas

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.

Números individuales

Los primeros primos de Sophie Germain (aquellos menores que 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, ... OEIS : 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 , ...

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 .

Propiedades

No existe una prueba de primalidad especial para los primos seguros como sí la hay para los primos de Fermat y los 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]

Restricciones modulares

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]

Infinitud y densidad

Problema sin resolver en matemáticas :
¿Existen infinitos números primos de Sophie Germain?

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]

Primos fuertes

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 .

Aplicaciones

Criptografía

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

Prueba de primalidad

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.

Generación de números pseudoaleatorios

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 ]

En la cultura popular

Los números primos de Sophie Germain se mencionan en la obra de teatro Proof [29] y en la película posterior . [30]

Notas

  1. ^ -1 es un residuo cuadrático solo cuando el primo seguro es igual a 5; para todos los demás primos seguros, -1 no es un residuo

Referencias

  1. ^ En concreto, Germain demostró que el primer caso del último teorema de Fermat, en el que el exponente divide a una de las bases, es cierto para todos los primos de Sophie Germain, y utilizó argumentos similares para demostrar lo mismo para todos los demás primos hasta 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, vol. 50, Springer, pp. 61–65, ISBN. 9780387950020.
  2. ^ ab Dalmedico, Amy (1991). "Sophie Germain". Scientific American . 265 (6): 116–123. doi :10.1038/scientificamerican1291-116. JSTOR  24938838 – vía JSTOR.
  3. ^ Laubenbacher, Reinhard; Pengelley, David (1 de noviembre de 2010). ""Voici ce que j'ai trouvé: "El gran plan de Sophie Germain para demostrar el último teorema de Fermat". Historia Matemática . 37 (4): 641–692. arXiv : 0801.1809 . doi : 10.1016/j.hm.2009.12.002 . ISSN  0315-0860.
  4. ^ Los veinte mejores Primes de Sophie Germain — de las páginas Prime . Consultado el 17 de mayo de 2020.
  5. ^ "PrimeGrid's Sophie Germain Prime Search" (PDF) . PrimeGrid. Archivado (PDF) del original el 2022-10-09 . Consultado el 29 de febrero de 2016 .
  6. ^ "PrimeGrid's Sophie Germain Prime Search" (PDF) . PrimeGrid. Archivado (PDF) del original el 2022-10-09 . Consultado el 18 de abril de 2012 .
  7. ^ Base de datos principal: 183027*2^265440-1. De las páginas principales .
  8. ^ La base de datos principal: 648621027630345*2^253824-1.
  9. ^ La base de datos principal: 620366307356565*2^253824-1
  10. ^ La base de datos principal: 1068669447*2^211088-1 De Las páginas principales .
  11. ^ La base de datos principal: 99064503957*2^200008-1 De las páginas principales .
  12. ^ La base de datos principal: 607095*2^176311-1.
  13. ^ La base de datos principal: 48047305725*2^172403-1.
  14. ^ La base de datos principal: 137211941292195*2^171960-1.
  15. ^ Ramesh VP, Makeshwari M (16 de septiembre de 2022). "La raíz menos primitiva de cualquier primo seguro es primo". The American Mathematical Monthly . 129 (10). doi :10.1080/00029890.2022.2115816.
  16. ^ Krantz, Steven G. (2010), Una historia episódica de las matemáticas: cultura matemática a través de la resolución de problemas, Asociación Matemática de América, pág. 206, ISBN 9780883857663.
  17. ^ abc Shoup, Victor (2009), "5.5.5 Primos de Sophie Germain", Una introducción computacional a la teoría de números y al álgebra, Cambridge University Press, págs. 123-124, ISBN 9780521516440.
  18. ^ Ribenboim, P. (1983), "1093", The Mathematical Intelligencer , 5 (2): 28–34, doi :10.1007/BF03023623, MR  0737682.
  19. ^ Dubner, Harvey (1996), "Grandes números primos de Sophie Germain", Matemáticas de la computación , 65 (213): 393–396, CiteSeerX 10.1.1.106.2395 , doi :10.1090/S0025-5718-96-00670-9, MR  1320893 .
  20. ^ Ribenboim, Paulo (1999), El último teorema de Fermat para aficionados, Springer, pág. 141, ISBN 9780387985084.
  21. ^ Wells, David (2011), Números primos: las cifras más misteriosas de las matemáticas, John Wiley & Sons, pág. 35, ISBN 9781118045718Si la conjetura de las k -tuplas primas fuertes es verdadera, entonces las cadenas de Cunningham pueden alcanzar cualquier longitud.
  22. ^ Löh, Günter (1989), "Cadenas largas de primos casi duplicados", Mathematics of Computation , 53 (188): 751–759, doi : 10.1090/S0025-5718-1989-0979939-8 , MR  0979939.
  23. ^ Rivest, Ronald L.; Silverman, Robert D. (22 de noviembre de 1999), ¿Se necesitan primos "fuertes" para RSA? (PDF) , archivado (PDF) desde el original el 2022-10-09
  24. ^ Cheon, Jung Hee (2006), "Análisis de seguridad del problema Diffie-Hellman fuerte", 24.ª Conferencia internacional anual sobre la teoría y las aplicaciones de las técnicas criptográficas (EUROCRYPT'06), San Petersburgo, Rusia, 28 de mayo – 1 de junio de 2006, Actas (PDF) , Lecture Notes in Computer Science , vol. 4004, Springer-Verlag, págs. 1–11, doi : 10.1007/11761679_1.
  25. ^ Gordon, John A. (1985), "Los números primos fuertes son fáciles de encontrar", Actas de EUROCRYPT 84, un taller sobre la teoría y la aplicación de técnicas criptográficas, París, Francia, 9-11 de abril de 1984 , Lecture Notes in Computer Science, vol. 209, Springer-Verlag, págs. 216-223, doi : 10.1007/3-540-39757-4_19.
  26. ^ Yap, Wun-She; Yeo, Sze Ling; Heng, Swee-Huay; Henricksen, Matt (2013), "Análisis de seguridad de GCM para la comunicación", Security and Communication Networks , 7 (5): 854–864, doi :10.1002/sec.798.
  27. ^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004), "PRIMES is in P" (PDF) , Annals of Mathematics , 160 (2): 781–793, doi : 10.4007/annals.2004.160.781 , JSTOR  3597229, archivado (PDF) del original el 2022-10-09
  28. ^ Matthews, Robert AJ (1992), "Recíprocos de máxima periodicidad", Boletín del Instituto de Matemáticas y sus Aplicaciones , 28 (9-10): 147-148, MR  1192408.
  29. ^ Peterson, Ivars (21 de diciembre de 2002), "Drama in numbers: putting a passion for mathematics on stage", Science News , doi :10.2307/4013968, JSTOR  4013968, [Jean E.] Taylor señaló que en el ejemplo de un primo de Germain dado 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 escuchar el 'más uno' claramente expresado", dice Taylor.
  30. ^ Ullman, Daniel (2006), "Movie Review: Proof" (PDF) , Notices of the AMS , 53 (3): 340–342, archivado (PDF) del original el 2022-10-09, 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.

Enlaces externos