Prueba de pepino

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 5 de julio de 2015; las comprobaciones requieren 5 ediciones .

pseudocódigo

b\,\flecha izquierda\,3

DESDE HASTA CAD

yo=1

2^{n}-1

b\,\flecha izquierda\,b^{2}{\bmod {F_{n))}

SI ENTONCES

b\equiv -1{\pmod {F_{n))}

RETORNO " -simple"

F_{n}

DE LO CONTRARIO RETORNO "-compuesto "

F_{n}

Prueba de Pepin : una prueba de primalidad para los números de Fermat La prueba lleva el nombre del matemático francés Theophilus Pepin. $F_{n}.$

Descripción

El número debe elevarse a una potencia (en algunos algoritmos esto se implementa mediante una serie de elevaciones sucesivas al cuadrado) módulo . Si el resultado es módulo comparable con −1, entonces es primo; de lo contrario, es compuesto. $3$ $(F_{n}-1)/2=2^{{2^{n}-1}}$ $2^{n}-1$ $F_{n}$ $F_{n}$ $F_{n}$

Este enunciado es el siguiente teorema:

teorema _ Para n ≥ 1 , el número de Fermat es primo si y solo si . $F_{n}=2^{{2^{n}}}+1$ $3^{{(F_{n}-1)/2}}\equiv -1{\pmod {F_{n}}}$

Prueba

Supongamos que la comparación es correcta. Entonces se cumple la condición del teorema de Lucas para , por lo tanto, es un número primo. Por el contrario, sea un número primo. Como es un número par, entonces , por lo tanto, . Pero , entonces el símbolo de Legendre es −1. Por lo tanto, 3 no es un módulo de residuo cuadrático . La comparación requerida se deriva del criterio de Euler . ■ $n=F_{n}$ $un=3$ $F_{n}$ $F_{n}$ $2^{n}$ $2^{{2^{n}}}\equiv 1{\pmod {3}}$ $F_{n}\equiv 2{\pmod {3}}$ $F_{n}\equiv 1{\pmod {4}}$ $\left({\frac 3{F_{n))}\right)$ $F_{n}$

Variaciones y generalizaciones

La prueba de Pepin es un caso especial de la prueba de Luc .

El número 3 en la prueba de Pepin se puede reemplazar por 5, 6, 7 o 10 (secuencia A129802 en OEIS ), que también son raíces primitivas módulo cada primo de Fermat.

Se sabe que Pepin dio un criterio con el número 5 en lugar del número 3. Prot y Lucas notaron que también se puede usar el número 3.

Complejidad computacional

Dado que la prueba de Pepin requiere elevar al cuadrado el módulo , se ejecuta en un tiempo polinomial en longitud pero superexponencial en longitud n ( ). $2^{n}-1$ $F_{n}$ $F_{n},$ $\log n$

Historia

Debido al gran tamaño de los números de Fermat, la prueba de Pepin se usó solo 8 veces (sobre números de Fermat, cuya simplicidad aún no ha sido probada ni refutada) [1] [2] [3] . Mayer, Papadopoulos y Crandall incluso sugirieron que tomaría varias décadas completar las pruebas de Pepin en más números de Fermat, porque el tamaño de los números de Fermat aún no explorados es muy grande [4] . En noviembre de 2014, el número no verificado más pequeño de Fermat es , que contiene 2 585 827 973 dígitos decimales. En el hardware estándar, la prueba de Pepin tardaría miles de años en probar tal número, y existe una gran necesidad de nuevos algoritmos para tratar con números de Fermat tan grandes. $F_{{33}}$

Año	Investigadores	Número de Fermat	resultado de la prueba de Pepin	¿Conseguiste encontrar el divisor?
1905	James S. Morehead y Alfred Western	$F_{{7}}$	compuesto	Sí (1970)
1909	James S. Morehead y Alfred Western	$F_{{8}}$	compuesto	Sí (1980)
1952	Rafael M. Robinson	$F_{{10}}$	compuesto	Sí (1953)
1960	GA Paxon	$F_{{13}}$	compuesto	Sí (1974)
1961	John Selfridge y Alexander Hurwitz	$F_{{14}}$	compuesto	Sí (2010)
1987	Duncan Buell y Geoffrey Young	$F_{{20}}$ [5]	compuesto	No
1993	Richard Crandall, J. Dignas, S. Norrie y Geoffrey Young	$F_{{22}}$ [6]	compuesto	Sí (2010)
1999	Ernst W. Mayer, Jason S. Papadopoulos y Richard Crandall	$F_{{24}}$	compuesto	No

Notas

↑ Conjetura 4. Los números primos de Fermat son finitos - Historia de las pruebas de Pepin, según Leonid Durman . Archivado el 24 de septiembre de 2015 en Wayback Machine .
↑ Wilfrid Keller: Fermat factoring status Archivado el 10 de febrero de 2016. (Inglés)
↑ RM Robinson (1954): Números de Mersenne y Fermat. Archivado el 26 de enero de 2015 en Wayback Machine .
↑ Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), El vigésimo cuarto número de Fermat es compuesto . Archivado el 8 de octubre de 2014 en Wayback Machine .
↑ Jeff Young & Duncan A. Buell (1988): El vigésimo número de Fermat es compuesto . Archivado el 4 de septiembre de 2014 en Wayback Machine , 261-263. (Inglés)
↑ R. Crandall, J. Doenias, C. Norrie y J. Young (1995): El vigésimo segundo número de Fermat es compuesto . Archivado el 29 de noviembre de 2014 en Wayback Machine , 863-868. (Inglés)

Literatura

P. Pepín. Sur la formule // Comptes Rendus Acad. ciencia París. - 1877. - Nº 85 . - S. 329-333 . $2^{{2^{n}}}+1$
Crandall R., Pomerance K. . números primos . - 2011. - S. 198 -200.

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