Semiprime - Semiprime

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 semiprimes también se denominan biprimes .

Ejemplos y variaciones

Los semiprímenes inferiores a 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 sin 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 números primos , números con factores primos exactos . Sin embargo, algunas fuentes usan "semiprime" para referirse a un conjunto más grande de números, los números con como máximo dos factores primos (incluyendo unidad (1), primos y semiprimes). 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 semiprimes

E. Noel y G. Panos descubrieron una fórmula de conteo semiprime en 2005.

Deje que indican el número de número semiprimo menos de o igual a n. Luego ${\ Displaystyle \ pi _ {2} (n)}$

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

donde es la función de conteo de primos y denota el k- ésimo primo. ${\ Displaystyle \ pi (x)}$ ${\ Displaystyle p_ {k}}$

Propiedades

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

Para una squarefree semiprimo (con ) el valor de la función totient de Euler (el número de enteros positivos de menos de o igual a que son relativamente primos a ) toma la forma sencilla ${\ 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.}

Este cálculo es una parte importante de la aplicación de semiprimes en el criptosistema RSA . Para un semiprimo cuadrado , la fórmula es nuevamente simple: ${\ Displaystyle n = p ^ {2}}$

{\ Displaystyle \ varphi (n) = p (p-1) = np.}

Aplicaciones

El mensaje de Arecibo

Los semiprímenes 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 semiprimes grandes específicos y se entregaron 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.

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 . El número se eligió porque es un semiprimo y, por lo tanto, se puede organizar en una imagen rectangular de solo dos formas distintas (23 filas y 73 columnas, o 73 filas y 23 columnas). ${\ Displaystyle 1679}$ ${\ Displaystyle 23 \ times 73}$ ${\ Displaystyle 1679 = 23 \ cdot 73}$