Algoritmos de factorización de números enteros

Clavo López, Miguel
Lozano Rojo, Álvaro (dir.) ; Martín Morales, Jorge (dir.)

Universidad de Zaragoza, CIEN, 2023
Departamento de Matemáticas, Área de Algebra

Graduado en Matemáticas

Resumen: Una explicación del algoritmo de factorización de Lenstra basado en curvas elípticas y de cómo éste se basa en el algoritmo p-1 de Pollard.
A partir de las bases de la aritmética modular se demuestra el pequeño teorema de Fermat, y con éste se explica cómo funciona el algoritmo de Pollard y por qué éste es especialmente bueno factorizando números tales que sus factores primos menos 1 se factorizan en primos muy pequeños.
A continuación se explican las bases de la teoría de grupos y del teorema de Lagrange, que es una generalización del teorema de Fermat. Una vez se define grupo se comprueba que los puntos de una curva elíptica sobre un cuerpo forman un grupo. El algoritmo de Lenstra consiste en realizar operaciones sobre puntos de una curva elíptica que no está definida sobre un cuerpo sino sobre la clase de equivalencias módulo el número que queramos factorizar, de manera que no es un grupo. En el momento en que no se puedan sumar dos puntos de la curva, se habrá obtenido un factor del número que queremos factorizar.

Tipo de Trabajo Académico: Trabajo Fin de Grado