Matemático peruano mejora un método de los antiguos griegos para producir números primos

En 2013, el matemático peruano Harald Helfgott ganó fama mundial cuando resolvió un problema de 271 años de antigüedad: la llamada “conjetura débil de Goldbach”, según la cual todo número impar mayor que cinco puede expresarse como la suma de tres números primos – tal como se puede observar en estos ejemplos:  2 + 2 + 3= 7 ó 19 + 13 + 3=35–.

Pero Helfgott, de 38 años, se remontó incluso más atrás en el tiempo y concibió una versión mejorada de la “criba de Eratóstenes”, un popular método para encontrar números primos que se formuló en la antigua Grecia hacia el año 240 a.C. La variante propuesta reduce el requerimiento de espacio físico en la memoria de computadoras, lo cual podría reducir el tiempo de ejecución de programas destinados a hacer ese cálculo.

Los números primos son algo así como “átomos de la matemática” que solo pueden dividirse por sí mismos y por la unidad,  y Eratóstenes, un matemático, astrónomo y geógrafo que fue director de la Biblioteca de Alejandría y se hizo famoso por calcular la circunferencia de la Tierra, también propuso un método práctico para identificarlos: la “criba” o filtro. “Como a tantos otros niños, a mí me lo enseñaron a los 10 años como tablita en la escuela primaria”, dice Helfgott, quien actualmente es investigador del Centro Nacional de la Investigación Científica (CNRS) de Francia y de la Universidad de Gotinga, en Alemania.

Para determinar con esa “tablita” o criba todos los primos entre 1 y 100, por ejemplo, hay que escribir la lista de números en ese intervalo para luego empezar a tachar siguiendo un orden: primero, los múltiplos de 2 (excepto el 2); luego, los múltiplos de 3, excepto el 3; y así sucesivamente, arrancando por el siguiente número que no hubiera sido tachado. Los números que “sobreviven” a ese procedimiento serán los primos. El método se puede formular como algoritmo y ejecutar rápido con computadoras.

Mientras trabajaba en la corrección de las pruebas de un libro con la demostración completa de la conjetura de Goldbach, Helfgott dice que empezó a pensar “quizás demasiado tiempo” en el problema de la criba de Eratóstenes. En particular, su requerimiento de espacio o memoria. “Las computadoras hoy en día son muy veloces y también pueden hacer cálculos en paralelo. Pero la memoria todavía es limitada”, explica Helfgott a Scientific American.

El matemático Jean Carlos Cortissoz Iriarte, doctorado en la Universidad de Cornell, en Nueva York, Estados Unidos, y profesor de la Universidad de los Andes, en Bogotá, Colombia, señala que dos factores a considerar para saber qué tan bueno es un algoritmo son la cantidad de operaciones por bit dado un dato de entrada (por ejemplo, 100) y el número de bits que deben guardarse en memoria mientras se ejecutan sus instrucciones.

“La criba de Eratóstenes, en cuanto a número de operaciones por bit a realizar se refiere, es relativamente eficiente. Crece de manera proporcional al tamaño del intervalo considerado. Pero si nos fijamos en lo que hay que mantener en memoria por cada paso del algoritmo que se ejecute, para intervalos [números] muy grandes, la criba deja de ser eficiente”, explica.

Ahora, inspirado en trabajos combinatorios sobre el método del círculo, una técnica analítica centenaria, Helfgott logró modificar la criba de Eratóstenes para que funcione con menor espacio físico de memoria. En términos matemáticos: en lugar de necesitar un espacio N, ahora le alcanza con aproximadamente la raíz cúbica de N. “Para calcular todos los primos hasta un trillón, la versión modificada de la criba requiere algunos millones de bits en lugar de mil millones de bits”, ejemplifica Helfgott.

Las ideas generales de la propuesta fueron presentadas en julio en el XXI Coloquio Latinoamericano de Álgebra, realizado en Buenos Aires, y en SINAPSIS 2016: un encuentro de científicos peruanos radicados en Europa que se celebró en París.

Para entender la ventaja de la nueva criba, Cortissoz plantea una analogía.  “Hagamos de cuenta que usted es una computadora y para almacenar en memoria utiliza hojas de papel. Si para calcular los primos entre 1 y 1.000.000 requiere 200 resmas de papel (10.000 hojas), con el algoritmo propuesto por Helfgott le alcanzaría con la quinta parte de una resma (un centenar de hojas)”, destaca.

Aunque reducir el requerimiento de espacio generalmente implica ciertos sacrificios “menores” en la velocidad teórica del algoritmo, Helfgott cree que, en ciertos rangos, ese déficit podría ser compensado o superado por la posibilidad de usar de manera prioritaria o exclusiva la memoria caché, que es más pequeña pero más rápida que la memoria principal o RAM. “Depende de la aplicación”, apunta.

Existen otras cribas o algoritmos para identificar números primos. Pero Helfgott enfatiza que una virtud diferencial de la criba de Eratóstenes es que, además, permite realizar otras operaciones matemáticas, como la factorización: una técnica que descompone cualquier número en el producto de números primos y es la base de los procedimientos criptográficos para codificar información de manera segura. Por ejemplo, para la realización de transferencias bancarias electrónicas o el uso de tarjeta de crédito para compras online.

“Factorizar se ha vuelto un elemento clave de la civilización contemporánea”, subraya Helfgott. Eratóstenes jamás lo hubiera imaginado. 

Fuente: Scientific American