Pruebas de primalidad para principiantes

Primality Testing for Beginners es un libro de matemáticas de nivel universitario sobre pruebas de primalidad , métodos para comprobar si un número dado es primo , centrado en la prueba de primalidad AKS , el primer método para resolver este problema en tiempo polinomial . Fue escrito por Lasse Rempe-Gillen y Rebecca Waldecker , y publicado originalmente en alemán como Primzahltests für Einsteiger: Zahlentheorie, Algorithmik, Kryptographie (Vieweg+Teubner, 2009). ^{[ 1 ] [ 2 ]} Fue traducido al inglés como Primality Testing for Beginners y publicado en 2014 por la American Mathematical Society , como el volumen 70 de su serie de libros Student Mathematical Library. ^{[ 2 ] [ 3 ] [ 4 ] [ 5 ]} Una segunda edición en alemán fue publicada por Springer en 2016.

El libro "Primality Testing for Beginners" tiene siete capítulos, divididos en dos partes: cuatro capítulos sobre conceptos básicos de teoría de números y teoría de la complejidad computacional , y tres sobre la prueba de primalidad AKS. ^{[ 1 ] [ 5 ]}

El capítulo 1 incluye material básico sobre teoría de números, incluyendo el teorema fundamental de la aritmética sobre la factorización única en números primos, el teorema del binomio , el algoritmo euclidiano para el máximo común divisor y la criba de Eratóstenes para generar la secuencia de números primos. El capítulo 2 inicia el estudio de los algoritmos y su complejidad, incluyendo algoritmos para cálculos básicos en aritmética, la noción de computabilidad , algoritmos de tiempo polinomial, aleatorización y tiempo polinomial no determinista . En algoritmos aleatorizados, introduce la distinción entre algoritmos de Las Vegas que siempre devuelven la respuesta correcta después de una cantidad de tiempo aleatoria (como quicksort ) y algoritmos de Monte Carlo para los que hay una pequeña probabilidad de obtener una respuesta incorrecta (ejemplificados por algoritmos basados ​​en el lema de Schwartz-Zippel para la prueba de identidad polinomial ). El capítulo 3 proporciona material adicional sobre teoría de números, incluyendo el teorema chino del resto , el pequeño teorema de Fermat y la prueba de primalidad de Fermat basada en él. También introduce el cálculo con polinomios y con aritmética modular . La primera parte del libro concluye con el capítulo 4, sobre la historia de los números primos y las pruebas de primalidad, incluyendo el teorema de los números primos (en una forma debilitada), aplicaciones de los números primos en criptografía y la ampliamente utilizada prueba de primalidad de Miller-Rabin , que se ejecuta en tiempo polinomial aleatorio. ^{[ 5 ]}

El capítulo 5 generaliza el pequeño teorema de Fermat de números a polinomios e introduce una prueba de primalidad aleatoria basada en esta generalización. El capítulo 6 proporciona los resultados matemáticos clave que respaldan la corrección de la prueba de primalidad AKS, y el capítulo 7 describe la prueba en sí. ^{[ 5 ]} Tanto la corrección como el tiempo de ejecución polinomial del algoritmo se demuestran rigurosamente. ^{[ 3 ]} Se incluyen ejercicios en cada capítulo, y una sección al final del libro proporciona las respuestas a algunos de ellos. ^{[ 1 ] [ 2 ]} Otro apéndice enumera algunos problemas sin resolver de la teoría de números. ^{[ 3 ]}

Aunque está dirigido principalmente a estudiantes universitarios de matemáticas, el libro "Primality Testing for Beginners" requiere muy pocos conocimientos previos y también puede ser adecuado para estudiantes avanzados de secundaria. ^{[ 2 ] [ 3 ]} Se basa en un programa de verano para estudiantes de este nivel, impartido por los autores en Alemania con el objetivo de introducirlos a las investigaciones recientes. ^{[ 4 ]}

Los revisores Robin Chapman y Jeffrey Ehme coinciden en que el contenido general del libro es probablemente demasiado escaso para usarlo como libro de texto principal en un curso de teoría de números de pregrado, pero que podría ser un buen complemento para dicho curso, o para un curso de criptografía. ^{[ 3 ] [ 4 ]} El revisor Frederic Green lo recomienda como una buena introducción a la investigación matemática en general, y también sugiere que los investigadores lo utilicen como referencia rápida sobre pruebas de primalidad. ^{[ 5 ]}