El mayor número primo falso tiene 300 mil millones de dígitos

Un número 300 mil millones de cifras es el mayor seudoprimo conocido: un número que se parece a un primo, pero no lo es. Las técnicas utilizadas para encontrar este monstruo podría ayudar a mantener seguras las transacciones en línea

Los 10 primeros dígitos son 1512269972… pero no podemos poner el resto ya que el nuevo número es tan grande que escribirlo completo se comería alrededor de una tercera parte de un terabyte. «Tengo un disco duro externo que lo contiene», dice el co-descubridor Andrew Shallue, de la Illinois Wesleyan University en Bloomington. Queda así empequeñecido el número primo verdadero más grande conocido, un monstruo de 17 millones de dígitos anunciado la semana pasada.

Los números primos sólo pueden dividirse por sí mismos y por 1. Averiguar qué números son primos puede ser complicado, por lo que los matemáticos han desarrollado varios algoritmos para acelerar la búsqueda. Una simple prueba se basa en una observación del siglo 17 del matemático Pierre de Fermat, quien dijo que para cualquier número primo p y un número entero a, si se divide p-a por p, el resto es 0. Por desgracia, a veces también es cierto cuando p no es un número primo.

Encontrar falsificaciones

Hay sólo 43 de estos seudoprimos Fermat en el primer millón de números, en comparación con cerca de 80.000 números primos. Los primos forman los ladrillos de construcción básicos de la criptografía moderna, por lo que confundir un seudoprimo con un verdadero primo hace que sea fácil que alguien se robe tus secretos. Después de Fermat, los matemáticos han desarrollado pruebas más sofisticadas para reducir estos errores, pero aún surgen seudoprimos inesperadamente.

Para cazar las falsificaciones, Shallue y su colega Steven Hayman han creado un algoritmo que analiza una lista de números para encontrar un subconjunto que, al ser multiplicado entre sí, produce un objetivo particular: en este caso, un seudoprimo que pasa la prueba de Fermat. La búsqueda de los más grandes seudoprimos conocidos demuestra que el algoritmo es mucho mejor que las técnicas anteriores, dice Shallue, quien lo presentó el mes pasado en la Reunión Conjunta de Matemáticas en San Diego, California.

«Encontrar este número es, sin duda, un logro», dice Graham Jameson de la Universidad de Lancaster, Reino Unido. Sin embargo, el avance práctico es el nuevo algoritmo, que le podría decir
a los matemáticos y criptógrafos acerca de las propiedades generales de los seudoprimos, dice. «El problema más importante es establecer qué tan poco comunes son estos números.»

Fuente: New Scientist. Aportado por Eduardo J. Carletti

Más información: