Emulador software para el cálculo de primos de Mersenne

Abstract

El objetivo de este proyecto consiste en el desarrollo de un emulador software para el cálculo de primos de Mersenne, en concreto para la resolución de los problemas que conlleva el tratamiento de números de una magnitud tan grande como los mencionados primos. El estudio de los números primos de Mersenne es importante dado que por sus propiedades características son especialmente útiles en distintas aplicaciones, especialmente criptográficas, como el protocolo RSA o la criptografía basada en curvas elípticas. La presente memoria se halla dividida en siete capítulos, cada uno de los cuales describiremos brevemente a continuación. El primer capítulo incluye la introducción, que contiene información general acerca del tema que nos ocupa, datos históricos sobre los descubrimientos de los números primos de Mersenne, así como su definición y algunas de sus propiedades características. Además, se habla acerca de los problemas que se pretenden resolver con el trabajo elaborado y las motivaciones del mismo. En el segundo capítulo se puede encontrar información acerca de los antecedentes que han servido como base a este proyecto. Datos acerca del proyecto GIMPS, y de programas ya desarrollados que guardan relación con nuestro problema, como Prime95 o Mprime. En el tercer capítulo se explica en detalle la arquitectura del emulador desarrollado, el sistema de representación empleado, una descripción detallada de la biblioteca de funciones desarrollada para construir el emulador y las mejoras propuestas al diseño inicial del mismo. El cuarto capítulo versa sobre CUDA y su uso en este proyecto, este capítulo incluye datos tanto de la arquitectura CUDA, su funcionamiento y algunas nociones básicas de su lenguaje de programación. El quinto capítulo muestra y discute los resultados obtenidos con el emulador y sus diversas optimizaciones. El sexto capítulo hace referencia a las conclusiones obtenidas de la investigación y a las vías de investigación de trabajo futuro que proponemos en caso de continuar con este proyecto, como son el uso de una aritmética RNS, el uso del estándar MPI o el uso de arquitecturas más modernas que soporten CUDA. Por último el séptimo capítulo contiene la bibliografía consultada para la elaboración de este proyecto. [ABSTRACT] The objective of this project consists of developing a Software Emulator focused on searching Mersenne Primes, particularly addressing the tremendous problems associated with such huge numbers, namely: precision and performance. The study of Mersenne primes is important due to their peculiar properties, that are specially useful in some cryptographic applications, such as the RSA protocol or the ECC (Elliptic Curve Criptography). This report is divided in seven chapters, which will be described in the following paragraphs. The first chapter includes the introduction, which contains generic information about the subject that will be studied, history about Mersenne primes discoveries, their definition and some of their special properties. Besides, this chapter deals with the problems that we expect to solve and the motivations that caused this work to be done. The second chapter contains information about previous work that support this project. Information concerning project GIMPS, and other programmes belonging to the state of the art and which are related to our work, such as Prime95 or Mprime, is described in this chapter. The third chapter will explain the emulator's architecture, data representation, and a description about the library implemented as well as the improvements proposed over the baseline design. The fourth chapter is about CUDA and its use in this project. Besides, it includes information about CUDA architecture, its way of working and some basic ideas about its programming language. The fifth chapter shows and discusses the results obtained with the baseline version of the emulator, as well as with its different optimizations. The sixth chapter gives some remarks about the project. Moreover, it describes our suggestions for continuing this work in the future, as for example: the utilization of the Residue Number System (RNS), the MPI standard or the use of the most up-to-date CUDA architectures. Finally, the seventh chapter contains the bibliography consulted to develop this project.