aula08_2010

Prévia do material em texto

A´lgebra A - Aula 08
Teste de Miller e Pseudoprimos fortes
Elaine Pimentel
Departamento de Matema´tica, UFMG, Brazil
2o Semestre - 2010
Teste de Miller
Teorema de Fermat: detecta nu´meros compostos com uma certa
eficieˆncia, mas na˜o e´ um bom teste de primalidade.
Teste de Miller: Calcula-se a sequeˆncia de poteˆncias mo´dulo n:
bq, b2q, . . . , b2
kq
onde n − 1 = 2kq.
Se n e´ primo, enta˜o:
b2
kq ≡ bn−1 ≡ 1 (mod n)
Teste de Miller
Seja j o menor expoente tal que b2
jq ≡ 1 (mod n). Se j ≥ 1.
Podemos escrever
b2
jq − 1 = (b2j−1q − 1)(b2j−1q + 1)
Se n e´ primo e divide b2
jq − 1, enta˜o n deve dividir (b2j−1q + 1)
pela minimalidade de j . Logo,
b2
j−1q ≡ −1 (mod n)
Ou seja, uma das poteˆncias
bq, b2q, . . . , b2
kq
deve ser congruente a −1 mo´dulo n. Se j = 0, enta˜o temos apenas
que bq ≡ 1 (mod n). Se nada disso acontecer, enta˜o n deve ser
composto.
Teste de Miller
1. Divida n − 1 por 2 ate´ encontrar q ı´mpar e k tais que
n − 1 = 2kq.
2. Fac¸a i = 0 e r = resto de bq por n.
3. Se i = 0 e r = 1 ou i ≥ 0 e r = n − 1: teste inconclusivo.
4. Fac¸a i = i + 1 e r = r2 onde r2 e´ o resto da divisa˜o de r
2 por
n.
5. Se i < k volte a` etapa 3; sena˜o: n e´ composto.
Exemplo
Tome o nu´mero de Carmichael 561. Temos que 560 = 24.35.
Calculando as sequeˆncias de restos mo´dulo 561 das poteˆncias de 2:
expoentes 35 2.35 22.35 23.35
restos 263 166 67 1
Logo 561 tem que ser composto.
Pseudoprimo forte
Se um nu´mero composto n tem resultado inconclusivo para o teste
de Miller com respeito a uma base b, dizemos que n e´ um
pseudoprimo forte para a base b. Observe que pseudoprimo forte
−→ pseudoprimo.
Existem 1282 pseudoprimos fortes entre 1 e 109.
Primalidade e computac¸a˜o alge´brica
E´ importante ressaltar que o teste de Miller e´ muito usado na
pra´tica. O que se faz para ter maior garantia do resultado e´ fazer o
teste para diversas bases. E´ assim com o Maple, ScratchPad -
IBM, Axiom 1.1 - IBM.
Vale a observac¸a˜o: dado um nu´mero finito qualquer de bases,
existem infinitos nu´meros de Carmichael que sa˜o pseudoprimos
fortes para todas essas bases.
Exerc´ıcios propostos - Cap´ıtulo 6
2, 5, 7, 8, 10