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 número primo de Sophie Germain se llama un número primo seguro . Por ejemplo, 11 es un número primo de Sophie Germain y 2 × 11 + 1 = 23 es su número primo seguro asociado. Los números primos de Sophie Germain llevan el nombre de la matemática francesa Sophie Germain , quien los utilizó en sus investigaciones sobre el último teorema de Fermat . [1] Sophie Germain primes y safe primes tienen aplicaciones en criptografía de clave pública y pruebas de primalidad . Ha sido conjeturadoque hay infinitos números primos de Sophie Germain, pero esto 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, ... OEIS : A005384
Por lo tanto, los primeros números 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, ... OEIS : A005385
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 grandes números primos de Sophie Germain. Los números primos de Sophie Germain más grandes conocidos a partir de mayo de 2020[actualizar]se dan en la siguiente tabla. [2]
Valor | Número de dígitos | Tiempo de descubrimiento | Descubridor |
---|---|---|---|
2618163402417 × 2 1290000 - 1 | 388342 | Febrero de 2016 | PrimeGrid [3] |
18543637900515 × 2 666667 - 1 | 200701 | Abril de 2012 | Philipp Bliedung en una búsqueda distribuida de PrimeGrid utilizando los programas TwinGen y LLR [4] |
183027 × 2 265440 - 1 | 79911 | Marzo de 2010 | Tom Wu usando LLR [5] |
648621027630345 × 2 253824 - 1 y 620366307356565 × 2 253824 - 1 | 76424 | Noviembre de 2009 | Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza y Antal Járai [6] [7] |
1068669447 × 2 211088 - 1 | 63553 | Mayo de 2020 | Michael Kwok [8] |
99064503957 × 2 200008 - 1 | 60220 | Abril de 2016 | S. Urushihata [9] |
607095 × 2 176311 - 1 | 53081 | Septiembre de 2009 | Tom Wu [10] |
48047305725 × 2 172403 - 1 | 51910 | Enero de 2007 | David Underbakke con TwinGen y LLR [11] |
137211941292195 × 2 171960 - 1 | 51780 | 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 240 dígitos (795 bits) primo RSA-240 + 49204 (el primer número primo seguro arriba RSA-240) usando un algoritmo de tamiz de campo numérico ; consulte Registros de logaritmos discretos .
Propiedades
No existe una prueba de primalidad especial para los números primos seguros como ocurre con 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 primacía de 2 p + 1 una vez que se ha probado la primacía 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 tales cadenas son primos seguros. Los números primos seguros terminados en 7, es decir, de la forma 10 n + 7, son los últimos términos en tales cadenas cuando ocurren, ya que 2 (10 n + 7) + 1 = 20 n + 15 es divisible por 5.
Si un primo seguro q es congruente con 7 módulo 8, entonces es un divisor del número de Mersenne con su primo correspondiente de Sophie Germain como exponente.
Si q > 7 es un primo seguro, entonces q divide 3 ( q −1) / 2 - 1. (Esto se sigue del hecho de que 3 es un residuo cuadrático mod q .)
Restricciones modulares
Con la excepción de 7, un primo seguro q es de la forma 6 k - 1 o, de manera equivalente, q ≡ 5 ( mod 6) - como es p > 3. De manera similar, con la 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 evaluar a un número natural impar . Combinando ambas formas usando el mcm (6, 4) determinamos que un primo seguro q > 7 también debe ser de la forma 12 k - 1 o, de manera equivalente, q ≡ 11 (mod 12). De ello se deduce que 3 (también 12) es un mod de residuo cuadrático q para cualquier primo seguro q > 7. (Por lo tanto, 12 no es una raíz primitiva de ningún primo seguro q > 7, y los únicos primos seguros que también son primos de repetición completos en base 12 son 5 y 7.)
Si p es un primo de Sophie Germain mayor que 3, entonces p debe ser congruente con 2 mod 3. Si no, sería congruente con 1 mod 3 y 2 p + 1 sería congruente con 3 mod 3, imposible para a número primo. [13] Restricciones similares son válidas para módulos primos más grandes 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. [14]
Si un primo p de Sophie Germain es congruente con 3 (mod 4) ( OEIS : A002515 , primos lucasianos ), entonces su primo seguro coincidente 2 p + 1 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 . [15] Se puede utilizar para generar los números de Mersenne más grandes (con índices primos) que se sabe que son compuestos. [dieciséis]
Infinitud y densidad
¿Hay infinitos números primos de Sophie Germain?
Se conjetura que hay infinitos números primos de Sophie Germain, pero esto no ha sido probado . [14] Varias otras conjeturas famosas en la teoría de números generalizan esta 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 del número de números primos de Sophie Germain menores que n es [14]
dónde
es la constante prima gemela de Hardy-Littlewood . Para n = 10 4 , esta estimación predice 156 números primos de Sophie Germain, 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% menos que el 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 . [17]
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 primer tipo. Cada término de dicha secuencia, excepto el último, es un número primo de Sophie Germain, y todos los términos excepto el primero son primos seguros. 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 primo fuerte si q + 1 y q - 1 tienen 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 , por lo que un primo seguro q cumple con parte de los criterios para ser un primo fuerte. Los tiempos de ejecución de algunos métodos para 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 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 es deseable, 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 denomina 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 de cálculo. La noción de una prima segura se puede fortalecer a una prima fuerte, para la 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 criptosistema RSA , porque impiden que el sistema se rompa mediante 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]
Problemas similares se aplican también en otros criptosistemas, incluido el intercambio de claves Diffie-Hellman y sistemas similares que dependen de la seguridad del problema de registro 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 Sophie Germain modo de contador , se propuso utilizar la aritmética en el campo finito de orden igual a la Sophie Germain prime 2 128 + 12 451, a las debilidades de contador en modo de contador / Galois utilizando el binario campo finito GF (2 128 ). Sin embargo, se ha demostrado que SGCM es vulnerable a muchos de los mismos ataques criptográficos que GCM. [23]
Prueba de primordialidad
En la primera versión del documento de prueba de primalidad de AKS , se utiliza una conjetura sobre los números primos de Sophie Germain para reducir la complejidad del peor de los casos de O (log 12 n ) a O (log 6 n ) . Se muestra que una versión posterior del artículo tiene una complejidad de tiempo O (log 7,5 n ) que también puede reducirse a O (log 6 n ) utilizando la conjetura. [24] Se ha demostrado que las variantes posteriores de AKS tienen una complejidad de O (log 6 n ) sin conjeturas ni el uso de números primos de Sophie Germain.
Generación de números pseudoaleatorios
Se pueden usar números primos seguros que obedezcan a ciertas congruencias para generar números pseudoaleatorios de uso en la simulación de Monte Carlo .
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 va a producir un flujo de q - 1 dígitos pseudo-aleatorios, si q es el primer seguro de un Sophie Germain prime p , con p congruente a 3, 9, o 11 de módulo 20. [25] Por lo tanto números primos "adecuados" q son 7, 23, 47, 59, 167, 179, etc. ( OEIS : A000353 ) (correspondiente 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). 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. 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 [26] y en la película posterior . [27]
Referencias
- ↑ Específicamente, Germain demostró que el primer caso del último teorema de Fermat, en el que el exponente divide una de las bases, es verdadero para todos los primos de Sophie Germain, y usó argumentos similares para demostrar lo mismo para todos los demás primos hasta 100. Para Para obtener más información, consulte Edwards, Harold M. (2000), El último teorema de Fermat: Una introducción genética a la teoría algebraica de números , Textos de posgrado en matemáticas, 50 , Springer, págs. 61–65, ISBN 9780387950020.
- ^ Los veinte primeros premios de Sophie Germain - de las páginas principales . Consultado el 17 de mayo de 2020.
- ^ La base de datos principal: 2618163402417 × 2 1290000 - 1
- ^ "PrimeGrid's Sophie Germain Prime Search" (PDF) . PrimeGrid . Consultado el 18 de abril de 2012 .
- ^ La base de datos principal: 183027 * 2 ^ 265440-1 . De las páginas principales .
- ^ La base de datos principal: 648621027630345 * 2 ^ 253824-1 .
- ^ La base de datos principal: 620366307356565 * 2 ^ 253824-1
- ^ La base de datos Prime: 1068669447 * 2 ^ 211088-1 De las páginas Prime .
- ^ La base de datos Prime: 99064503957 * 2 ^ 200008-1 De las páginas Prime .
- ^ La base de datos principal: 607095 * 2 ^ 176311-1 .
- ^ La base de datos principal: 48047305725 * 2 ^ 172403-1 .
- ^ La base de datos principal: 137211941292195 * 2 ^ 171960-1 .
- ^ 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. 206, ISBN 9780883857663.
- ^ a b c Shoup, Victor (2009), "5.5.5 Sophie Germain primes", A Computational Introduction to Number Theory and Algebra , Cambridge University Press, págs. 123-124, ISBN 9780521516440.
- ^ Ribenboim, P. (1983), "1093", The Mathematical Intelligencer , 5 (2): 28–34, doi : 10.1007 / BF03023623 , MR 0737682.
- ^ Dubner, Harvey (1996), "Large Sophie Germain primes", Mathematics of Computation , 65 : 393–396, CiteSeerX 10.1.1.106.2395 , doi : 10.1090 / S0025-5718-96-00670-9 , MR 1320893.
- ^ Ribenboim, Paulo (1999), Último teorema de Fermat para aficionados , Springer, p. 141, ISBN 9780387985084.
- ^ Wells, David (2011), Números primos: Las cifras más misteriosas de las matemáticas , John Wiley & Sons, p. 35, ISBN 9781118045718,
Si la conjetura de tuplas k primos fuertes es cierta, entonces las cadenas de Cunningham pueden alcanzar cualquier longitud.
- ^ Löh, Günter (1989), "Cadenas largas de números primos casi duplicados", Mathematics of Computation , 53 (188): 751–759, doi : 10.1090 / S0025-5718-1989-0979939-8 , MR 0979939.
- ^ Rivest, Ronald L .; Silverman, Robert D. (22 de noviembre de 1999), ¿Se necesitan primos 'fuertes' para RSA? (PDF)
- ^ Cheon, Jung Hee (2006), "Análisis de seguridad del problema fuerte de Diffie-Hellman", 24ª Conferencia Internacional Anual sobre Teoría y Aplicaciones de Técnicas Criptográficas (EUROCRYPT'06), San Petersburgo, Rusia, 28 de mayo - 1 de junio 2006, Actas (PDF) , Lecture Notes in Computer Science , 4004 , Springer-Verlag, págs. 1-11, doi : 10.1007 / 11761679_1.
- ^ Gordon, John A. (1985), "Los números primos fuertes son fáciles de encontrar", Actas de EUROCRYPT 84, A Workshop on the Theory and Application of Cryptographic Techniques, París, Francia, 9-11 de abril de 1984 , Lecture Notes in Computer Science , 209 , Springer-Verlag, págs. 216–223, doi : 10.1007 / 3-540-39757-4_19.
- ^ Yap, Wun-She; Yeo, Sze Ling; Heng, Swee-Huay; Henricksen, Matt (2013), "Análisis de seguridad de GCM para comunicaciones", Redes de seguridad y comunicación , doi : 10.1002 / sec.798.
- ^ 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
- ^ Matthews, Robert AJ (1992), "Recíprocos máximamente periódicos", Boletín del Instituto de Matemáticas y sus Aplicaciones , 28 (9-10): 147-148, MR 1192408.
- ^ Peterson, Ivars (21 de diciembre de 2002), "Drama en números: poner la pasión por las matemáticas en el escenario" , Science News ,
[Jean E.] Taylor señaló que el ejemplo de un número primo de Germain que se da en el texto preliminar término "+ 1" "Cuando fui por primera vez a ver 'Proof' y ese momento surgió en la obra, estaba feliz de escuchar claramente el 'más uno'", dice Taylor.
- ^ Ullman, Daniel (2006), "Movie Review: Proof" (PDF) , Notices of the AMS , 53 (3): 340–342,
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 hablarían entre ellos. Cuando Hal (Harold) recuerda lo que es un Germain principal, le habla a Catherine de una manera que sería condescendiente para otro matemático.
enlaces externos
- Seguro prime en PlanetMath .
- M. Abramowitz , IA Stegun , ed. (1972). Manual de funciones matemáticas . Matemáticas Aplicadas. Serie. 55 (Décima edición ed.). Oficina Nacional de Normas. pag. 870.