Número semiprimo: definición, ejemplos y propiedades

Definición y ejemplos

Formalmente, n es semiprimo si n = p*q, donde p y q son primos, no necesariamente distintos. Entre los ejemplos pequeños están 4 = 2×2, 6 = 2×3, 9 = 3×3, 10 = 2×5, 14 = 2×7 y 15 = 3×5. Como hay infinitos números primos, hay infinitos semiprimos; por ejemplo, todo número de la forma 2p, con p primo, es un semiprimo.

Propiedades elementales

Los semiprimos tienen una estructura de divisores muy restringida. Si n = p^2 es el cuadrado de un primo, tiene exactamente tres divisores positivos: 1, p y n. Si n = p*q con p ≠ q, tiene exactamente cuatro divisores positivos: 1, p, q y n. En términos del número de factores primos, los semiprimos son precisamente los enteros para los que el número total de factores primos, contados con multiplicidad, es dos (a menudo se denota Ω(n)=2).

Historia y papel en la criptografía

La aritmética de los semiprimos se ha estudiado desde hace mucho tiempo en la teoría analítica y multiplicativa de números. En la informática moderna son importantes porque muchos sistemas criptográficos de clave pública dependen de la dificultad práctica de factorizar semiprimos grandes. El criptosistema RSA, por ejemplo, utiliza un módulo formado por el producto de dos primos grandes; la hipótesis de seguridad es que recuperar los dos factores primos a partir de ese producto es computacionalmente difícil. Véanse también las discusiones generales sobre criptografía para contexto.

Clases especiales y distinciones

Se distinguen ciertas subclases de semiprimos por razones teóricas o criptográficas. Por ejemplo, un entero de Blum es un semiprimo p*q con p y q primos distintos, ambos congruentes con 3 módulo 4; estos números tienen propiedades algebraicas especiales que se usan en algunos protocolos. También conviene distinguir los semiprimos de los primos, que tienen exactamente dos divisores, y de los k-casi primos de orden superior, que tienen más de dos factores primos.

Cálculo y factorización

Determinar si un entero grande dado es semiprimo requiere encontrar sus factores primos o demostrar que tiene más o menos de dos factores primos. Entre los métodos sencillos están la división por prueba y los cribados con rueda; en casos grandes se emplean algoritmos de factorización más avanzados. El estudio de los semiprimos enlaza hechos elementales sobre divisores con preguntas más profundas sobre la distribución y la complejidad algorítmica en teoría de números. Para ampliar, véanse recursos sobre teoría de números y material introductorio sobre factorización en primos, como aritmética entera básica o la estructura multiplicativa general. También hay referencias y panoramas adicionales en textos estándar e introducciones en línea a la teoría de los primos y la factorización.