Prueba de granja

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 3 de noviembre de 2015; las comprobaciones requieren 7 ediciones .

La prueba de primalidad de Fermat en teoría de números es una prueba de primalidad para un número natural n basada en el Pequeño Teorema de Fermat .

Contenidos

Si n es primo , entonces satisface la comparación para cualquier a que no sea divisible por n . $a^{n-1} \equiv 1 \pmod n$

Realizar una comparación es una señal necesaria, pero no suficiente, de que un número es primo. Es decir, si hay al menos un a para el cual , entonces el número n es compuesto; en caso contrario, no se puede decir nada, aunque aumentan las posibilidades de que el número sea primo. Si se hace una comparación para un número compuesto n , entonces se dice que el número n es pseudoprimo en base a . Cuando se prueba la primalidad de un número mediante la prueba de Fermat, se eligen varios números a . Cuanto mayor sea el número de a , por lo que , mayor será la probabilidad de que el número n sea primo. Sin embargo, hay números compuestos para los que se realiza la comparación de todos los coprimos con n : estos son los números de Carmichael . Los números de Carmichael son infinitos , el número de Carmichael más pequeño es 561. Sin embargo, la prueba de Fermat es bastante efectiva para detectar números compuestos. $a^{n-1} \equiv 1 \pmod n$ $a^{n-1} \not\equiv 1 \pmod n$ $a^{n-1} \equiv 1 \pmod n$ $a^{n-1} \equiv 1 \pmod n$ $a^{n-1} \equiv 1 \pmod n$

Velocidad

Cuando se utilizan algoritmos de módulo de exponenciación rápida , se estima que el tiempo de ejecución de la prueba de Fermat para una a es O (log 2 n × log log n × log log log n ), donde n es el número que se está probando. Por lo general, se realizan varias comprobaciones con diferentes a .

Literatura

Vasilenko O. N. Algoritmos teóricos de números en criptografía, MTsNMO, 2003
Trost E. - Primzahlen / Números primos - M .: GIFML, 1959, 135 páginas
Thomas Cormen , Charles Letherston , Ronald Rivest , Clifford Stein . Sección 31.8: Pruebas de primalidad // Introducción a los algoritmos . - Segunda edicion. — Prensa del MIT; McGraw-Hill, 2001, págs. 889-890. — ISBN 0-262-03293-7 . (Ruso)

Enlaces

¿Es este número primo? // Círculo de Matemáticas de Berkeley 2002-2003
Prueba de Fermat // Algoritmos utilizados en criptosistemas asimétricos. criptowiki.net

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin