semiprime

Producto de dos números primos

En matemáticas , un semiprimo es un número natural que es producto de exactamente dos números primos . Los dos primos del producto pueden ser iguales entre sí, por lo que los semiprimos incluyen los cuadrados de los números primos. Como hay infinitos números primos, también hay infinitos semiprimos. Los semiprimos también se llaman biprimos . ^[1]

Ejemplos y variaciones

Los semiprimos menores que 100 son:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94 y 95 (secuencia A001358 en el OEIS )

Los semiprimos que no son números cuadrados se llaman semiprimos discretos, distintos o libres de cuadrados:

6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, ... (secuencia A006881 en el OEIS )

Los semiprimos son el caso de los -casi primos , números con factores exactamente primos. Sin embargo, algunas fuentes utilizan "semiprimos" para referirse a un conjunto más grande de números, los números con como máximo dos factores primos (incluida la unidad (1), primos y semiprimos). ^[2] Estos son: ${\displaystyle k=2}$ ${\displaystyle k}$ ${\displaystyle k}$

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, ... (secuencia A037143 en la OEIS )

Fórmula para el número de semiprimos

E. Noel y G. Panos descubrieron una fórmula de conteo de semiprimos en 2005. Denotemos el número de semiprimos menores o iguales que n. Entonces ${\displaystyle \pi _{2}(n)}$

$${\displaystyle \pi _{2}(n)=\sum _{k=1}^{\pi ({\sqrt {n}})}[\pi (n/p_{k})-k+1]}$$

función de conteo de primosk^[3] ${\displaystyle \pi (x)}$ ${\displaystyle p_{k}}$

Propiedades

Los números semiprimos no tienen números compuestos como factores distintos a ellos mismos. ^[4] Por ejemplo, el número 26 es semiprimo y sus únicos factores son 1, 2, 13 y 26, de los cuales sólo 26 es compuesto.

Para un semiprimo libre de cuadrados (con ), el valor de la función totiente de Euler (el número de números enteros positivos menores o iguales que son primos relativos con ) toma la forma simple ${\displaystyle n=pq}$ ${\displaystyle p\neq q}$ ${\displaystyle \varphi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$

$${\displaystyle \varphi (n)=(p-1)(q-1)=n-(p+q)+1.}$$

criptosistema RSA^[5][5] ${\displaystyle n=p^{2}}$

$${\displaystyle \varphi (n)=p(p-1)=n-p.}$$

Aplicaciones

El mensaje de Arecibo

Los semiprimos son muy útiles en el área de la criptografía y la teoría de números , sobre todo en la criptografía de clave pública , donde son utilizados por RSA y generadores de números pseudoaleatorios como Blum Blum Shub . Estos métodos se basan en el hecho de que encontrar dos números primos grandes y multiplicarlos (lo que da como resultado un semiprimo) es computacionalmente simple, mientras que encontrar los factores originales parece ser difícil. En el RSA Factoring Challenge , RSA Security ofreció premios por el factoring de grandes semiprimes específicos y se entregaron varios premios. El RSA Factoring Challenge original se publicó en 1991 y fue reemplazado en 2001 por el New RSA Factoring Challenge, que luego fue retirado en 2007. ^[6]

En 1974 se envió el mensaje de Arecibo con una señal de radio dirigida a un cúmulo de estrellas . Consistía en dígitos binarios destinados a ser interpretados como una imagen de mapa de bits . Se eligió el número porque es semiprimo y, por lo tanto, se puede organizar en una imagen rectangular sólo de dos maneras distintas (23 filas y 73 columnas, o 73 filas y 23 columnas). ^[7] ${\displaystyle 1679}$ ${\displaystyle 23\times 73}$ ${\displaystyle 1679=23\cdot 73}$

Ver también

• teorema de chen
• Número esfénico , producto de tres números primos distintos

Referencias

1. Sloane, Nueva Jersey (ed.). "Secuencia A001358". La enciclopedia en línea de secuencias enteras . Fundación OEIS.
2. Stewart, Ian (2010). Gabinete de curiosidades matemáticas del profesor Stewart. Libros de perfil. pag. 154.ISBN _ 9781847651280.
3. Ishmukhametov, Sh. T.; Sharifullina, FF (2014). "Sobre la distribución de números semiprimos". Matemáticas rusas . 58 (8): 43–48. doi :10.3103/S1066369X14080052. SEÑOR  3306238. S2CID  122410656.
4. Francés, John Homer (1889). Aritmética avanzada para escuelas secundarias. Nueva York: Harper & Brothers. pag. 53.
5. Cozzens, Margaret; Molinero, Steven J. (2013). Las matemáticas del cifrado: una introducción elemental. Mundo Matemático. vol. 29. Sociedad Matemática Estadounidense. pag. 237.ISBN _ 9780821883211.
6. "El RSA Factoring Challenge ya no está activo". Laboratorios RSA. Archivado desde el original el 27 de julio de 2013.
7. du Sautoy, Marcus (2011). Los misterios de los números: una odisea matemática a través de la vida cotidiana. Prensa de San Martín. pag. 19.ISBN _ 9780230120280.

enlaces externos

• Weisstein, Eric W. "Semiprime". MundoMatemático .