Primalidad

Abstract

The aim of this work is to present a deterministic method that establishes with absolute certainty whether a given number is a prime or not. In order to give an answer to this question, we will study in depth the AKS algorithm, which gives a theoretical polynomial–time solution to the Primality problem. The first chapter is devoted to give an introduction of what being a prime means, as well as presenting the Primality problem. We will talk about some subjects, from both Mathematics and Computer Science, where this problem plays an essential role. Moreover, we will make a distinction between probabilistic primality tests and deterministic primality tests, giving an example for each case. In the second chapter, we will introduce some notations that we will use through the text. In addition to this, we will also show and recall several previous concepts that will help us in the sequel. During the third chapter we will be presenting the AKS algorithm as well as developing the ideas and mathematical concepts behind this test that verifies its correctness. We will use not only modular arithmetic but also group theory in order to build some results that allow us to prove the primality of a certain number in a satisfactory way. Throughout the fourth chapter we will be studying the complexity of AKS algorithm using basic notions of complexity theory. Eventually, in the last chapter we will give an example of the AKS algorithm, providing us a detailed study of each step.

El objetivo de este trabajo es exponer un método determinístico para, dado un cierto entero 𝑛�, poder afirmar con total certeza si es o no primo. Para ello estudiaremos en profundidad el algoritmo determinístico AKS [PinP] que da una solución computacionalmente eficaz (esto es, en tiempo logarítmico) al problema de la Primalidad. Dedicaremos el primer capítulo a introducir el concepto de número primo, así como el problema de la Primalidad. Veremos algunas áreas, tanto de las matemáticas como de las ciencias de la computación, en las que tanto dicho problema como los números primos en sí mismos juegan un papel fundamental. Por otra parte haremos una distinción entre tests de primalidad probabilísticos y tests de primalidad determinísticos, tomando algunos algoritmos como ejemplo en cada caso. En el segundo capítulo introduciremos algunas notaciones que adoptaremos a lo largo del texto, además de exponer o recordar diversos conceptos previos para el desarrollo de nuestro tema. A lo largo del tercer capítulo, expondremos el algoritmo AKS y desarrollaremos las ideas y conceptos matemáticos que se encuentran detrás de él y que verifican su corrección. Haremos uso de la aritmética modular y de la teoría de grupos para construir una serie de resultados que permitan demostrar la primalidad de un cierto número de manera satisfactoria. Siguiendo con el algoritmo AKS, en el cuarto capítulo se estudia la complejidad del mismo, haciendo uso de resultados básicos de la teoría de la complejidad. Finalmente, en el último capítulo emplearemos el algoritmo AKS para determinar la primalidad de un cierto valor 𝑛�, haciendo un estudio detallado de cada paso.