Estudio sobre primalidad con el algortimo AKS

Arroyo Rodríguez, Verónica (2020). Estudio sobre primalidad con el algortimo AKS. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Description

Title: Estudio sobre primalidad con el algortimo AKS
Author/s:
  • Arroyo Rodríguez, Verónica
Contributor/s:
  • Mata Hernández, Águeda
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: June 2020
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (2MB) | Preview

Abstract

El objeto de estudio principal de este Trabajo de Fin de Grado son los números primos. Suponen una estructura fundamental no solo en el área de Teoría de Números, sino en muchos otros tales como Criptografía o Aritmética Modular debido a las numerosas aplicaciones y propiedades derivadas de ellos. Uno de los problemas principales cuando se trabaja con números primos es el estudio de su primalidad. A lo largo de la historia se han desarrollado numerosos algoritmos, pero el que se analiza en este trabajo es el primer test de primalidad cuya complejidad es polinomial. Se trata del denominado Algoritmo AKS, publicado en 2004 por Manindra Agrawal, Neeraj Kayal y Nitin Saxena en Annals of Mathematics con el título «PRIMES is in P» [1]. En el capítulo 1 se introducen conceptos de Estructuras Algebraicas y complejidad algorítmica necesarios para el posterior estudio y análisis del algoritmo AKS, cuyo desarrollo se encuentra en el Capítulo 2. En tal capítulo se detalla el algoritmo y se presenta un seguimiento paso a paso de la demostración propuesta por los autores, profundizando en ella hasta concluir su corrección. En este capítulo se presenta, además, una implementación del algoritmo en el lenguaje de programación Python, a partir de la cual se ha llevado a cabo un estudio de la complejidad del mismo. Al final del capítulo se puede encontrar otra versión del algoritmo AKS propuesta por Martin Dietzfelbinger en [8]. Los pasos del algoritmo son distintos pero ni el resultado ni la complejidad se ven alterados. El objetivo del Capítulo 3 es aportar un punto de vista diferente desde el que abordar el problema de la Primalidad: mediante algoritmos que involucren curvas elípticas. Es por ello que la primera parte del capítulo es una introducción de conceptos necesarios de curvas elípticas, y la segunda mitad aporta una idea general del test de primalidad Goldwasser-Kilian [25], basado en tales estructuras matemáticas. Finalmente, en el Capítulo 4, están desarrolladas todas las conclusiones a las que se ha ido llegando durante el desarrollo del trabajo, destacando principalmente las relativas a la complejidad del algoritmo AKS ya que, al estudiarla, se dieron discordancias en los datos obtenidos, luego en este capítulo se muestra una comparación de los resultados pertenecientes a distintos lenguajes de programación (Python, Maple y Matlab) con el fin de asegurar así la veracidad de la complejidad calculada. Se concluye el trabajo exponiendo diversas líneas futuras de investigación, la bibliografía utilizada en el desarrollo y un anexo con el código de programación de los algoritmos implementados.---ABSTRACT---The main subject of this Final Degree Project is prime numbers. They are a fundamental mathematical structure not only in the area of Number Theory, but in many others such as Cryptography and Modular Arithmetic due to the numerous applications and properties derived from them. One of the most important problems related to prime numbers is the study of primality. Throughout history, numerous algorithms have been developed to address this problem, but the one analyzed in this project is the first algorithm whose complexity is of class P. That is the well-known AKS Algorithm, published in 2004 by Manindra Agrawal, Neeraj Kayal and Nitin Saxena in Annals of Mathematics with the title «PRIMES is in P» [1]. Chapter 1 presents the concepts of Algebraic Structures and Algorithmic Complexity necessary for the subsequent study and analysis of the AKS algorithm. In Chapter 2, the AKS algorithm is described in detail, including the steps followed by the authors to prove its correctness. Chapter 2 also contains an implementation of the algorithm in the programming language “Python”, which has been used to carry out a study of its complexity. At the end of the chapter, another version of the AKS algorithm is explained. It was proposed by Martin Dietzfelbinger in [8] and despite the steps followed are different, the results and complexity are the same. The main purpose of Chapter 3 is to provide a different point of view to the primality testing problem: using elliptic curve algorithms. The first half of the chapter introduces some necessary concepts of elliptic curves, and the second half provides a general outline of the Goldwasser-Kilian primality test [25], based on such mathematical structures. Finally, the main results reached during the development of this project are found in Chapter 4. In particular, those related to the complexity of the AKS algorithm since, while studying it, there were discordances in the data obtained. Therefore, to ensure that the calculated complexity is correct, a comparison of the results obtained from different programming languages (in particular, Python, Maple and Matlab) is provided. This project is concluded exposing the future work, the bibliography used in the development and an annex with the programming code of the implemented algorithms.

More information

Item ID: 63147
DC Identifier: http://oa.upm.es/63147/
OAI Identifier: oai:oa.upm.es:63147
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 22 Jul 2020 10:48
Last Modified: 22 Jul 2020 10:48
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM