Los algoritmos para encontrar números primos se remontan al menos a la antigua Grecia, donde los matemáticos utilizaban un enfoque directo conocido como la Criba de Erastótenes. La criba de Erastóstenes funciona de la siguiente manera: Para encontrar todos los primos menores que n, se empieza por escribir todos los números del 1 al n en secuencia. A continuación, tache todos los números que sean múltiplos de 2, además de él mismo (
4,6,8,10,12, etc.). Tome el siguiente número más pequeño que no haya sido tachado (en este caso, el 3), y tache todos los múltiplos de ese número (6,9,12,15). Repita la operación y los números que quedan al final son los primos. ... aunque la criba de Erastótenes es eficaz, no es eficiente. Si quieres comprobar si un número concreto es primo... entonces seguir la estrategia de la criba requiere intentar dividirlo por todos los primos hasta su raíz cuadrada (porque un número que tiene raíz cuadrada entera no es primo) Para comprobar si un número de seis dígitos es primo habría que dividirlo entre los 168 primos menores que 1.000, lo que no está tan mal. Pero comprobar un número de doce dígitos implica dividirlo entre los 78.498 primos menores que un millón, y toda esa división empieza a descontrolarse rápidamente...
Durante milenios, se creyó que el estudio de los números primos era, como dijo G. H. Hardy, "una de las ramas más obviamente inútiles" de las matemáticas. Sin embargo, en el siglo XX se convirtió en algo práctico, y pasó a ser fundamental para la criptografía y la seguridad en internet. Resulta que es mucho más fácil multiplicar los números primos entre sí que volver a descomponerlos en sus factores. Con primos lo suficientemente grandes -por ejemplo, de mil dígitos- la multiplicación puede hacerse en una fracción de segundo, mientras que la descomposición en factores podría llevar literalmente millones de años, lo que da lugar a lo que se conoce como una 'función unidireccional'. En la encriptación moderna, por ejemplo, los números primos secretos que sólo conocen el remitente y el destinatario se multiplican para crear enormes números compuestos que pueden transmitirse públicamente sin temor, ya que la factorización del producto llevaría a cualquier espía demasiado tiempo como para que valga la pena intentarlo. Así, prácticamente todas las comunicaciones seguras en línea -ya sea el comercio, la banca o el correo electrónico- comienzan con la búsqueda de números primos
No hay comentarios:
Publicar un comentario