Estas aquiContenido / Estudios de algoritmos deterministas para generar primos
Estudios de algoritmos deterministas para generar primos
Los números primos son de una importancia vital en nuestros días, pues al final están detrás de multitud de algoritmos criptográficos que protegen nuestras comunicaciones.
Quizás la generación de primos sea una de las ramas de las matemáticas más estudiadas. Como se ha comentado, por ejemplo, en Kriptópolis, existen multitud de concursos para ver quién es capaz de generar el primo con mayor número de cifras, y concursos para demostrar propiedades....
Sin embargo, en los procedimientos reales de generación de primos, utilizados habitualmente en sistemas de criptografia de clave pública, tipo RSA, es necesario determinar si un número es primo o no, y mientras no se conozca otro procedimiento esto se realiza por algoritmos estadísticos: son los conocidos como test de primalidad.
Básicamente se le proporciona un número, se ejecuta el algoritmo y dependiendo del numero de pasadas se obtiene una mayor probabilidad de que el número sea primo. Algoritmos de este tipo son, por ejemplo, el test de Miller-Rabin, etc.
Esto es lo habitual, no obstante hay muchos osados que siguen soñando con un algoritmo determinista. Es decir, un proceso conductista que dado un número te diga si es primo o no.
Un ejemplo de este avance son los estudios del profesor Manindra Agrawal y dos de sus estudiantes del Indian Institute of Technology Kanpur. Sus estudios son revolucionarios y suponen un gran paso hacia el sueño final de un algoritmo determinista.
Versión para imprimir