aula10_2010

Prévia do material em texto

A´lgebra A - Aula 10
Ra´ızes Primitivas
Elaine Pimentel
Departamento de Matema´tica, UFMG, Brazil
2o Semestre - 2010
Ra´ızes primitivas
Para determinar se n e´ primo, podemos verificar se φ(n) = n − 1.
Ou seja, se mdc(a, n) = 1 para todo a menor que n. Logo
precisamos calcular φ(n) sem fatorar n ⇒ precisamos contar
quantos elementos U(n) tem ⇒ imposs´ıvel se n e´ muito grande.
Teorema da raiz primitiva. Se p e´ um primo, existe b ∈ U(p)
tal que
bp−1 ≡ 1 (mod p)
mas
br 6≡ 1 (mod p) se r < p − 1
Ordem e Lema chave
Ordem de a ∈ U(n): menor nu´mero s tal que
as ≡ 1 (mod n)
Lema chave. Um inteiro positivo t satisfaz
at ≡ 1 (mod n)
se e somente se t e´ divis´ıvel pela ordem s de a ∈ U(n).
(⇐) Se s|t enta˜o t = rs e
at ≡ asr ≡ (as)r ≡ 1 (mod n).
Lema chave
(⇒) Suponhamos at ≡ 1. Dividindo t por s:
t = sq + r 0 ≤ r < s
Logo,
1 ≡ at ≡ (as)q.ar ≡ ar (mod n)
Como r < s e s e´ o menor inteiro positivo que satisfaz ak ≡ 1
(mod n), enta˜o r = 0. Ou seja, t e´ divis´ıvel por s.
Ra´ızes primitivas
Seja n ı´mpar e suponhamos que exista um b ∈ U(n) tal que a
ordem de b e´ n − 1.
Pelo Lema Chave e o Teorema de Euler , a ordem de b
divide φ(n). Mas φ(n) ≤ n − 1. Ou seja, φ(n) = n − 1. Logo n e´
primo.
Pelo Teorema da raiz primitiva : n primo ⇒ tal b sempre
existe. Encontra´-lo e´ uma questa˜o de sorte...
Teste de Lucas
Para aplicar isso a` primalidade, precisamos encontrar uma maneira
eficiente de mostrar que a ordem de um elemento de U(n) e´
exatamente n − 1.
Teste de Lucas. Sejam n ı´mpar e 2 ≤ b ≤ n − 1. Se
bn−1 ≡ 1 (mod n)
e
b
n−1
p 6≡ 1 (mod n)
para cada fator primo de n − 1, enta˜o n e´ primo.
Teste de Lucas - Prova
I Seja k a ordem de b em U(n). Queremos mostrar que
k = n − 1.
I bn−1 ≡ 1 (mod n) ⇒ k |(n − 1). Digamos que n − 1 = k .t
I Suponhamos t > 1. Enta˜o existe q primo tal que q|t:
n − 1
q
= k .
t
q
Teste de Lucas - Prova
I Logo, k divide n−1q e portanto,
bn−1/q ≡ 1 (mod n).
ABSURDO!
I Logo t = 1 e k = n − 1 ⇒ n e´ primo.
Teste de Lucas
I Testes anteriores: determinavam com certeza nu´meros
compostos.
I Teste de Lucas: determina com certeza nu´meros primos.
I Mas... precisamos fatorar n − 1!!!
I Finalmente: na˜o existe me´todo eficiente para escolher a base
b!
Outro teste de primalidade
Exemplo: n = 41. Logo n − 1 = 40 = 23.5. Teste de Lucas:
devemos achar 2 ≤ b ≤ 40 tal que:
I b40 ≡ 1 (mod 41)
I b20 6≡ 1 (mod 41)
I b8 6≡ 1 (mod 41)
Mas 220 ≡ 1 (mod 41) e 38 ≡ 1 (mod 41)... Para 41, a melhor
base e´ 7.
Outro teste de primalidade
Teste de primalidade. Seja n > 0 inteiro tal que
n − 1 = pe11 . . . perr
Se, para cada i = 1, . . . , r existirem inteiros positivos bi ,
(2 ≤ bi ≤ n − 1) que satisfac¸am
bn−1i ≡ 1 (mod n)
b
(n−1)/pi
i 6≡ 1 (mod n)
enta˜o n e´ primo.
Obs. Na˜o e´ necessa´rio que os bi ’s sejam todos distintos.
Outro teste de primalidade
Seja s1 a ordem de b1 em U(n). Segue do lema chave e da equac¸a˜o
bn−11 ≡ 1 (mod n)
que s1 divide n − 1. Logo
s1 = p
k1
1 . . . p
kr
r onde k1 ≤ e1, . . . kr ,≤ er
Por outro lado, b
(n−1)/p1
1 6≡ 1 (mod n) ⇒ (n − 1)/p1 na˜o e´
divis´ıvel por s1.
Outro teste de primalidade
Mas
(n − 1)
p1
= pe1−11 .p
e2
2 . . . p
er
r
Comparando com a fatorac¸a˜o de s1, temos que a u´nica
possibilidade de s1 na˜o dividir (n − 1)/p e´ k1 = e1.
Ou seja, pe11 divide s1.
Mas s1 divide φ(n). Logo p
e1
1 divide φ(n).
Outro teste de primalidade
Ou seja,
pe11 , p
e2
2 , . . . , p
er
r
dividem φ(n). Como pe11 , . . . , p
er
r sa˜o primos entre si, o produto
deles:
pe11 . . . . .p
er
r = n − 1
divide φ(n).
Mas φ(n) ≤ n − 1. Logo φ(n) = n − 1 e n e´ primo.
Estrate´gia para primalidade
1. Verificamos, por tentativa, se n e´ divis´ıvel por primos menores
que 5.000.
2. Se n passa por (1), aplique o teste de Miller para todas as
bases primas de (1).
3. Se n passa pelo teste de Miller para todas essas bases,
aplicamos o teste de primalidade descrito nesta aula.
Teorema da raiz primitiva
Teorema da raiz primitiva Se p e´ primo, existe um elemento c
em U(p) tal que a ordem de c em U(p) e´ exatamente
φ(p) = p − 1.
Tal elemento c e´ chamado raiz primitiva.
Nu´meros de Carmichael
Teorema de Korselt. Um inteiro positivo ı´mpar n e´ um nu´mero
de Carmichael se, e somente se, cada fator primo p de n satisfaz as
seguintes condic¸o˜es:
1. p2 na˜o divide n;
2. p − 1 divide n − 1.
Nu´meros de Carmichael
Falta apenas provar: n de Carmichael ⇒ (2).
Suponhamos n de Carmichael:
bn ≡ b (mod n) ∀1 < b < n − 1
Seja p primo que divide n. Pelo teorema da raiz primitiva, existe
c ∈ U(p) tal que a ordem de c e´ p − 1.
Nu´meros de Carmichael
Mas cn − c e´ divis´ıvel por n. Como p divide n, temos tambe´m que
p divide cn − c . Ou seja,
cn ≡ c (mod p)
Como c e´ invers´ıvel mo´dulo p,
cn−1 ≡ 1 (mod p)
Logo, pelo teorema de Lagrange, a ordem de c divide n − 1. Ou
seja, (p − 1)|(n − 1).
Exerc´ıcios - Cap´ıtulo 10
1, 2, 4