Números primos, MCD y MCM · Lección 8 de 10
Primos y criptografía
Entender por qué la dificultad de factorizar protege internet.
Antes de empezar, una de repaso
Recordar algo cuesta más que releerlo, y por eso funciona mejor. Esta pregunta es de una lección anterior.
Una operación fácil de hacer y difícil de deshacer
Multiplicar dos primos grandes es trivial para un ordenador. Recuperar los dos factores a partir del producto no se sabe hacer rápido, y llevaría más tiempo del que lleva existiendo el universo con números suficientemente grandes.
Las funciones con esa asimetría se llaman de un solo sentido, y son la base de la criptografía moderna.
Cómo se usa
En RSA, la clave pública contiene el producto de dos primos enormes y la privada, los factores. Cualquiera puede cifrar; solo quien conoce los factores puede descifrar.
Cada vez que aparece un candado en el navegador, hay aritmética de primos funcionando por debajo.
Nadie ha demostrado que sea difícil
No se conoce ningún algoritmo rápido para factorizar, pero tampoco se ha demostrado que no exista. Toda la seguridad se apoya en que nadie lo ha encontrado.
Y un ordenador cuántico suficientemente grande sí podría hacerlo, con el algoritmo de Shor. Por eso se está migrando ya a criptografía poscuántica: no es un problema teórico, es una fecha de caducidad.
Practica
Cada ejercicio se genera con números nuevos y lo corrige el mismo motor que mueve las calculadoras del sitio. La lección se da por dominada al acertar 4 de los últimos 5.
¿Quieres comprobar tus propios números? Esta calculadora resuelve lo mismo paso a paso: Factores primos.