| Title | Nuevo algoritmo para comprobar si un número es primo | |
| Date | Jueves, 08 Agosto de 2002, 20:49h | |
| Author | Baranda | |
| Topic | ||
| from the cálculos-altos dept. | ||
JuanjoAI, que no tenía tiempo de publicarlo, ha llamado mi antención sobre un artículo en el New York Times (requiere suscripción gratuita) en el que se habla sobre un nuevo método para resolver si un número dado es primo o no. Lo nuevo del método está en que, con un algoritmo de complejidad polinomial, determina con certeza absoluta si un número es primo. Por lo que yo sé, los algoritmos rápidos actuales determinan si un número es primo sólo con una cierta probabilidad (normalmente muy alta), y no siempre pueden decidir en tiempo finito. Este método pone finalmente a los números primos en P (algoritmos de complejidad polinomial). A pesar de todo esto, es importante el detalle de que el algoritmo propuesto no es más rápido que los ya conocidos (por lo que en principio no sirve para romper más rápidamente métodos de cifrado que usan números primos grandotes). Pero los matemáticos, al parecer, están muy excitados por lo elegante del método. El artículo donde se describe "PRIMES is in P" ha sido escrito por Manindra Agrawal, Neeraj Kayal y Nitin Saxena, del Indian Institute of Technology (Kanpur, India).
| Links |
printed from Barrapunto, Nuevo algoritmo para comprobar si un número es primo on 2018-06-16 04:38:02