Semiprime

Producto de dos números primos

En matemáticas , un semiprimo es un número natural que es el producto de exactamente dos números primos . Los dos primos en el producto pueden ser iguales entre sí, por lo que los semiprimos incluyen los cuadrados de los números primos. Debido a que hay infinitos números primos, también hay infinitos semiprimos. Los semiprimos también se denominan biprimos , ^[1] ya que incluyen dos primos, o segundos números , ^[2] por analogía con cómo "primo" significa "primero".

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 la OEIS )

Los semiprimos que no son números cuadrados se denominan 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 la OEIS )

Los semiprimos son el caso de los -casi primos- , números con factores primos exactos . Sin embargo, algunas fuentes utilizan "semiprimos" para referirse a un conjunto más amplio de números, los números con como máximo dos factores primos (incluyendo la unidad (1), los primos y los semiprimos). ^[3] 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

En 2005, E. Noel y G. Panos descubrieron una fórmula de conteo de semiprimos. Sea n el número de semiprimos menores o iguales a n. Entonces, donde es la función de conteo de primos y denota el k- ésimo primo. ^[4] ${\displaystyle \pi _{2}(n)}$ $${\displaystyle \pi _{2}(n)=\sum _{k=1}^{\pi ({\sqrt {n}})}[\pi (n/p_{k})-k+1]}$$ ${\displaystyle \pi (x)}$ ${\displaystyle p_{k}}$

Propiedades

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

Para un semiprimo sin cuadrados (con ), el valor de la función totiente de Euler (el número de números enteros positivos menores o iguales a que son primos relativos a ) toma la forma simple Este cálculo es una parte importante de la aplicación de los semiprimos en el criptosistema RSA . ^[6] Para un semiprimo cuadrado , la fórmula es nuevamente simple: ^[6] ${\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.}$$ ${\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 , más notablemente 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 primos grandes y multiplicarlos juntos (resultando en 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 la factorización de semiprimos grandes específicos y se otorgaron varios premios. El RSA Factoring Challenge original se emitió en 1991 y fue reemplazado en 2001 por el New RSA Factoring Challenge, que luego se retiró en 2007. ^[7]

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 un semiprimo y, por lo tanto, se puede organizar en una imagen rectangular de solo dos maneras distintas (23 filas y 73 columnas, o 73 filas y 23 columnas). ^[8] ${\displaystyle 1679}$ ${\displaystyle 23\times 73}$ ${\displaystyle 1679=23\cdot 73}$

Véase también

• Teorema de Chen
• Número esfénico , producto de tres primos distintos
• Problema de paridad (teoría del tamiz)

Referencias

1. Sloane, N. J. A. (ed.). "Secuencia A001358". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
2. Nowicki, Andrzej (1 de julio de 2013), Segundos números en progresiones aritméticas , arXiv : 1306.6424
3. Stewart, Ian (2010). El gabinete de curiosidades matemáticas del profesor Stewart. Profile Books. pág. 154. ISBN 9781847651280.
4. 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. MR  3306238. S2CID  122410656.
5. French, John Homer (1889). Aritmética avanzada para escuelas secundarias. Nueva York: Harper & Brothers. pág. 53.
6. Cozzens, Margaret; Miller, Steven J. (2013). Las matemáticas del cifrado: una introducción elemental. Mathematical World. Vol. 29. American Mathematical Society. pág. 237. ISBN 9780821883211.
7. "El desafío de factorización RSA ya no está activo". RSA Laboratories. Archivado desde el original el 27 de julio de 2013.
8. du Sautoy, Marcus (2011). Los misterios de los números: una odisea matemática a través de la vida cotidiana. St. Martin's Press. pág. 19. ISBN 9780230120280.

Enlaces externos

• Weisstein, Eric W. "Semiprime". MathWorld .