Número primo seguro

En teoría de números, un número primo seguro es un número primo expresable en la forma 2p + 1, donde p es también un número primo; P se llama un número primo de Sophie Germain. Algunos números primos 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 y 2027.

Con la excepción del número 7, todos los primos seguros están en la forma 6n-1, es decir, son congruentes con el módulo 5 6. Del mismo modo, con la excepción de 5, Todos los primos seguros están en la forma 4n-1, es decir, son congruentes con 3 Módulo 4, como se puede verificar fácilmente, teniendo en cuenta que p debe ser un número impar. Dado que el múltiplo común mínimo de 6 y 4 es 12, todos los primos seguros mayores que 7 deben ser expresables en la forma 12n − 1, es decir, deben ser congruentes con la forma 11 12. El número primo seguro más grande conocido actualmente es 183 027 × 2 265 440 − 1, Obtenido junto con el primer corresponsal de Sophie Germain por Tom Wu el 22 de marzo de 2010 utilizando los programas Sgsieve y LLR.

Estos primos se llaman "seguros" debido a su relación con los primos fuertes. Si un número primo q es fuerte, q + 1 y q-1 tienen factores primos "grandes" en relación con el propio número. El número natural antes del primo seguro q = 2P + 1 obviamente tiene un factor primo grande, p, y por lo tanto es un buen candidato para ser un primo fuerte. Varios algoritmos para factorizar un número n requieren tiempo relacionado con las dimensiones de los factores primos de q-1, donde q son los factores primos de n. esto es especialmente cierto en el algoritmo Rho de Pollard. Aunque el tiempo requerido por los Algoritmos de factorización más eficientes, actualmente conocidos, no depende del tamaño de los factores primos de q − 1, Esta propiedad todavía se considera importante en el cifrado: por ejemplo, el estándar ANSI X9. 31 recomienda el uso de primos fuertes (por ejemplo, primos no seguros) para los módulos en cifrado RSA. Esto se debe al hecho de que si asumimos n=pq pero p - 1 y q - 1 no son primos fuertes, entonces hay varias técnicas de factorización, que nos permiten factorizar n a través de técnicas de Fermat y/o Pollard. Los primes seguros también juegan otro papel importante en el cifrado, siendo utilizados en protocolos basados en logaritmos discretos como Diffie - Hellman key exchange. Si 2p + 1 es un primo seguro, el grupo multiplicativo del módulo 2p + 1 incluye un subgrupo cuyo orden es un número primo grande. De esta manera el módulo es pequeño comparado con p, y esta característica hace que los subgrupos de este tipo sean deseables. Los primos seguros, que satisfacen ciertas congruencias modulares, también se pueden usar en algoritmos para generar números pseudo-aleatorios.

Las pruebas no están disponibles para determinar si un número es un primo seguro, como es el caso de los primos de Mersenne y Fermat. La prueba de Pocklington se puede utilizar para determinar si 2p + 1 es primo, una vez que p es primo. Con la excepción de 5, no hay primos seguros que también sean primos de Fermat. Esto se debe a que un primo de Fermat es un primo en la forma 2 n + 1, y la mitad de n − 1 es una potencia de dos. Excepto por el 7, no hay ni siquiera primero seguro de que también son de Mersenne, siendo 2 m -1 ≠ 6k-1. 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 elementos excepto el primero son primos seguros. El último término de una cadena Cunnigham es una terminación prima segura en 7 (expresable en la forma 10n + 7). Esto se debe a que 2 (10N + 7) + 1=20N + 15, que no es primo siendo definitivamente divisible por 5. Si un primo seguro 2p + 1 es congruente con el módulo 7 8, entonces es un divisor del P-ésimo número de Mersenne.

Secuencias de números primos

Cifrado

Tema DSCH

El tema dsch es un motivo musical utilizado por el compositor Dmitrij Šostakovič para representarse a sí mismo. Es un criptograma musical a la manera del tema d...

Dmitrij Šostakovič

Esta página se basa en el artículo de Wikipedia: Fuente, Autores, Licencia Creative Commons Reconocimiento-CompartirIgual.
This page is based on the Wikipedia article: Source, Authors, Creative Commons Attribution-ShareAlike License.
contactos
Política de privacidad , Descargos de responsabilidad