Semiprima

En matemáticas, un semiprimo es un número natural que es el producto de exactamente dos números primos. Los dos primos del producto pueden ser iguales, 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 denominan biprimos.

Ejemplos y variaciones

Los semiprimos menores de 100 son:

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

Las semiprimes son el caso k=2{displaystyle k=2} de la k{displaystyle k}- casi primos, números con exactamente k{displaystyle k} factores principales. Sin embargo, algunas fuentes utilizan "semiprime" para referirse a un conjunto más grande de números, los números con en la mayoría de dos factores principales (incluyendo unidad (1), primos y semiprimes). Estos son:

Fórmula para el número de semiprimos

E. Noel y G. Panos descubrieron una fórmula semiprimera en 2005. Vamos π π 2()n){displaystyle pi _{2}(n)} denota el número de semiprimes menos o igual a n. Entonces...

π π 2()n)=.. k=1π π ()n)[π π ()n/pk)− − k+1]{displaystyle pi _{2}(n)=sum _{k=1}{pi ({sqrt {n}})}[pi (n/p_{k})-k+1]}

π π ()x){displaystyle pi (x)}

pk{displaystyle P_{k}

Propiedades

Los números semiprimos no tienen números compuestos como factores distintos de 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 es compuesto.

Para un semiprime libre de cuadrado n=pq{displaystyle n=pq} (con pل ل q{displaystyle pneq q}) el valor de la función totiente de Euler φ φ ()n){displaystyle varphi (n)} (el número de números enteros positivos menos o igual a n{displaystyle n} que son relativamente primos n{displaystyle n}) toma la forma simple

φ φ ()n)=()p− − 1)()q− − 1)=n− − ()p+q)+1.{displaystyle varphi (n)=(p-1)(q-1)=n-(p+q)+1.}

n=p2{displaystyle n=p^{2}

φ φ ()n)=p()p− − 1)=n− − p.{displaystyle varphi (n)=p(p-1)=n-p.}

Aplicaciones

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 los utilizan 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 juntos (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 para el factoraje de semiprimes 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.

En 1974 el mensaje de Arecibo fue enviado con una señal de radio dirigida a un cluster estrella. Consistió en 1679{displaystyle 1679} dígitos binarios destinados a ser interpretados como 23× × 73{displaystyle 23times 73} imagen de bitmap. El número 1679=23⋅ ⋅ 73{displaystyle 1679=23cdot 73} fue elegido porque es un semiprime y por lo tanto puede ser arreglado en una imagen rectangular de sólo dos maneras distintas (23 filas y 73 columnas, o 73 filas y 23 columnas).