Primos Safe y Sophie Germain

En la teoría de números, un número primo p es un Sophie Germain prime si 2p+ 1 es también primo. El número 2p+ 1 asociado con un Sophie Germain prime se llama un seguro. Por ejemplo, 11 es un Sophie Germain prime y 2 × 11 + 1 = 23 es su principal seguro asociado. Sophie Germain primos son nombrados después de la matemática francesa Sophie Germain, que los usó en sus investigaciones del último teorema de Fermat. Un intento de Germain para probar el último teorema de Fermat fue dejar p ser un número primo de la forma 8k + 7 y dejar n = p – 1. En este caso, ${displaystyle ¿Qué?$ es insolvable. La prueba de Germain, sin embargo, permaneció inacabada. A través de sus intentos de resolver el último teorema de Fermat, Germain desarrolló un resultado ahora conocido como Teorema de Germain que afirma que si p es una prima rara y 2p + 1 es también primo, entonces p debe dividirse x, Sí., o z. De lo contrario, ${fnK}$. En este caso p no divide x, Sí., o z se llama el primer caso. El trabajo de Sophie Germain fue el mayor progreso alcanzado en el último teorema de Fermat en ese momento. El trabajo más difícil de Kummer y otros siempre dividieron el problema en casos primero y segundo. Sophie Germain primos y primos seguros tienen aplicaciones en criptografía de clave pública y pruebas de primalidad. It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven.

Números individuales

Los primeros números primos de Sophie Germain (menos 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 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⁶⁰⁰.

Dos proyectos informáticos distribuidos, 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.

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 de 240 dígitos (795 bits) primo RSA-240 + 49204 (el primer cebado seguro por encima de RSA-240) utilizando un algoritmo de tamiz de campo numérico; ver Registros de logaritmos discretos.

Propiedades

No existe una prueba de primalidad especial para primos seguros como la que existe para los primos de Fermat y los primos de Mersenne. Sin embargo, el criterio de Pocklington se puede usar para probar la primalidad de 2p + 1 una vez que se ha probado la primalidad de p.

Al igual que 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 que terminan en 7, es decir, de la forma 10n + 7, son los últimos términos de tales cadenas cuando ocurren, ya que 2(10n + 7) + 1 = 20n + 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 correspondiente primo de Sophie Germain como exponente.

Si q > 7 es un primo seguro, entonces q divide 3^(q−1)/2 − 1. (Esto se deduce 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 (mod 6) – como es 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) — trivialmente cierto ya que (q − 1) / 2 debe evaluarse como un número natural impar. Combinando ambas formas usando lcm(6, 4) determinamos que un primo seguro q > 7 también debe tener 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 mod 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 repetidos completos en base 12 son 5 y 7).

Si p es un número primo de Sophie Germain mayor que 3, entonces p debe ser congruente con 2 mod 3. De lo contrario, sería congruente con 1 mod 3 y 2p + 1 sería congruente con 3 mod 3, imposible para un número primo. 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" 2C en la estimación de Hardy-Littlewood sobre la densidad de los números primos de Sophie Germain.

Si un primo de Sophie Germain p es congruente con 3 (mod 4) (OEIS: A002515, primos lucasianos), entonces su primo seguro coincidente 2p + 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 fuera compuesto. Se puede usar para generar los números de Mersenne más grandes (con índices primos) que se sabe que son compuestos.

Infinitud y densidad

Se conjetura que hay infinitos números primos de Sophie Germain, pero esto no ha sido probado. 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

${displaystyle 2C{fn}}approx 1.32032{fn} {fnn}}}}} {fn}}}}}}$

dónde

${displaystyle C=prod {p-1)}approx 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 descuento con respecto al valor exacto de 56032. La forma de esta estimación se debe a G. H. Hardy y J. E. Littlewood, quienes aplicaron una estimación similar a primos gemelos.

Una secuencia (p, 2p + 1, 2(2p + 1) + 1,...) en la que todos los números son primos se llama cadena de Cunningham del primer tipo. 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, aunque se sabe que las cadenas infinitas son imposibles.

Primos fuertes

Un número primo q es un número primo fuerte si q + 1 y q − 1 ambos 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 con parte de los criterios para ser un factor fuerte principal. 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, del 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 discretas basadas en logaritmos como el intercambio de claves Diffie-Hellman. Si 2p + 1 es un primo seguro, el grupo multiplicativo de enteros módulo 2p + 1 tiene un subgrupo de gran orden primo. 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 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 criptosistema 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.

También se aplican problemas similares 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. 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.

En el modo contador de Sophie Germain, se propuso usar la aritmética en el campo de orden finito igual al número primo de Sophie Germain 2¹²⁸ + 12451, para contrarrestar las debilidades en el modo contador/Galois 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.

Pruebas de primalidad

En la primera versión del documento de prueba de primalidad de AKS, se usa una conjetura sobre los números primos de Sophie Germain para reducir la complejidad del peor de los casos de O(log¹²< i>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. Se ha demostrado que las variantes posteriores de AKS tienen una complejidad de O(log⁶n) sin conjeturas ni uso de Sophie primos de Germain.

Generación de números pseudoaleatorios

Los números primos seguros que obedecen a ciertas congruencias se pueden utilizar para generar números pseudoaleatorios útiles en la simulación Monte Carlo.

Del mismo modo, 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 una Sophie Germain prima p, con p congruente con 3, 9 u 11 módulo 20. Por lo tanto, "adecuado" los números primos 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 un flujo 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 adecuados para fines criptográficos, ya que el valor de cada uno puede derivarse de su predecesor en el flujo de dígitos.

En la cultura popular

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