En matemáticas , un semiprimo es un número natural que es el producto de exactamente dos números primos . Los dos números primos del 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 . [1]
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 semiprimes son el caso de El - casi números primos , números con exactamentefactores primos. 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). [2] Estos son:
Fórmula para el número de semiprimes
E. Noel y G. Panos descubrieron una fórmula de recuento semiprime en 2005. [3]
Dejar denotar el número de semiprimos menor o igual que n. Luego
dónde es la función de conteo de primos ydenota el k- ésimo primo. [4]
Propiedades
Los números de semiprimo no tienen números compuestos como factores distintos a 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 semiprime sin cuadrados (con ) el valor de la función totient de Euler (el número de enteros positivos menores o iguales que que son relativamente primos para) toma la forma simple
Este cálculo es una parte importante de la aplicación de semiprimes en el criptosistema RSA . [6] Por un semiprimo cuadrado, la fórmula es nuevamente simple: [6]
Aplicaciones
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 publicó 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 un imagen de mapa de bits . El númerose 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). [8]
Ver también
Referencias
- ^ Sloane, N. J. A. (ed.). "Secuencia A001358" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ Stewart, Ian (2010). Gabinete de curiosidades matemáticas del profesor Stewart . Libros de perfil. pag. 154. ISBN 9781847651280.
- ^ Sobre la distribución de números semiprime Shamil Ishmukhametov
- ^ Weisstein, Eric W. Semiprime: de Wolfram MathWorld
- ^ Francés, John Homer (1889). Aritmética avanzada para escuelas secundarias . Nueva York: Harper & Brothers. pag. 53.
- ^ a b Cozzens, Margaret; Miller, Steven J. (2013), Las matemáticas del cifrado: una introducción elemental , Mathematical World, 29 , American Mathematical Society, p. 237, ISBN 9780821883211
- ^ "El RSA Factoring Challenge ya no está activo" . Laboratorios RSA. Archivado desde el original el 27 de julio de 2013.
- ^ du Sautoy, Marcus (2011). Los misterios numéricos: 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" . MathWorld .