Diferencia entre revisiones de «Número semiprimo»

Los semiprimos son altamente útiles en el área de la [[criptografía]] y de la [[teoría de números]], más notable en la [[criptografía asimétrica]] donde son utilizados por el [[RSA]] y en las [[secuencia pseudoaleatoria|secuencias pseudoaleatorias]] tales como [[Blum Blum Shub]]. Estos métodos se basan en el hecho de que encontrar dos números primos grandes y multiplicarlos luego es computacionalmente sencillo, mientras que encontrar los factores originales es más difícil. En la [[competición de factorización RSA]], [[RSA Security]] ofreció premios por la factorización de semiprimos grandes específicos. El desafío se cerró en 2007. [http://www.rsa.com/rsalabs/node.asp?id=2092]

 

 

En criptografía práctica, no es suficiente elegir apenas ningún semiprimo; un buen número debe evadir un número bien conocido de [[Factorización de enteros#De propósito específico|algoritmos de propósito específico]] que puedan los números de cierta forma. Los factores p y q de n deben ser muy grandes, alrededor del misma orden de la magnitud que la raíz cuadrada; esto hace la [[división por tentativa]] y el [[Algoritmo rho de Pollard]] impracticable. Al mismo tiempo no pueden estar demasiado juntos, a si no otro prueba simple puede dar factor del número. El número se puede también elegir de modo que ninguno de p − 1, p + 1, q − 1, o q + 1 sean [[número liso|números lisos]], protegiendo contra el [[algoritmo p-1 de Pollard]] o el algoritmo p+1 de Williams. Estas comprobaciones no pueden tomar los algoritmos futuros o los algoritmos secretos en consideración sin embargo, introduciendo la posibilidad de que en su uso hoy puede ser descifrado por algoritmos de propósito específico.