- Número semiprimo
-
En matemáticas , un número semiprimo, también llamado biprimo, es un número natural que es producto de dos números primos no necesariamente distintos.
Contenido
Los 20 primeros semiprimos
Los primeros semiprimos son:
SEMIPRIMOS 4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 ... PRODUCTO DE LOS PRIMOS 2×2 2×3 3×3 2×5 2×7 3×5 3×7 2×11 5×5 2×13 3×11 2×17 5×7 2×19 3×13 2×23 7×7 3×17 5×11 3×19 ... (secuencia n°A001358 del OEIS).
Mayor semiprimo conocido
Actualmente, el mayor semiprimo conocido es (232 582 657 − 1)2, con alrededor de 19 millones de dígitos. Esto es el cuadrado del mayor número primo conocido; el cuadrado de cualquier número primo es semiprimo, así que el mayor semiprimo conocido será siempre el cuadrado del mayor primo conocido, a menos que los factores del semiprimo no se sepan.
Utilidades
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 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. [1]
En 1966, el matemático chino Chen Jingrun demostró que todo número par suficientemente grande puede expresarse como suma de dos primos o como la suma de un primo y de un número que es la multiplicación de dos primos. ("semi-primo").[1]
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 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ú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.
El valor de la función φ de Euler para un semiprimo n = pq es particularmente simple cuando p y q son distintos:
- φ(n) = n + 1 − (p + q).
Curiosidades
En 1974 el mensaje de Arecibo fue enviado con una señal de radio que tuvo como objetivo un cúmulo estelar. Consistió en 1679 dígitos binarios previstos para ser interpretado como imagen bitmap. El número 1679 = 23×73 fue elegido porque es un semiprimo y por lo tanto puede ser analizado solamente en 23 filas y 73 columnas, o 73 filas y 23 columnas.
Referencias
- ↑ Tony Crilly (2011). 50 cosas que hay que saber sobre matemáticas. Ed. Ariel. ISBN 978-987-1496-09-9.
Véase también
Enlaces externos
- MathWorld: Semiprime (en inglés)
Categorías:- Números primos
- Criptografía
- Sucesiones de números enteros
Wikimedia foundation. 2010.