Paralelismo para la resolución de cuadrados mágicos formados por números primos

Abstract

Por la sencillez de su planteamiento y sus curiosas propiedades, los cuadrados mágicos han sido objeto de estudio y admiración por los matemáticos durante muchos siglos. En este documento describimos un estudio sobre la composición de cuadrados mágicos formados por números primos. La composición de este tipo de cuadrados es compleja porque no existe un método determinista, es decir, una heurística de formación de nuevos cuadrados. Por ejemplo, en un cuadrado relativamente pequeño, de tamaño 7x7, formado por 49 elementos tendríamos las siguientes combinaciones diferentes: 49! = 6x1062. Esto dificulta su tratamiento computacional. Inspirado por el cuadrado mágico del prisionero (1), y aprovechando las capacidades de cálculo que ofrece la computación paralela, se formula un modelo denominado CCMSFP (Creador de Cuadrados Mágicos Superanidados Formados por Primos) para componer cuadrados mágicos de gran tamaño compuestos por primos. Asimismo, la inclusión de una nueva restricción, el anidamiento, simplifica el espacio de búsqueda al añadir una nueva restricción, permitiendo acelerar el proceso a la hora de ordenar los primos en el cuadrado. Los resultados obtenidos tras la implementación de CCMSFP reducen el número de combinaciones probadas para el 7x7 a 2x107. En este trabajo se proponen dos implementaciones para solucionar cuadrados mágicos formados por primos. La primera variante del algoritmo permite componer cuadrados de gran orden en un tiempo reducido. Por ejemplo, un cuadrado de tamaño 17x17 toma un tiempo menor de 10 segundos. Además, encuentra una gran cantidad de cuadrados con las mismas características, pero de menor tamaño durante el proceso de ejecución. La segunda variante del algoritmo funciona exclusivamente para los cuadrados de tamaño 7x7 y permite asegurar, para una combinación de pares, si existe una solución. El algoritmo CCMSFP irrumpe como un método inédito para construir cuadrados mágicos compuestos por primos. Sus principales características involucran una eficacia temporal muy alta y el uso de la plataforma OpenMP como marco computacional. La utilización de este algoritmo podría tener un impacto en la ciencia de la encriptación e incluso abrir nuevas vías para la resolución de la teoría de los números primos.