Test de Pépin

Test de Pépin

En matemáticas, el test de Pépin (por el matemático francés P. Pépin) es un test de primalidad que se puede emplear para determinar si un número de Fermat es primo. Es una variante del test de Proth.

Contenido

Descripción del test

Sea F_n=2^{2^n}+1 el n-ésimo número de Fermat. El test de Pépin establece que para cada n > 0,

Fn es primo si y sólo si 3^{(F_n-1)/2}\equiv-1\pmod{F_n}.

La expresión 3^{(F_n-1)/2} se puede evaluar módulo Fn elevándolo repetidamente al cuadrado. Esto permite que el test tenga un tiempo de ejecución polinómico, es decir, en principio se trata de un algoritmo rápido. Sin embargo, los números de Fermat crecen tan rápidamente que sólo se pueden evaluar unos pocos en un intervalo de tiempo razonable.

También pueden emplearse otras bases en lugar de 3, por ejemplo, 5, 6, 7 ó 10 (A129802).

Demostración de que el test funciona

Para la demostración en un sentido, se parte de la congruencia

3^{(F_n-1)/2}\equiv-1\pmod{F_n}.

Entonces, 3^{F_n-1}\equiv1\pmod{F_n}, por tanto, el orden multiplicativo de 3 módulo Fn divide a F_n-1=2^{2^n}, que es una potencia de dos. Por otra parte, el orden no divide a (Fn − 1) / 2, por lo que debe ser igual a Fn − 1. En particular, existen al menos Fn − 1 números menores que Fn que son coprimos con Fn, y esto sólo puede ocurrir si Fn es primo.

Para el otro sentido, supóngase que Fn es primo. Por el criterio de Euler,

3^{(F_n-1)/2}\equiv\left(\frac3{F_n}\right)\pmod{F_n},

donde \left(\frac3{F_n}\right) es el símbolo de Legendre. Elevándolo al cuadrado repetidas veces, encontramos que 2^{2^n}\equiv1\pmod3, por tanto, F_n\equiv2\pmod3, y \left(\frac{F_n}3\right)=-1. Como F_n\equiv1\pmod4, concluimos que \left(\frac3{F_n}\right)=-1 debido a la ley de reciprocidad cuadrática.

Referencias

  • P. Pépin, Sur la formule 2^{2^n}+1, Comptes Rendus Acad. Sci. Paris 85 (1877), pp. 329–333.

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Pépin's test — In mathematics, Pépin s test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth s test. The test is named for a French mathematician, P. Pépin.Description of the testLet F n=2^{2^n}+1 be …   Wikipedia

  • Pépin-Test — Der Pépin Test ist ein Primzahltest für Fermat Zahlen. Er prüft, ob natürliche Zahlen der Form prim sind oder nicht. Grundlage für den Pépin Test sind Arbeiten von Théophile Pépin (1826 – 1904), François Proth (1852 – 1879) und Édouard Lucas.… …   Deutsch Wikipedia

  • Pepin-Test — Unter dem Pepin Test versteht man einen Primzahltest. Der Pepin Test überprüft Fermatsche Zahlen, das sind natürliche Zahlen der Form darauf, ob sie eine Primzahl sind oder nicht. Grundlage für den Pepin Test sind Arbeiten, die auf Édouard Lucas… …   Deutsch Wikipedia

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Prix Pépin — Pour les articles homonymes, voir Pépin. Le prix Pépin est un prix littéraire français, créé par Pierre Gévart et décerné depuis 2005, qui récompense de courtes nouvelles de science fiction d une taille maximale de 300 signes, espaces comprises.… …   Wikipédia en Français

  • Prix Pepin — Prix Pépin Pour les articles homonymes, voir Pépin. Cet article fait partie de l …   Wikipédia en Français

  • AKS primality test — The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra… …   Wikipedia

  • Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… …   Wikipedia

  • Miller–Rabin primality test — The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version …   Wikipedia

  • Lucas–Lehmer test for Mersenne numbers — This article is about the Lucas–Lehmer test (LLT), that only applies to Mersenne numbers. There is also a Lucas Lehmer Riesel test for numbers of the form N=k 2^n 1, with 2^n > k, based on the LLT: see Lucas Lehmer Riesel test. There is also a… …   Wikipedia

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”