Número semiprimo

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

  1. 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


Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Número casi primo — En teoría de números, se le llama k casi primo a un número natural n escrito en la forma n = p1...pk en donde los pi son números primos (no necesariamente distintos) y es una constante. Así definido, un número k casi tendrá exactamente k factores …   Wikipedia Español

  • Número de Hilbert — En matemáticas, el concepto de número de Hilbert, nombrado así en honor de David Hilbert, tiene distintos significados. En análisis y teoría de números, el número de Hilbert (también conocido como constante de Gelfond Schneider) es la constante… …   Wikipedia Español

  • Problemas de Landau — Los Problemas de Landau son cuatro conocidos problemas básicos sobre los números primos, que Edmund Landau catalogó como inabarcables en el estado actual de la ciencia durante el Quinto Congreso Internacional de Matemáticos del año 1912. Los… …   Wikipedia Español

  • Algoritmo rho de Pollard — Para otros usos de este término, véase algoritmo rho de Pollard para logaritmos discretos. El algoritmo rho de Pollard es un algoritmo especializado de factorización de números enteros. Fue inventado por John Pollard en 1975. Es especialmente… …   Wikipedia Español

  • Potencia prima — En matemática, una potencia prima o número primario, es una potencia entera y positiva de un número primo. Por ejemplo 5=51, 9=32 y 16=24 son potencias primas, mientras que 6=2×3, 15=3×5 y 36=62=22×32 no lo son. Las primeras potencias primas son… …   Wikipedia Español

  • Conjetura de Legendre — La conjetura de Legendre, enunciada por de Adrien Marie Legendre, afirma que siempre existe un número primo entre n2 y (n + 1)2. Esta conjetura forma parte de los problemas de Landau. Chen Jingrun demostró en 1965 que siempre existe un número… …   Wikipedia Español

  • Teoría de cribas — La teoría de cribas es un conjunto de técnicas generales en teoría de números, diseñadas para contar o estimar el tamaño de un conjunto de números enteros. El ejemplo primordial de un conjunto tamizado es conjunto de números primos menores… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”