Util Monster
Gratis
Prueba de primalidad · Factorización · Generación de primos
Un número primo es un número natural mayor que 1 que no tiene divisores positivos aparte de 1 y de sí mismo. Ejemplos: 2, 3, 5, 7, 11, 13... Todos los primos, excepto 2, son impares. Los primos son los "átomos de los números".
Un algoritmo antiguo desarrollado por el matemático griego Eratóstenes alrededor del 240 a. C. Encuentra eficientemente todos los primos hasta n marcando de forma iterativa los múltiplos de cada primo como compuestos.
Los primos gemelos son pares de primos que difieren en 2: (3,5), (5,7), (11,13), (17,19)... Sigue siendo un problema sin resolver si existen infinitos primos gemelos.
• Cifrado RSA: seguridad basada en la dificultad de factorizar números grandes • Funciones hash: las tablas hash de tamaño primo reducen las colisiones • Generación de números aleatorios: primos en algoritmos PRNG • Naturaleza: los ciclos de vida de las cigarras usan números primos
Un número primo es un número natural mayor que 1 que no tiene divisores salvo 1 y sí mismo. El primo más pequeño es 2, el único primo par. Secuencia: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... El matemático griego Euclides demostró alrededor del 300 a. C. que existen infinitos primos. A los primos se les llama "átomos de los números" porque todo entero > 1 se factoriza de manera única en primos (teorema fundamental de la aritmética). Ejemplos: 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5.
El método más simple comprueba la divisibilidad por todos los números de 2 a n-1, pero es ineficiente. Una mejora consiste en probar solo de 2 a √n, porque si n = a × b, entonces a ≤ √n o b ≤ √n. Para 101: √101 ≈ 10.05, así que solo se comprueban 2, 3, 5, 7. La prueba probabilística de Miller-Rabin maneja números muy grandes con eficiencia. AKS (2002) es el primer algoritmo determinista de tiempo polinómico. La criptografía moderna usa cientos de dígitos, por lo que requiere pruebas eficientes.
Desarrollado por el matemático griego Eratóstenes alrededor del 240 a. C. Proceso: ① Lista los números del 2 a n. ② Marca 2 como primo y elimina sus múltiplos (4,6,8,10...). ③ El siguiente número sin marcar, 3, es primo, y se eliminan sus múltiplos. ④ Continúa con 5, 7, etc. hasta √n. ⑤ Los números restantes son primos. Para n=30: los primos son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Complejidad temporal: O(n log log n). Puede encontrar todos los primos menores de 1 millón en segundos.
La factorización en primos expresa un número como producto de primos. Según el teorema fundamental, todo entero > 1 tiene una factorización única. Método: ① Empieza con el primo más pequeño, 2. ② Divide repetidamente entre 2 hasta que ya no sea divisible. ③ Prueba los siguientes primos 3, 5, 7... ④ Continúa hasta que el cociente sea 1. Ejemplo 360: 360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1. Resultado: 360 = 2³×3²×5. Aplicaciones: cálculo de MCD/MCM, reducción de fracciones, seguridad RSA.
Los primos gemelos difieren en 2: (3,5), (5,7), (11,13), (17,19), (29,31)... La conjetura de los primos gemelos afirma que existen infinitos, pero sigue sin demostrarse. En 2013, Yitang Zhang demostró que existen infinitos pares de primos que difieren en ≤70 millones; después se redujo a 246. La conjetura de Goldbach (1742): todo número par > 2 es suma de dos primos. Ejemplos: 4=2+2, 6=3+3, 8=3+5, 10=5+5. Verificada hasta 4×10¹⁸, pero aún no se ha demostrado.
El cifrado RSA, base de la seguridad de internet, se apoya en que multiplicar es fácil, pero factorizar primos grandes es difícil. Generación de claves: ① Elige primos grandes p, q (1024+ bits cada uno). ② Calcula n = p×q (público). ③ Calcula φ(n) = (p-1)(q-1). ④ Elige un exponente público e coprimo con φ(n) (normalmente 65537). ⑤ Calcula el exponente privado d tal que e×d ≡ 1 (mod φ(n)). Clave pública: (n,e), clave privada: (n,d). Cifrar: C = M^e mod n, descifrar: M = C^d mod n. Factorizar n para encontrar p,q rompería el cifrado, pero factorizar cientos de dígitos lleva millones de años. Otras aplicaciones: tamaños de tablas hash primos reducen colisiones, los ciclos 13/17 años de las cigarras evitan el solapamiento con depredadores, ritmos primos en la música.