Un primo seguro es un primo de la forma 2p + 1, donde p también es un primo (y viceversa, p es un primo de Sophie Germain ). 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 )Con la excepción de 7, el número primo seguro q es de la forma 6 k − 1 o, de manera equivalente, q ≡ 5 ( mod 6) - donde p > 3. De la misma manera, con la excepción de 5, el número primo seguro el número q es representable en la forma 4 k − 1 o, de manera equivalente, q ≡ 3 (mod 4) es un enunciado trivial, ya que ( q − 1)/2 debe ser un número natural impar . Combinando ambas formas usando MCM (6,4) obtenemos que el número primo seguro q > 7 también debe ser representable como 12k −1 o, de manera equivalente, q ≡ 11 (mod 12).
Los números primos de este tipo se denominan seguros debido a su conexión con números primos fuertes . Un número primo q se llama primo estricto si q + 1 y q − 1 tienen grandes divisores primos[ especificar ] . Para un número primo seguro q = 2p + 1, el número q − 1 tiene naturalmente un divisor grande, a saber, p , por lo que q satisface parcialmente el criterio de primo fuerte. El tiempo de ejecución de algunos métodos para factorizar un número que tiene q como divisor depende en parte de la magnitud de los divisores primos de q − 1. Esto es cierto, por ejemplo, para los métodos del algoritmo ρ +1 y −1 de Pollard. Aunque la mayoría de los métodos de descomposición eficientes conocidos no dependen de la magnitud de los divisores primos en la descomposición q −1, esto se considera importante para el cifrado: por ejemplo, el estándar ANSI X9.31 requiere que se usen números primos fuertes (no primos seguros ). utilizado para RSA .
Los números primos seguros también son importantes en criptografía por su uso en enfoques basados en logaritmos discretos , como el algoritmo Diffie-Hellman . Si 2p + 1 es un primo seguro, el grupo multiplicativo de números módulo 2p + 1 tiene un subgrupo de orden superior . Este suele ser el subgrupo que desea, y la razón para usar números primos seguros es que el módulo es pequeño con respecto a p .
Los primos seguros, que también cumplen ciertas condiciones , se pueden usar para generar números pseudoaleatorios para usar en el método de Monte Carlo .
No existe una prueba para números primos seguros como la que existe para los números de Fermat y los números de Mersenne . Sin embargo, la prueba de Pocklington se puede usar para probar la primalidad de 2 p + 1 cuando se establece la primalidad de p .
Con la excepción de 5, no hay números primos de Fermat que también sean seguros. Dado que los números primos de Fermat tienen la forma m F = 2 n + 1, se sigue que ( F − 1)/2 es una potencia de dos .
Con la excepción de 7, no hay números primos de Mersenne que también sean seguros. Esto se deriva del hecho mencionado anteriormente de que todos los primos seguros excepto 7 son de la forma 6 k − 1. Los números de Mersenne son de la forma 2 m − 1, pero entonces 2 m − 1 = 6 k − 1, lo que implica que 2 m es divisible por 6, lo cual es imposible.
Todos los elementos de la secuencia de Cunningham, excepto el primero, son números de Sophie Germain de primer tipo, por lo que todos los elementos excepto el primero de la cadena son números primos seguros. Los números primos que terminan en 7, es decir, de la forma 10 n + 7, si se dan en tales cadenas, son siempre los últimos, ya que 2(10 n + 7) + 1 = 20 n + 15 es divisible por 5.
Si el primo seguro q es 7 mod 8, es un divisor del número de Mersenne , que corresponde al número de Sophie Germain (usado como potencia).
En marzo de 2010, el número seguro más grande conocido es 183027 2 265441 −1. Este número, al igual que el correspondiente número más grande conocido de Sophie Germain, fue encontrado por Tom Wu el 22 de marzo de 2010 utilizando los programas sgsieve y LLR [1] .
El 5 de febrero de 2007 se calculó el módulo del logaritmo discreto de un primo seguro de 160 dígitos (530 bits). Ver registros para logaritmos discretos .