algebra-teoNum

Prévia do material em texto

´
Algebra e Teoria dos Números
Diego F. Aranha
Institute of Computing
UNICAMP
dfaranha (IC)
´
Algebra e Teoria dos Números 1/22
Primos e divisibilidade
Divisibilidade
Para a, b 2 Z, dizemos que a divide b (denotado por a | b) ou que a é
divisor de b se existe c 2 Z tal que ac = b. Se a 62 {1, b}, dizemos que a
é fator ou divisor não-trivial de b.
Primalidade
Um número inteiro p > 1 é primo se não possui fatores, ou seja, só
possui divisores triviais. Um número que não é primo é dito composto.
Teorema Fundamental da Aritmética
Qualquer número inteiro N > 1 pode ser expressado unicamente (a
menos de permutação) como um produto de fatores primos N =
Q
i p
ei
i ,
com pi distintos e ei � 1 para todo i .
dfaranha (IC)
´
Algebra e Teoria dos Números 2/22
Divisibilidade
Divisão
Seja a 2 Z e b inteiro positivo. Existem inteiros únicos q, r tais que
a = bq + r , com 0  r < b.
Máximo Divisor Comum
Sejam a, b inteiros positivos. Existem inteiros x , y tais que
ax + by = mdc(a, b) e mdc(a, b) é o menor inteiro que pode ser escrito
dessa forma.
Propriedades
- Se c | ab e mdc(a, c) = 1, então c | b. Em particular, se p é primo e
p | ab, então p | a ou p | b.
- Se p | N, q | N e mdc(p, q) = 1, então pq | N.
dfaranha (IC)
´
Algebra e Teoria dos Números 3/22
Algoritmo de Euclides
Algorithm 1 Cálculo de mdc(a, b).
1: r
0
 a, r
1
 b,m 1
2: while rm 6= 0 do
3: qm b rm�1rm c
4: rm+1 rm�1 � qmrm
5: m m + 1
6: end while
7: m m � 1
8: return (q
1
, . . . , qm; rm = mdc(a, b))
Invariantes
- Para 0  i  rm�2 : ri = qi+1ri+1 + ri+2, com 0 < ri+2 < ri+1;
- Temos que rm�1 = qmrm;
- mdc(r
0
, r
1
) = mdc(r
1
, r
2
) = · · · = mdc(rm�1, rm) = rm
dfaranha (IC)
´
Algebra e Teoria dos Números 4/22
Algoritmo de Euclides
Sejam as duas seqüências:
tj =
8
><
>:
0 se j = 0
1 se j = 1
tj�2 � qj�1tj�1 se j � 2
sj =
8
><
>:
1 se j = 0
0 se j = 1
sj�2 � qj�1sj�1 se j � 2
Teorema
Para 0  j  m, temos que rj = sj r0 + tj r1.
Prova: Por indução forte!
dfaranha (IC)
´
Algebra e Teoria dos Números 5/22
Algoritmo Estendido de Euclides
Algorithm 2 Cálculo de r = mdc(a, b) = sa+ tb, com r , s, t 2 Z.
1: a
0
 a, b
0
 b
2: t
0
 0, t 1, s
0
 1, s 0
3: q b a0b
0
c, r a
0
� qb
0
4: while r > 0 do
5: T t
0
� qt, t
0
 t, t T
6: T s
0
� qs, s
0
 s, s T
7: a
0
 b
0
, b
0
 r , q b a0b
0
c, r a
0
� qb
0
8: end while
9: r b
0
10: return (r , s, t)
dfaranha (IC)
´
Algebra e Teoria dos Números 6/22
Aritmética Modular
Definições
Sejam a, b,N 2 Z, com N > 1. A redução modular de a módulo N
(a mod N) denota o resto da divisão inteira de a por N. Dizemos que
a, b são congruentes módulo N (a ⌘ b (mod N)) se
a mod N = b mod N ou ainda se N | (a� b). A relação de congruência é
reflexiva, simétrica e transitiva.
Lembrete: ad ⌘ cd (mod N) nem sempre implica a ⌘ c (mod N).
Inverso
Sejam a,N 2 Z , com N > 1. Então a é inverśıvel módulo N sse
mdc(a,N) = 1. O inverso único de a é denotado por a�1 e pode ser
calculado pelo Algoritmo Estendido de Euclides.
Exemplo: 14 é o inverso de 11 módulo 17.
dfaranha (IC)
´
Algebra e Teoria dos Números 7/22
Grupos
Definição
Um grupo G é um conjunto equipado com uma operação binária � que
possui as seguintes propriedades:
- Fechamento: Se g , h 2 G, então g � h 2 G;
- Elemento Neutro: 9e 2 G tal que 8g 2 G, g � e = e � g = g .
- Inverso: 8g 2 G, 9h 2 G tal que g � h = e = g � e.
- Associatividade: 8g
1
, g
2
, g
3
2 G, g
1
� (g
2
� g
3
) = (g
1
� g
2
) � g
3
.
Quando G é um grupo finito, denotamos o número de elementos (ordem)
de G por |G|. Um grupo é dito abeliano se � é uma relação comutativa,
ou seja, 8g
1
, g
2
2 G, g
1
� g
2
= g
2
� g
1
.
Exemplos: (Z,+), (R,+), (R⇤,⇥), (ZN = {0, 1, . . . ,N � 1},+).
Subgrupo
Se G é um grupo, um conjunto H ✓ G é subgrupo se H for um grupo
sob a mesma operação de G.
dfaranha (IC)
´
Algebra e Teoria dos Números 8/22
Grupos
Notação
A operação de grupo pode utilizar notação aditiva ou multiplicativa.
Quando a operação de grupo é aplicada (m � 1) vezes a um elemento g ,
utilizamos a notação aditiva m · g ou multiplicativa gm. Inversos e
elementros neutros são denotados por (�g , 0) e (g�1, 1),
respectivamente.
Importante: Não confundir com adição ou multiplicação inteira.
Teorema
Seja G um grupo finito de ordem m. Para todo g 2 G e i 2 Z , temos
que gm = 1 e se m > 1, g i = g i mod m.
Corolário
Seja d , e 2 Z e G um grupo finito de ordem m > 1. A função
fe : G! G tal que fe(g) = g e é uma permutação quando
mdc(e,m) = 1 e fd é função inversa de fe se d = e�1 mod m.
dfaranha (IC)
´
Algebra e Teoria dos Números 9/22
O grupo Z⇤N
Teorema
Sejam um inteiro N > 1 com fatoração N =
Q
i p
ei
i e
Z⇤N = {a 2 {1, . . . ,N � 1} | mdc(a,N) = 1}. Então Z⇤N é um grupo
abeliano sob a multiplicação módulo N. A ordem do grupo é dada pela
função totiente de Euler �(N) =
Q
i p
ei�1
i (pi � 1).
Corolário
Seja N > 1 inteiro e a 2 Z⇤N . Então a�(N) = 1 mod N. Se N é primo e
a 2 Zp, temos que ap�1 = 1 mod p.
dfaranha (IC)
´
Algebra e Teoria dos Números 10/22
Teorema Chinês do Resto
Isomorfismo
Sejam G,H grupos com operações �G, �H, respectivamente. A função
f : G! H é um isomorfismo se f é uma bijeção e
8g
1
, g
2
2 G, f (g
1
�G g2) = f (g1) �H f (g2).
Teorema
Seja N = pq, com p, q relativamente primos. A função
f (x) = (x mod p, x mod q) é um isomorfismo de ZN para Zp ⇥ Zq e de
Z⇤N para Z⇤p ⇥ Z⇤q.
Importante: A mudança de representação afeta o custo computacional de
operações em grupo.
dfaranha (IC)
´
Algebra e Teoria dos Números 11/22
Teorema Chinês do Resto
Sejam m
1
, . . . ,mr inteiros co-primos entre si dois a dois e suponha
a
1
, . . . , ar inteiros.
Considere o sistema de equações:
x ⌘ a
1
(mod m
1
)
x ⌘ a
2
(mod m
2
)
· · ·
x ⌘ ar (mod mr )
O Teorema Chinês do Resto fornece uma solução única para esse sistema
módulo M =
Qr
i=1mi :
Teorema
A solução para o sistema de equações é x =
rX
i=1
aiMiyi mod M, onde
Mi = M/mi e yi = M
�1
i mod mi , para 1  i  r .
dfaranha (IC)
´
Algebra e Teoria dos Números 12/22
Geração de números primos
Precisamos da geração de números primos grandes, ou ainda, a geração
de números grandes e teste de sua primalidade.
Alternativas:
- Teste determińıstico polinomial: [AKS 2002], O(n6);
- Teste probabiĺıstico: mais rápido, chance de erro.
Teorema dos números primos
Seja ⇡(N) a quantidade de números primos menores ou iguais a N.
Podemos aproximar ⇡(N) ⇡ N/ ln (N).
Exemplo: Para n com 1024 bits, precisamos gerar p, q com 512 bits. Um
número aleatório com 512 bits tem probabilidade 2/355 de ser primo
ı́mpar.
dfaranha (IC)
´
Algebra e Teoria dos Números 13/22
Algoritmo probabiĺıstico
Definição
Um algoritmo probabiĺıstico é qualquer algoritmo que utiliza números
aleatórios. Quando há chance de erro, o algoritmo é dito de Monte
Carlo. Quando a resposta é sempre correta, mas com chance de falha, o
algoritmo é dito Las Vegas. Classificação para solução de problemas de
decisão:
1 Monte Carlo com viés positivo: uma resposta SIM é sempre
correta, mas uma resposta NÃO pode estar incorreta;
2 Monte Carlo com viés negativo: uma resposta NÃO é sempre
correta, mas uma resposta SIM pode estar incorreta.
A probabilidade de erro é limitada superiormente por ✏.
Importante: como transformar Monte Carlo em Las Vegas?
dfaranha (IC)
´
Algebra e Teoria dos Números 14/22
Problema de decisão
Composto(n), n � 2
O conjunto D(n) de divisores distintos de n possui mais do que dois
elementos?
Alternativas para resolver o problema:
1 Solovay-Strassen: Monte Carlo com viés positivo, ✏ = 1/2;
2 Miller-Rabin: Monte Carlo com viés positivo, ✏ = 1/4.
dfaranha (IC)
´
Algebra e Teoria dos Números 15/22
Problema de decisão
Definição
Seja p um primo ı́mpar e a inteiro. Dizemos que a é reśıduoquadrático
módulo p se a 6= 0 (mod p) e y2 ⌘ a (mod p) possui duas soluções
(y ,�y) módulo p. Caso contrário, a é reśıduo não-quadrático.
Exemplo: Em Z
11
, os reśıduos quadráticos são 1, 3, 4, 5 e 9. Os reśıduos
não-quadráticos são 2, 6, 7, 8 e 10.
Lema
Se p é um primo ı́mpar, então as únicas ráızes quadradas de 1 módulo p
são 1 e �1 mod p.
dfaranha (IC)
´
Algebra e Teoria dos Números 16/22
Śımbolos de Jacobi e Legendre
Teorema (Critério de Euler)
Seja p primo ı́mpar. Então a é reśıduo quadrático módulo p sse
a(p�1)/2 ⌘ 1 (mod p).
Prova: Suponha que a ⌘ y2 (mod p). Se p é primo, então ap�1 ⌘ 1
(mod p), 8a 6⌘ 0 (mod p). Logo:
a(p�1)/2 ⌘ (y2)(p�1)/2 ⌘ 1 (mod p).
Agora, suponha que a(p�1)/2 ⌘ 1 (mod p). Seja b um elemento
primitivo módulo p. Então a ⌘ bi (mod p) para i 2 Z. Logo:
a(p�1)/2 ⌘ (bi )(p�1)/2 (mod p).
Como b tem ordem p � 1, então (p � 1)|i(p � 1)/2. Então i é par e as
ráızes quadradas de a são ±bi/2 mod p.
dfaranha (IC)
´
Algebra e Teoria dos Números 17/22
Śımbolos de Jacobi e Legendre
Teorema (Critério de Euler)
Seja p primo ı́mpar. Então a é reśıduo quadrático módulo p sse
a(p�1)/2 ⌘ 1 (mod p).
Prova: Suponha que a ⌘ y2 (mod p). Se p é primo, então ap�1 ⌘ 1
(mod p), 8a 6⌘ 0 (mod p). Logo:
a(p�1)/2 ⌘ (y2)(p�1)/2 ⌘ 1 (mod p).
Agora, suponha que a(p�1)/2 ⌘ 1 (mod p). Seja b um elemento
primitivo módulo p. Então a ⌘ bi (mod p) para i 2 Z. Logo:
a(p�1)/2 ⌘ (bi )(p�1)/2 (mod p).
Como b tem ordem p � 1, então (p � 1)|i(p � 1)/2. Então i é par e as
ráızes quadradas de a são ±bi/2 mod p.
dfaranha (IC)
´
Algebra e Teoria dos Números 17/22
Śımbolos de Jacobi e Legendre
Definição
Para a 2 Z, p primo ı́mpar, o śımbolo de Legendre
⇣
a
p
⌘
é:
✓
a
p
◆
=
8
><
>:
0 se a ⌘ 0 (mod p)
1 se a é reśıduo quadrático módulo p
�1 se a é reśıduo não-quadrático módulo p.
Temos que
⇣
a
p
⌘
⌘ a(p�1)/2 (mod p).
Definição
Suponha n 2 Z ı́mpar positivo com fatoração n =
Qk
i=1 pi
ei .
Seja a 2 Z. O śımbolo de Jacobi
�
a
n
�
é definido como:
⇣a
n
⌘
=
kY
i=1
✓
a
pi
◆ei
dfaranha (IC)
´
Algebra e Teoria dos Números 18/22
Śımbolos de Jacobi e Legendre
Definição
Para a 2 Z, p primo ı́mpar, o śımbolo de Legendre
⇣
a
p
⌘
é:
✓
a
p
◆
=
8
><
>:
0 se a ⌘ 0 (mod p)
1 se a é reśıduo quadrático módulo p
�1 se a é reśıduo não-quadrático módulo p.
Temos que
⇣
a
p
⌘
⌘ a(p�1)/2 (mod p).
Definição
Suponha n 2 Z ı́mpar positivo com fatoração n =
Qk
i=1 pi
ei .
Seja a 2 Z. O śımbolo de Jacobi
�
a
n
�
é definido como:
⇣a
n
⌘
=
kY
i=1
✓
a
pi
◆ei
dfaranha (IC)
´
Algebra e Teoria dos Números 18/22
Algoritmo Solovay-Strassen
Para o śımbolo de Jacobi, temos que
�
a
n
�
= 0 sse mdc(a, n) 6= 1.
Temos ainda que para n composto, a igualdade
�
a
n
�
= a(n�1)/2 (mod n)
é verdadeira para metade dos inteiros a 2 Z⇤n.
Algoritmo
1 Escolher inteiro aleatório a tal que 1  a  n � 1
2 x 
�
a
n
�
3 Se x = 0, retorne COMPOSTO
4 y a(n�1)/2 (mod n)
5 Se x ⌘ y (mod n), retorne PRIMO. Caso contrário, retorne
COMPOSTO.
Importante: Por que o algoritmo tem viés positivo com ✏ = 1/2?
dfaranha (IC)
´
Algebra e Teoria dos Números 19/22
Algoritmo Solovay-Strassen
Para o śımbolo de Jacobi, temos que
�
a
n
�
= 0 sse mdc(a, n) 6= 1.
Temos ainda que para n composto, a igualdade
�
a
n
�
= a(n�1)/2 (mod n)
é verdadeira para metade dos inteiros a 2 Z⇤n.
Algoritmo
1 Escolher inteiro aleatório a tal que 1  a  n � 1
2 x 
�
a
n
�
3 Se x = 0, retorne COMPOSTO
4 y a(n�1)/2 (mod n)
5 Se x ⌘ y (mod n), retorne PRIMO. Caso contrário, retorne
COMPOSTO.
Importante: Por que o algoritmo tem viés positivo com ✏ = 1/2?
dfaranha (IC)
´
Algebra e Teoria dos Números 19/22
Algoritmo Solovay-Strassen
Propriedades do śımbolo de Jacobi:
- Se n > 0 ı́mpar e m
1
⌘ m
2
(mod n), então:
⇣m
1
n
⌘
=
⇣m
2
n
⌘
.
- Se n > 0 ı́mpar, então:
✓
2
n
◆
=
(
1 se n ⌘ ±1 (mod 8)
�1 se n ⌘ ±3 (mod 8).
- Se n > 0 ı́mpar, então:
⇣m
1
m
2
n
⌘
=
⇣m
1
n
⌘⇣m
2
n
⌘
, ou
✓
m = 2kt
n
◆
=
✓
2
n
◆k ⇣ t
n
⌘
- Se m, n > 0 ı́mpares, então:
⇣m
n
⌘
=
(
�
�
n
m
�
se m ⌘ n ⌘ 3 (mod 4)�
n
m
�
caso contrário.
dfaranha (IC)
´
Algebra e Teoria dos Números 20/22
Algoritmo Miller-Rabin
Intuição: Não há ráızes não-triviais de 1 módulo p primo. Extrair ráızes
quadradas de an�1 mod n e verificar se todas são ±1 mod n.
Algoritmo
1 Escrever n � 1 = 2km, com m ı́mpar
2 Escolher inteiro aleatório a tal que 1  a  n � 1
3 b am mod n
4 Se b ⌘ 1 (mod n), retorne PRIMO
5 Para i 0 até k � 1, faça:
- Se b ⌘ �1 (mod n), retorne PRIMO
- b b2 mod n
6 Retorne COMPOSTO
Importante: Por que o algoritmo tem viés positivo com ✏ = 1/4?
dfaranha (IC)
´
Algebra e Teoria dos Números 21/22
RSA (Rivest, Shamir, Adleman, 1977)
Geração de chaves:
1 Gerar primos p e q com k/2 bits;
2 Calcular N = pq e �(N) = (p � 1)(q � 1);
3 Selecionar e tal que mdc(e,�(N)) = 1; (primo pequeno?)
4 Calcular d tal que d = e�1 mod �(N);
5 M = C = ZN ;
6 K = (N, p, q, d , e).
7 Chave pública é (e,N), chave privada é (d ,N, p, q).
Cifração: Calcular EncK (x) = x
e mod N;
Decifração: Calcular DecK (y) = y
d mod N.
dfaranha (IC)
´
Algebra e Teoria dos Números 22/22