Teste de Pépin - Pépin's test

Em matemática , o teste de Pépin é um teste de primalidade , que pode ser usado para determinar se um número de Fermat é primo . É uma variante do teste de Proth . O teste tem o nome de um matemático francês, Théophile Pépin .

Descrição do teste

Vamos ser o n º número Fermat. O teste de Pépin afirma que para n > 0, ${\ displaystyle F_ {n} = 2 ^ {2 ^ {n}} + 1}$

{\ displaystyle F_ {n}}

é primo se e somente se

{\ displaystyle 3 ^ {(F_ {n} -1) / 2} \ equiv -1 {\ pmod {F_ {n}}}.}

A expressão pode ser avaliada módulo por quadratura repetida . Isso torna o teste um algoritmo de tempo polinomial rápido . No entanto, os números de Fermat crescem tão rapidamente que apenas alguns números de Fermat podem ser testados em uma quantidade razoável de tempo e espaço. ${\ displaystyle 3 ^ {(F_ {n} -1) / 2}}$ ${\ displaystyle F_ {n}}$

Outras bases podem ser usadas no lugar de 3, essas bases são

3, 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 63, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 105, 108, 112, 119, 125, 126, 130, 147, 150, 156, 160, ... (sequência A129802 no OEIS ).

Os primos na sequência acima são chamados de primos Elite , eles são

3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041, 163841, 544001, 604801, 6684673, 14172161, 159318017, 446960641, 1151139841, 3208642561, 38126223361, 10890510331261, 1780409482881, 31.05.509.48612, 31.05.509.48612, 31.05.509.48612, 31.05.409.48612 . (sequência A102742 no OEIS )

Para o inteiro b > 1, a base b pode ser usada se e somente se apenas um número finito de números de Fermat F _n satisfaz isso , onde é o símbolo de Jacobi . ${\ displaystyle \ left ({\ frac {b} {F_ {n}}} \ right) = 1}$ ${\ displaystyle \ left ({\ frac {b} {F_ {n}}} \ right)}$

Na verdade, o teste de Pépin é o mesmo que o teste de Euler-Jacobi para números de Fermat, já que o símbolo de Jacobi é -1, ou seja, não há números de Fermat que sejam pseudoprimos de Euler-Jacobi para essas bases listadas acima. ${\ displaystyle \ left ({\ frac {b} {F_ {n}}} \ right)}$

Prova de correção

Suficiência: suponha que a congruência

{\ displaystyle 3 ^ {(F_ {n} -1) / 2} \ equiv -1 {\ pmod {F_ {n}}}}

detém. Então , assim, a ordem multiplicativa de 3 módulos se divide , que é uma potência de dois. Por outro lado, a ordem não se divide e, portanto, deve ser igual a . Em particular, há pelo menos números abaixo de coprime de , e isso só pode acontecer se for primo. ${\ displaystyle 3 ^ {F_ {n} -1} \ equiv 1 {\ pmod {F_ {n}}}}$ ${\ displaystyle F_ {n}}$ ${\ displaystyle F_ {n} -1 = 2 ^ {2 ^ {n}}}$ ${\ displaystyle (F_ {n} -1) / 2}$ ${\ displaystyle F_ {n} -1}$ ${\ displaystyle F_ {n} -1}$ ${\ displaystyle F_ {n}}$ ${\ displaystyle F_ {n}}$ ${\ displaystyle F_ {n}}$

Necessidade: suponha que seja principal. Pelo critério de Euler , ${\ displaystyle F_ {n}}$

{\ displaystyle 3 ^ {(F_ {n} -1) / 2} \ equiv \ left ({\ frac {3} {F_ {n}}} \ right) {\ pmod {F_ {n}}}}

,

onde está o símbolo Legendre . Por quadratura repetida, descobrimos que , portanto , e . Como , concluímos da lei da reciprocidade quadrática . ${\ displaystyle \ left ({\ frac {3} {F_ {n}}} \ right)}$ ${\ displaystyle 2 ^ {2 ^ {n}} \ equiv 1 {\ pmod {3}}}$ ${\ displaystyle F_ {n} \ equiv 2 {\ pmod {3}}}$ ${\ displaystyle \ left ({\ frac {F_ {n}} {3}} \ right) = - 1}$ ${\ displaystyle F_ {n} \ equiv 1 {\ pmod {4}}}$ ${\ displaystyle \ left ({\ frac {3} {F_ {n}}} \ right) = - 1}$

Testes históricos de Pépin

Por causa da esparsidade dos números de Fermat, o teste de Pépin foi executado apenas oito vezes (em números de Fermat cujos status de primalidade ainda não eram conhecidos). Mayer, Papadopoulos e Crandall especulam que, de fato, por causa do tamanho dos números de Fermat ainda indeterminados, serão necessários avanços consideráveis na tecnologia antes que qualquer outro teste de Pépin possa ser executado em um período de tempo razoável. Em 2021, o menor número de Fermat não testado sem fator primo conhecido é o de 2.585.827.973 dígitos. ${\ displaystyle F_ {33}}$

Ano	Provadores	Número Fermat	Resultado do teste Pépin	Fator encontrado mais tarde?
1905	Morehead e Western	${\ displaystyle F_ {7}}$	composto	Sim (1970)
1909	Morehead e Western	${\ displaystyle F_ {8}}$	composto	Sim (1980)
1952	Robinson	${\ displaystyle F_ {10}}$	composto	Sim (1953)
1960	Paxson	${\ displaystyle F_ {13}}$	composto	Sim (1974)
1961	Selfridge e Hurwitz	${\ displaystyle F_ {14}}$	composto	Sim (2010)
1987	Buell & Young	${\ displaystyle F_ {20}}$	composto	Não
1993	Crandall , Doenias, Norrie & Young	${\ displaystyle F_ {22}}$	composto	Sim (2010)
1999	Mayer, Papadopoulos e Crandall	${\ displaystyle F_ {24}}$	composto	Não