Fundamentos Matemáticos

Fundamentos Matemáticos
Instituto de Computação - UNICAMP
Julio López
Disciplina MC889
Agenda
Números inteiros
Divisão de Números
O Algoritmo de Euclides
Grupos
Corpos finitos
Julio López
Disciplina MC889
Números inteiros
Z é o conjunto dos números inteiros.
Sejam a e b números inteiros. Dezimos que a é divisı́vel por b
se existe inteiro q tal que a = qb. Nesse caso, b é divisor de a
3|21, mas 4 6 |15.
Um número inteiro p ≥ 2 é primo se é divisı́vel somente por 1
e por ele mesmo.
Teorema 1: Todo inteiro n ≥ 2 pode ser escrito como um produto
de potências de números primos; a fatoração de n.
n = p1e1 p2e2 · · · pkek
Julio López
Disciplina MC889
Divisão de Números
Definição 1: Sejam a, n números inteiros com n > 0. O resto ou
resı́duo da divisão de a por n é o único inteiro r , com
0 ≤ r ≤ n − 1, tal que a = qn + r para algum inteiro q, o
quociente da divisão.
Por essa definição o resto da divisão de 7 por 3 é 1 (com quociente
2), e o resto da divisão de −7 por 3 é 2 (com quociente −3).
Definição 2: Para a, n números inteiros com n > 0, a expressão
a mod n é a redução de a módulo n, definida como o resto da
divisão de a por n.
Portanto, 0 mod 5 = 0 e (3 − 8) mod 4 = −1 mod 4 = 3.
Julio López
Disciplina MC889
Aritmética modular
Definição 3: Dado um inteiro n ≥ 1, denotamos por Zn ao
conjunto {0, 1, . . . , n − 1} de resı́duos módulo n, isto é dos restos
possı́veis de divisões de números inteiros por n.
Como todo número inteiro produz um resto ao ser dividido por n,
Zn tem em si um representante para cada número inteiro. A
próxima definição captura essa idéia.
Definição 4: Para a, b, n números inteiros com n > 0, escrevemos
a ≡ b (mod n), quando a mod n = b mod n. Dizemos que a e b
são congruentes módulo n.
Assim, 0 ≡ 3 (mod 3) e 43 ≡ 1 (mod 2).
Proposição : a ≡ b (mod n) se e somente se a = b + kn para
algum inteiro k.
Julio López
Disciplina MC889
Aritmética modular
Proposição :
Se a ≡ b (mod n) e c ≡ d (mod n) então a + c ≡ b + d
(mod n)
Se a ≡ b (mod n) e c ≡ d (mod n) então a × c ≡ b × d
(mod n)
Se a ≡ b (mod n) e m é um inteiro positivo então
m × a ≡ m × b (mod n)
Exemplo:
5
≡
52 ≡
53 ≡
54 ≡
54 (mod 3) ?
2 (mod 3)
10 ≡ 1 (mod 3)
5 ≡ 2 (mod 3)
10 ≡ 1 (mod 3).
Julio López
Disciplina MC889
O máximo divisor comum (m.d.c)
Considere a, b dois números inteiros, não ambos nulos.
O máximo divisor comum de a e b, (mdc(a, b)), é o maior
inteiro d que divide ambos a e b.
mdc(20, 8) = 4
mdc(20, 0) = 20
mdc(20, 7) = 1
Quando mdc(a, b) = 1, dizemos que a e b são primos entre si
ou coprimos.
O Algoritmo de Euclides, é o método mais popular para o cálculo
do mdc.
Julio López
Disciplina MC889
O Algoritmo de Euclides
Entrada: inteiros a, b, com a > 0, b ≥ 0.
Saı́da: inteiro d, onde d = mdc(a, b).
mdc(a, b)
mdc(a, 0)
=
=
mdc (b, mdc(a, b));
a.
mdc(18, 4)
= mdc(4, 18 mod 4)
= mdc(4, 2)
= mdc(2, 4 mod 2)
= mdc(2, 0)
= 2.
Nota: a mod b = a − b · ba/bc.
Julio López
Disciplina MC889
O Algoritmo de Euclides
Entrada: inteiros a, b, com a > 0, b ≥ 0.
Saı́da: inteiro d, onde d = mdc(a, b).
1. se b = 0 então retorne a;
2. enquanto b > 0 faça
2.1 q ← a div b; r ← a − q ∗ b;
2.2 a ← b; b ← r ;
3. d ← a;
4. retorne d
Julio López
Disciplina MC889
Propriedades do Máximo Divisor Comúm
Teorema 2: Sejam a, b números inteiros. Então existem inteiros s
e t tais que sa + tb = mdc(a, b). Adicionalmente, o mdc(a, b) é o
menor número positivo que pode ser representado dessa forma.
Proposição 1: 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.
Proposição 2: Se p|n e q|n, e mdc(p, q) = 1, então pq|n.
Julio López
Disciplina MC889
Aritmética modular em Z∗n
Definição 5: Dado um inteiro n ≥ 2, denotamos por Z∗n ao
conjunto {a | mdc(a, n) = 1, 1 ≤ a ≤ n − 1}. O tamanho de Z∗n é
representado por φ(n), a função de Euler.
Assim, Z∗10 = {1, 3, 7, 9} e φ(10) = 4. Também, φ(n) = n − 1
sempre que n for primo.
É fácil verificar que as operações de soma, subtração e
multiplicação modular são as mesmas da aritmética usual mas
com o resultado reduzido módulo n. A divisão é a única
exceção: (a/b) mod n é sempre escrita e intepretada como
ab −1 mod n.
Julio López
Disciplina MC889
Inversos
Definição 6: Para a, n números inteiros com n > 0, o inverso
aditivo de a módulo n é o inteiro b = −a mod n.; ou seja
a + b ≡ 0 (mod n).
Definição 7: Para a, n números inteiros com n > 0, o inverso
multiplicativo de a módulo n, se existir, é o único inteiro b,
1 ≤ b ≤ n − 1, tal que ab ≡ 1 (mod n). Denotamos o inverso
multiplicativo de a módulo n por a−1 mod n.
O inverso aditivo de 4 módulo 7 é 3.
O inverso multiplicativo de 2 módulo 5 é 3.
O inverso multiplicativo de 2 módulo 6 não existe.
Julio López
Disciplina MC889
Inversos
Proposição 3: Para a, n números inteiros com n > 0, o inverso
multiplicativo de a módulo n existe se e somente se mdc(a, n) = 1.
Se mdc(a, n) = 1, como calcular a−1 mod n?
Extensão do Algoritmo de Euclides:
1 = mdc(a, n) = sa + tn
1 = sa mod n
a−1 = s mod n.
Julio López
Disciplina MC889
Extensão do Algoritmo de Euclides
Dados a, n, a extensão do Algoritmo de Euclides, retorna inteiros
(r , s, t) onde r = mdc(a, n) e r = sa + tn. Isto é, sa ≡ r mod n.
Assim, quando mdc(a, n) = 1, o inteiro s é a−1 mod n.
r0 = a, r1 = b
mcd(r0 , r1 )
r0
=
r1
=
..
.
=
..
.
=
rm−2 =
rm−1 =
= mcd(r1 , r2 ) = · · · = mdc(rm−1 , rm ) = rm
q1 r1 + r2
0 < r2 < r1
q2 r2 + r3
0 < r3 < r2
..
..
.
.
..
..
.
.
qm−1 rm−1 + rm 0 < rm < rm−1
qm rm .
rj = sj a + tj b, 0 ≤ j ≤ m.
Julio López
Disciplina MC889
Extensão do Algoritmo de Euclides
Entrada: inteiros a, b, com a > 0, b ≥ 0.
Saı́da: inteiros r , s e t onde r = mdc(a, b) = sa + tb.
1. a0 ← a; b0 ← b; t0 ← 0; t ← 1;
2. s0 ← 1; s ← 0; q ← ba0 /b0 c; r ← a0 − qb0 ;
3. enquanto r > 0 faça
3.1 temp ← t0 − qt; t0 ← t; t ← temp;
3.2 temp ← s0 − qs; s0 ← s; s ← temp;
3.3 a0 ← b0 ; b0 ← r ; q ← ba0 /b0 c; r ← a0 − qb0 ;
4. r ← b0 ;
5. retorne (r , s, t)
Julio López
Disciplina MC889
Extensão do Algoritmo de Euclides
28−1 mod 75?
ti
i ri qi si
0 75 − 1
0
1
1 28 2 0
2 19 1 1 −2
3 9 2 −1 3
4 1 9 3 −8
3 × 75 − 8 × 28 = 1
28−1 mod 75 = −8 mod 75 = 67.
Julio López
Disciplina MC889
Inverso Multiplicativo
Entrada: inteiros a, b.
Saı́da: inteiro s onde 1 = sa mod b
1. a0 ← a; b0 ← b; s0 ← 1; s ← 0;
2. q ← ba0 /b0 c; r ← a0 − qb0 ;
3. enquanto r > 0 faça
3.1 temp ← s0 − qs mod b; s0 ← s; s ← temp;
3.2 a0 ← b0 ; b0 ← r ; q ← ba0 /b0 c; r ← a0 − qb0 ;
4. se r 6= 1 então a não tem inverso multiplicativo;
señao retorne (s).
Julio López
Disciplina MC889
Algoritmo Binário do MDC (Stein, 1961)
Entrada: inteiros a, b.
Saı́da: inteiro r , onde r = mdc(a, b).
1. u ← a; v ← b; k ← 1.
2. enquanto ambos u e v sejam pares faça
2.1 u ← u/2; v ← v /2; k ← 2k.
3. enquanto u 6= 0 faça
3.1 enquanto u seja par faça u ← u/2.
3.2 enquanto v seja par faça v ← v /2.
3.3 se u ≥ v faça u ← u − v ; senão v ← v − u.
4. retorne (r = kv )
Julio López
Disciplina MC889
Algoritmo Binário do MDC
mcd(18, 4) =?
u
18
9
9
8
..
.
v
4
2
1
1
..
.
1
0
1 2
1 2
k
1
2
2
2
..
.
mdc(18, 4) = kv = 2 × 1 = 2
Julio López
Disciplina MC889
Grupos
Definição 8: Um grupo é formado por um conjunto G e uma
operação +, com as seguintes propriedades, para todos a, b, c ∈ G:
1
(fechamento) a + b ∈ G;
2
(associatividade) (a + b) + c = a + (b + c);
3
(existência de elemento neutro ou identidade) existe um
elemento em G, denotado 0, tal que a + 0 = a;
4
(existência de inversos) para todo a ∈ G, existe em G um
elemento denotado −a, tal que a + (−a) = 0.
Um grupo é abeliano se a + b = b + a para todos a, b ∈ G.
Julio López
Disciplina MC889
Grupos (cont.)
Exemplos de grupos são:
números inteiros, racionais e reais com a soma usual;
os elementos de Zn = {0, 1, 2, . . . , n − 1}, n > 0, com a
operação de soma módulo n;
os elementos de Z∗p = {1, 2, . . . , p − 1}, p > 1, primo, com a
operação de multiplicação módulo p.
Julio López
Disciplina MC889
Grupos aditivos e multiplicativos
Denotaremos o grupo definido acima por (G, +), ou
simplesmente G, quando a operação + estiver subentendida
no texto.
Essa definição usa a notação aditiva, isto é, a + a + a + a é
denotado por 4a, 0 é a identidade, e 0 · a = 0.
Poderı́amos ter usado uma notação multiplicativa, onde a
operação do grupo seria denotada ’·’. Assim, a · a · a (ou aaa)
seria denotado por a3 , o elemento identidade seria 1, e a0 = 1.
Como já ficou claro, essas não são necessariamente as operações
usuais de soma e multiplicação.
Julio López
Disciplina MC889
Grupos aditivos e multiplicativos
O número de elementos de G é a sua ordem. Se a ordem é
finita, então G é um grupo finito.
A ordem de um elemento a ∈ G é o menor inteiro positivo t
tal que ta = 0. É um fato bem conhecido que a ordem de um
elemento divide a ordem do grupo.
Quando, para um grupo finito G de ordem n, existe um
elemento α de ordem n, dizemos que G é cı́clico e que α é um
gerador de G.
Julio López
Disciplina MC889
Exemplo:
G = Z∗7 = {1, 2, 3, 4, 5, 6}
A ordem do grupo (Z∗7 , ·) é 6;
A ordem do elemento 2 é 3: 23 ≡ 8 ≡ 1 mod 7;
A ordem do elemento 3 é 6: 36 ≡ 1 mod 7;
portanto, o grupo (Z∗7 , ·) é cı́clico, com gerador 3.
Z∗7 = {3i mod 7; i = 1, 2, 3, 4, 5, 6}
Julio López
Disciplina MC889
Exercı́cios:
Calcule 1093987656544168 × 9996543298765002 mod 1000.
Calcule em Z11 o número 8 × 7 − 10/6.
Prove: se c = 2k a + b, 0 ≤ b < 2k , então c ≡ b mod 2k .
Calcule 21000 − 1 mod 24 .
Calcule 312 mod 23.
Determine números d, s e t tais que
d = mdc(234, 26) = 234 × s + 26 × t.
Calcule o inverso multiplicativo de 17 em Z∗123 .
Implemente em C a extensão do algoritmo de Euclides.
Julio López
Disciplina MC889
Corpos finitos
Definição 9: Um corpo é formado por um conjunto F e duas
operações, ‘+’ e ‘·’, satisfazendo as seguintes propriedades:
(F, +) é um grupo abeliano com identidade 0;
(F \ {0}, .) é um grupo abeliano com identidade 1; e
a operação · é distributiva sobre a operação +, isto é,
a · (b + c) = a · b + a · c, para todos a, b, c ∈ F.
Números racionais, reais e complexos são exemplos de corpos
infinitos.
A ordem de um corpo finito é o número de elementos em F.
Quando a ordem é finita dizemos que o corpo é finito.
Julio López
Disciplina MC889
Corpos finitos
Sejam a, b dois elementos de um corpo, finito ou não. Então
a − b é equivalente a a + (−b), onde −b é o (único) inverso
aditivo de b;
a/b é equivalente a a.(b −1 ), onde b −1 é o (único) inverso
multiplicativo de b;
ka denota a adição de k parcelas iguais a a;
ak denota a multiplicação de k parcelas iguais a a, onde
a0 = 1.
Julio López
Disciplina MC889
Corpos finitos - existência
Existe um corpo finito de ordem q, se e somente se q = p m
para algum primo p e inteiro m > 0.
O primo p é a caracterı́stica de F.
Quando q é primo, i.e. m = 1, dizemos que o corpo é primo.
Quando m > 1, o corpo é de extensão.
Denotamos o corpo finito de ordem q por Fq .
Julio López
Disciplina MC889
Corpos finitos - exemplos
O conjunto Zp , p primo, com as operações de soma e
multiplicação módulo p formam o corpo primo Fp de ordem p.
Exemplos de primos: (NIST)
p = 2192 − 264 − 1
p = 2521 − 1
Julio López
Disciplina MC889
Corpos binários
Definição 10: O corpo binário F2m é formado pelos polinômios
em uma variável z de grau máximo m − 1, cujos coeficientes são 0
ou 1. As duas operações associadas são as de soma e multiplicação
de polinômios, com as seguintes restrições:
os coeficientes do polinômio resultante são reduzidos módulo
2;
o resultado da multiplicação de dois polinômios deve ser
tomado módulo um polinômio irredutı́vel f (z) de grau m. Isto
é, f (z) não é o produto de dois polinômios binários de grau
menor que m.
Julio López
Disciplina MC889
Corpos finitos - exemplos
Corpo Finito:
F2m = {
m−1
X
ai x i | ai ∈ Z2 },
i=0
f (x) = x m + r (x) polinômio irredutı́vel
Exemplo: m = 3, F23 , f (x) = x 3 + x + 1
F23 = {a2 x 2 + a1 x + a0 | ai ∈ {0, 1}}
= {0, 1, x, x + 1, x 2 , x 2 + 1, x 2 + x, x 2 + x + 1}
= {000, 001, 010, 011, 100, 101, 110, 111}
Julio López
Disciplina MC889
Corpos finitos - exemplos
Os elementos não nulos de um corpo finito Fq , juntamente
com a multiplicação do corpo, formam um grupo cı́clico,
denotado por Fq ∗ .
Portanto, existe para esse grupo pelo menos um gerador α,
isto é,
Fq∗ = {αi : 0 ≤ i ≤ q − 2}.
Julio López
Disciplina MC889
Problema do logaritmo discreto
Definição 11: (Problema do logaritmo discreto) Dados elementos
a, b de um grupo (G , .), tais que b = al , o problema do logaritmo
discreto é o de encontrar l conhecendo a e b apenas.
Em Z∗p : y = αx mod p2048 , calcular x onde p2048 é um primo
de 2048 bits.
Os métodos conhecidos para o cálculo do logaritmo discreto
em Fq∗ são todos muito ineficientes quando q é muito grande,
da ordem de centenas de dı́gitos. Para outros grupos o cálculo
é muito fácil, por exemplo, em (Zn , +).
Julio López
Disciplina MC889