Nuevo algoritmo para ver

Escrito el 11 agosto, 2002 – 10:00 | por storm | 739 lecturas

Tres científicos hindúes han resuelto un antiguo problema matemático al idear una forma para que una computadora pueda decir rápida y definitivamente si un número es primo o no (un número primo es aquel que sólo es divisible por si mismo y por uno dando resto cero).
Los números primos juegan un rol central en la criptografía, así que idear formas rápidas para identificarlos es importante. Los algoritmos actuales son rápidos, pero siempre queda la posibilidad de que den respuestas incorrectas o que ni siquiera den una respuesta.


El Nuevo algoritmo, ideado por Manindra Agrawal, Neeraj Kayal y Nitin Saxena del Indian Institute of Technology en Kanpur — no solo garantiza una respuesta correcta sino que también lo hace en un tiempo razonable. Aunque su paper no ha sido publicado aun, lo han distribuido entre destacados matemáticos quienes dijeron sentirse emocionados por el descubrimiento.

“Esto era uno de los grandes problemas no resueltos de la teoría de la ciencia de la computación y de la teoría numérica computacional” dijo Shafi Goldwasser, un profesor de ciencias de la computación del Massachusetts Institute of Technology (MIT) y del Weizmann Institute of Science en Israel. “Es el mejor resultado que escuche en más de 10 años.”
El nuevo algoritmo no tiene aplicaciones inmediatas, dado que existen otros que son más rápidos y cuya probabilidad de error se puede reducir tanto que resulta prácticamente cero. De todas formas el nuevo algoritmo representa un gran éxito, porque según dijeron, resuelve simple y elegantemente un problema que había desafiado a muchos de los mejores investigadores en el campo por décadas. Al preguntarle porque tuvo el coraje para trabajar en un problema que había frustrado a tantos, Agrawal respondió vía e-mail: “El nuestro fue un método completamente nuevo e inexplorado. Por lo tanto eso nos dio esperanza de que podríamos tener éxito.”


El paper está posteado en la página del departamento de computación del Indian Institute of Technology (www.cse.iitk.ac.in).

Los métodos para determinar si un número es primo han cautivado a los matemáticos desde tiempos ancestrales porque al entender los números primos se podrían resolver muchos e importantes problemas matemáticos. Más recientemente, la atención se ha enfocado en pruebas que corran eficientemente en una computadora, porque estas pruebas son parte de las matemáticas subyacentes de muchos sistemas de encriptación ampliamente utilizados. La llamada prueba de “primalidad” tiene un rol crucial en el muy usado algoritmo RSA, cuya seguridad se basa en la dificultad de encontrar los factores primos de un número. RSA es usado para asegurar transacciones a través de Internet.


El domingo, los investigadores mandaron por mails un borrador del paper a docenas de matemáticos expertos y científicos computacionales. Carl Pomerance, un matematico de Bell Labs, dijo que el recibió el paper el lunes por la mañana y que determinó que era correcto.

La nota original es del Indian Times:
El paper se puede leer acá

Es muy compleja toda esa matematica, pero al principio tiene una breve historia de la búsqueda de números primos (en inglés).
Como resumen del paper les muestro el algoritmo que diseñaron

You must be logged in to post a comment.

Buscar: