Algoritmos em Teoria dos Nmeros e Criptografia de chave pblica

Notação 1. Denotamos por ℤ o conjunto dos números inteiros. Temos as funções (operações) +, ⋅ : ℤ × ℤ → ℤ tais que valem as seguinte propriedades:

Associatividade:: ∀a,b,c ∈ ℤ;a + (b + c) = (a + b) + c e a⋅ (b⋅c) = (a⋅b) ⋅c.
Comutatividade:: ∀a,b ∈ ℤ;a + b = b + a e a ⋅ b = b ⋅ a.
Distributiva:: ∀a,b,c ∈ ℤ;a ⋅ (b + c) = a ⋅ b + a ⋅ c.
Elemento neutro da adição:: ∀a ∈ ℤ;a + 0 = a e 0 é o único inteiro que satisfaz essa sentença.
Simétrico aditivo:: ∀a ∈ ℤ∃!b ∈ ℤ;a + b = 0. b é denotado por −a.
Elemento neutro do produto:: ∀a ∈ ℤ;a ⋅ 1 = a e 1 é o único inteiro que satisfaz essa sentença.
Cancelativa:: ∀a≠0,b,c ∈ ℤ;a + b = a + c ⇒ b = c e a ⋅ b = a ⋅ c ⇒ b = c.
Tricotomia: se a < b denota a - b = c para algum inteiro c > 0: ∀a,b ∈ ℤ;a < b ou a = b ou b < a.
≤ é uma relação de ordem total:: ≤ é reflexiva:; ∀a ∈ ℤ;a ≤ a.; ≤ é antissimétrica:; ∀a,b ∈ ℤ;a ≤ b e b ≤ a ⇒ a = b.; ≤ é transitiva:; ∀a,b,c ∈ ℤ;a ≤ b e b ≤ c ⇒ a ≤ c.
≤ é compatível com +:: ∀a,b,c ∈ ℤ;a ≤ b ⇒ a + c ≤ b + c.
≤ é compatível com ⋅ em ℤ⁺:: ∀a,b,c ∈ ℤ;a ≤ b e 0 ≤ c ⇒ a ⋅ c ≤ b ⋅ c.
Princípio da Boa-Ordem:: Todo subconjunto S ⊆ ℤ não-vazio contém um elemento mínimo m , i.e., tal que m ≤ a para todo a ∈ S.

Exercício 1. Prove a partir das propriedades acima

∀a ∈ ℤ;a ⋅ 0 = 0.
∀a,b ∈ ℤ;a ⋅ b = 0 ⇒ a = 0 ou b = 0.
∀a,b ∈ ℤ;a ⋅ b = 1 ⇒ a=b=1 ou a=b=-1.
∀a ∈ ℤ; − (−a) = a.
∀a,b ∈ ℤ;(−a) ⋅ b = −(a ⋅ b) = a ⋅ (−b).
∀a,b ∈ ℤ;(−a) ⋅ (−b) = a ⋅ b.
∀a,b ∈ ℤ;a ⋅ b = 0 ⇒ a = 0 ou b = 0.
∀a ∈ ℤ;a ≤ 0 ⇒−a ≥ 0 e a ≥ 0 ⇒−a ≤ 0.
∀a ∈ ℤ;a² ≥ 0.
Não existe inteiro n tal que 0 < n < 1 .
(Propriedade arquimediana) Para quaisquer inteiros a,b tal que b≠ 0 , existe um inteiro n tal que n b > a .

Exercício 2 (módulo ou valor absoluto) . Definimos ∀a ∈ ℤ |a| = a se a ≥ 0 e |a| = −a caso contrário. Prove que para a,b ∈ ℤ:

|a|≥ 0 e |a| = 0 se e só se a = 0.
−|a|≤ a ≤|a|.
|− a| = |a|.
|ab| = |a||b|.
|a + b|≤|a| + |b|.
||a|−|b||≤|a − b|.

Notação 2. Denotamos por ℤ⁺ o conjunto dos números inteiros positivos, i.e., inteiros maiores que 0. Os inteiros menores ou iguais a 0 são ditos não-positivos. Analogamente, definimos os inteiros negativos e os inteiros não-negativos.

Assumimos que os inteiros são representados numa base b ∈ ℤ⁺, b > 1. Assim o tamanho da representação de n é ⌈log n⌉
b + 1.

Se, e.g., um algoritmo que recebe como entrada inteiros n₁,n₂,…,n_k é de tempo polinomial no pior caso se a complexidade de tempo desse algoritmo é expressa por um polinômio em ⌈log n1⌉
b , ⌈log n2⌉
b ,…, ⌈log nk⌉
b .

Exemplo 1. Para os algoritmos aprendidos na escola:

a + b:: O(max{log a,log b}).
a × b:: O(log a ⋅ log b).
a ÷ b:: O(log b ⋅ log q), onde q é o quociente da divisão.

Observação 1. Para a notação assintótica, uma entrada grande significa que a grandeza dos números da entrada é grande, ao contrário de ordenação, por exemplo, onde uma entrada grande significa uma entrada com muitos números para serem ordenados.

1.1. Divisibilidade.

Sejam a,b ∈ ℤ.

Definição 3 (divide, divisor e múltiplo). b divide a se existe c ∈ ℤ tal que bc = a.

Nesse caso, dizemos que b é um divisor de a, que c é o quociente e que a é múltiplo de b.

Notação 4. Escrevemos ba para b divide a.

Observação 2. 0 |
| a se e somente se a = 0 e nesse caso 0c = 0 para todo c ∈ ℤ.

Proposição 1. Se ba e a≠0 então |b|≤|a|.

Demonstração. Se ba e a≠0 então |a| = |b||c| > |b|. ♦

Corolário 2. Se b |
| 1 então b = 1 ou b = −1.

Corolário 3. Se a |
| b e b |
| a então a = ±b.

Exercício 3. Prove:

aa.
Se ab e bc então a| c.
Se ab e cd então ac| bd.
Se ab então a|mb ∀m ∈ ℤ.
Se ab e ac então a| (mb + nc) ∀m,n ∈ Z.
ab se e só se a|b|.

Definição 5 (elemento mínimo). Seja S ⊂ ℤ. Dizemos que m ∈ S é um elemento mínimo de S se m ≤ a ∀a ∈ S.

Observação 3. Nem todo subconjunto de ℤ tem elemento mínimo.

Notação 6. minS denota o elemento mínimo de S, quando existe.

Teorema (Teorema da Divisão). Para todo inteiro a e todo inteiro positivo b existe um único inteiro q e existe um único inteiro r com 0 ≤ r < b tal que

a = bq+ r.

(1)

Demonstração. Em dois casos:

1)a ≥ 0: Defina o conjunto

S = {a − bx : x ∈ ℤ,a − bx ≥ 0}.

(2)

Como a ≥ 0 temos a ∈ S (x = 0), portanto S≠∅.

Tome r = minS, que existe pelo Princípio da Boa-Ordem.

r ∈ S implica que ∃q ∈ ℤ tal que em r = a − bq ≥ 0, pela definição de S.

Resta mostrar que r < b. Suponha que r ≥ b; então r −b = a−bq −b = a−b(q + 1) ≥ 0, portanto a − b(q + 1) ∈ S, mas r − b < r contrariando o fato de r ser elemento mínimo.

Note que se a = bq′ + (r + k) então k ≥ b.

2)a < 0: pelo caso 1, temos que existem únicos inteiros q e r tais que |a| = bq + r e 0 ≤ r < b.

Se r = 0 então −|a| = a = b(−q) + r, senão −|a| = (−q)b − r = (−q − 1)b + (b − r) e 0 ≤ b − r < b. ♦

Notação 7. No teorema acima

⌊a∕b⌋ = q é o quociente da divisão
a modb = r é o resto é o resto.

Exercício 4. Escreva um algoritmo Int_Div(a,b) que devolve q e r como no teorema acima, de complexidade O(log(a)log(b)).

Exercício 5 (Teorema da Divisão). Prove o teorema 1.1 para b≠0: Para todo inteiro a e todo inteiro não-nulo b existe um único inteiro q e existe um único inteiro r com 0 ≤ r < |b| tal que a = bq + r.

Definição 8 (Classes de equivalência mod b). Dados b ∈ ℤ⁺ e r ∈ ℤ defina

[r]b = {bq+ r: q ∈ ℤ }.

(3)

Exercício 6. Prove que

b−⋃1 [r]b = ℤ r=0

(4)

e que para r e s inteiros e distintos, 0 ≤ r,s ≤ b − 1

[r]b ∩ [s]b = ∅.

(5)

Portanto, {[0]b,[1]b,...,[b− 1]b} é uma partição dos inteiros.

Exercício 7. Mostre que a relação definida por

m ≡ n (mod b)

(6)

se e somente se m ∈ [n]_b para todos m,n ∈ ℤ, é uma relação de equivalência.

1.2. MDC.

Notação 9. Para todo a ∈ ℤ denote por D(a) o conjunto dos divisores de a

D (a) = {m ∈ ℤ : m|a}.

(7)

Para inteiros a e b temos 1 ∈ D(a) ∩ D(b) e se ambos não são nulos temos para todo m ∈ D(a) ∩ D(b) que m ≤ max{|a|,|b|} pela proposição 1, portanto está definido maxD(a) ∩ D(b) para quaisquer a,b ∈ ℤ (justifique).

Definição 10 (mdc). Para a,b ∈ ℤ

( |{0, se a = b = 0, mdc (a,b) = |max D (a)∩D (b), caso contr´ario. (

(8)

Notação 11. Para a,b ∈ ℤ

(9) aℤ = {ax: x ∈ ℤ } (10) aℤ+ bℤ = {ax+ by: x,y ∈ ℤ }.

Exemplo 2. Com a notação acima, [r]_b = bℤ + r = {bx+ r: x ∈ ℤ} .

Teorema. Sejam a e b inteiros e d = mdc(a,b). Então

aℤ + bℤ = dℤ.

(11)

Demonstração. O caso a = b = 0 é trivial. Vamos supor que a≠0.

Primeiro, vamos mostrar que aℤ + bℤ = dℤ para algum d ∈ ℤ; em seguida, que d = mdc(a,b).

Como (aℤ + bℤ) ∩ ℤ⁺≠∅ (justifique) podemos aplicar o Princípio da Boa Ordem (PBO) e tomar d o menor elemento positivo de aℤ + bℤ.

d ∈ aℤ + bℤ ⇒ ∃x0,y0 ∈ ℤ;d = ax0 + by0

(12)

Claramente dℤ ⊆ aℤ + bℤ. Vamos mostrar que dℤ ⊇ aℤ + bℤ.

Tome um elemento c de aℤ + bℤ; existem inteiros x₁ e y₁ tais que c = ax₁ + by₁. Pelo Teorema da Divisão existem inteiros q e r tais que c = dq + r, onde 0 ≤ r < d, e

r = c− dq = ax1 + by1 − (ax0 + by0)q = a(x1 − x0q)+ b(y1 − y0q) ∈ aℤ + bℤ,

(13)

como 0 ≤ r < d e d é mínimo deduzimos que r = 0. Portanto c = dq ∈ dℤ.

Resta mostrar que d = mdc(a,b).

Do resultado acima temos que existem inteiros x e y tais que a = dx e b = dy, portanto, d ∈ D(a) ∩ D(b) por definição, logo d ≤ mdc(a,b). Por outro lado, existem inteiros m e n tais que d = am + bn portanto mdc(a,b)d (exerc. 3 (5)). Da proposição 1 mdc(a,b) ≤ d, logo, mdc(a,b) = d. ♦

Corolário 4. Dados inteiros a, b e n a equação ax+by = n admite solução inteira se e somente se mdc(a,b)n.

Corolário 5 (Teorema de Bézout). Existem inteiros x e y tais que ax + by = mdc(a,b).♦

Exercício 8. Determine se é verdadeiro ou falso as igualdades ∀a,b,c ∈ ℤ:

mdc(a,b) = mdc(b,a).
mdc(a,1) = 1.
mdc(a,b + c) = mdc(a,b) + mdc(a,c).
mdc(a,ka) = |a|, para todo k ∈ ℤ.
mdc(a,bc) = mdc(a,b)mdc(a,c).
mdc(a,−b) = mdc(−a,b) = mdc(a,b).
mdc(ac,bc) = mdc(a,b)|c|.
mdc(a,b) = mdc(|a|,|b|).

Exercício 9. (Teorema de Euclides) Sejam a,b,c ∈ ℤ tais que abc. Prove que se mdc(a,b) = 1 então ac.

Exercício 10. Mostre que se mdc(a,c) = 1 e mdc(b,c) = 1 então mdc(ab,c) = 1.

1.3. Algoritmo de Euclides.

O seguinte algoritmo é conhecido como Algoritmo de Euclides (circa 300 aC). Ele determina o mdc de dois inteiros quaisquer. De saída, usamos o exercício 8 item (8), mdc(a,b) = mdc(|a|,|b|) para fazer as contas nos inteiros não-negativos.

_____________________________________________________________________

    Dado um par de inteiros $(a,b)$
    Devolve $mdc (a,b)$ .

    1   $a ← |a|$ ;
    2   $b ← |b|$ ;
    3  se $b = 0$ então devolva( $a$ );
    4  senão devolva(Euclides $(b,a mod b)$ ).

_____________________________________________________________________

Figura 1: Euclides(a,b).

O algoritmo termina pois 0 ≤ a modb < b, pelo Teorema da Divisão, logo o valor da variável b decresce estritamente a cada iteração.

Exemplo 3. Nas tabelas abaixo cada linha mostra o valor das variáveis em cada rodada.

a	b


7	5
5	2
2	1
1	0

a	b


8	5
5	3
3	2
2	1
1	0

a	b


9	5
5	4
4	1
1	0

a	b


5	9
9	5
5	4
4	1
1	0

Note que se a < b então na primeira chamada teremos a ← b e b ← a, também note que mdc(a,0) = |a|, ∀a ∈ ℤ. Portanto, para provar a correção e a complexidade do algoritmo de Euclides, podemos assumir que a > b > 0.

É fácil deduzir que o Algoritmo de Euclides funciona corretamente do resultado abaixo.

Teorema. Se a e b > 0 são inteiros então

d|a e d|b ⇔ d|b e d|a modb.

(14)

Demonstração. Do Teorema da Divisão a modb = a − bq para algum q ∈ ℤ. Portanto (exerc. 3 item (5)) d |
| a e d |
| b ⇒ d|b e d |
| a modb.

Corolário 7. Se a e b > 0 são inteiros então mdc(a,b) = mdc(b,a modb).

Demonstração. Faça d = mdc(a,b). Temos que da e db, portanto, db e da modb. Pelo corolário 6 do teorema 1.2 temos dmdc(b,a modb).

Agora, faça d = mdc(b,a modb). Pelo teorema acima temos que d |
| a e d |
| b, portanto, dmdc(a,b), pelo corolário 6 do teorema 1.2.

Pelo corolário 5 da proposição 1 mdc(a,b) = mdc(b,a modb). ♦

Teorema. Se a ≥ b > 1, então o número de chamadas recursivas no Algoritmo de Euclides é no máximo 2lg(b).

Demonstração. Tome r = a modb. Vejamos que r < a∕2.

Se b ≤ a∕2 então a afirmação segue do Teorema da Divisão. Se b > a∕2 então o Teorema da Divisão nos dá a = b ⋅ 1 + (a − b), assim r = a − b < a∕2.

Assim, após 2 chamadas consecutivas a grandeza da entrada cai pela metade

′ (a,b) ↦→ (b,r) ↦→ (r,r )

(15)

com r < a∕2 e r′ < b∕2. Após 2t passos teremos que a entrada é limitada por (a∕2^t,b∕2^t). Logo, com 2lg b passos o algoritmo terminou. ♦

Corolário. O número de operações no pior caso do Algoritmo de Euclides com dois números de tamanho n é O(n³).

Demonstração. Pelo teorema são O(n) divisões, cada uma com custo O(n²). ♦

No que segue, f_k é o k-ésimo número de Fibonacci, definido por f₁ = 1, f₂ = 1 e f_k = f_k−1 + f_k−2, ∀k ≥ 3.

Exercício 11 (Pior caso do Algoritmo de Euclides). Mostre que o algoritmo de Euclides com entradas f_k+2 e f_k+1 executa k chamadas recursivas. Prove o seguinte

Teorema (Teorema de Lamé). Se (a,b) é o menor par de inteiros positivos que fazem a algoritmo de Euclides executar k chamadas recursivas então (a,b) = (f_k+1,f_k+2).

Observação 4. Considerando os exercícios acima, a estimativa 2lg b do teorema é superestimada em menos que 40% pois

2lgfk+1 ≈ 1,388k − 0,936

(16)

pois f_k = ∘1-∕5 {[(1 + )∕2]^k − [(1 −)∕2]^k}.

Observação 5. Uma análise mais cuidadosa1 permite concluir que o custo do algoritmo é O(log(a)log(b)).

1.3.1. Algoritmo de Euclides Estendido. O algoritmo a seguir é uma extensão do algoritmo de Euclides.

_____________________________________________________________________

  Dado um par de números inteiros $(a,b)$ não-negativos
  Devolve uma terna $(d,x,y)$ tal que $d = mdc (a,b) = ax + by$ .

  1   se $b = 0$ então devolva( $(a,1,0)$ );
  2    $(d,x,y) ←$ Euclides_estendido $(b, a mod b)$ ;
  3   devolva( $(d,y,x− ⌊a∕b⌋y)$ .

_____________________________________________________________________

Figura 2: Euclides_estendido(a,b).

Considere uma execução do algoritmo acima com entradas 99 e 78.

a	b		x	y	d


99	78	1	−11	14	3
78	21	3	3	−11	3
21	15	1	−2	3	3
15	6	2	1	−2	3
6	3	2	0	1	3
3	0	−	1	0	3

Observação 6. O número de chamadas recursivas do algoritmo estendido é o mesmo que no Algoritmo de Euclides.

Exercício 12 (Correção do algoritmo estendido). Prove que o algoritmo 2 funciona corretamente.

Para isso, suponha que (d′,x′,y′) são os valores atribuídos na linha 2.

d′ = bx ′+ (a modb )y′ = bx′ + (a− ⌊a∕b⌋b)y′ = ay′ +b(x′ − ⌊a∕b⌋y′).

(17)

A prova segue por indução.

Exercício 13 (Complexidade do algoritmo estendido). Prove que a complexidade do algoritmo 2 é O(log(a)log(b)).

Exercício 14. Escreva uma versão do algoritmo 2 para quaisquer inteiros.

Exercício 15. Escreva uma versão não recursiva dos algoritmos 1 e 2.

2. Números primos e fatoração

Definição 12 (número primo). Um número inteiro p é primo se tem exatamente dois divisores positivos: 1 e |p|.

Definição 13 (divisor próprio). Todo divisor b de a com 1 < |b| < |a| é chamado de divisor próprio de a.

Definição 14 (número composto). Um inteiro que admite divisor próprio é dito composto.

Observação 7. Decorre das definições acima que os inteiros −1, 0 e 1 não são primos nem compostos, todo outro inteiro ou é primo ou é composto.

_____________________________________________________________________

    Dado um inteiro $n$
    Devolve sim se $n$ é primo, não caso contrário.

_____________________________________________________________________

Figura 3: Problema da Primalidade.

O Problema da Primalidade pode ser resolvido em tempo polinomial. Em 2002 os indianos M. Agrawal, N. Kayal, e N. Saxena mostraram2 um algoritmo que determina se n é primo em tempo O(log ^12+εn). Esse algoritmo foge do escopo da disciplina.

Veremos algoritmos probabilísticos (devolve composto ou provavelmente primo) que são extremamente simples (envolvem conceitos que aparecerão adiante) e úteis como o teste de Miller–Rabin, de complexidade O(k × log ³n), onde k é o número de rodadas do teste. Para k = 100 a probabilidade do algoritmo devolver provável primo todas as vezes quando a entrada é composto é menor que 10⁻³⁰.

Observação 8. 10⁻³⁰ é um número muito pequeno, por exemplo, na teoria do Big-Bang é estimado que o universo tem 4.3 × 10¹⁷ segundos de idade, o universo observável (7.4 × 10²⁶ metros) contém aproximadamente 10⁸⁰ átomos.

Proposição 8. Todo inteiro a > 1 tem um divisor primo.

Demonstração. De fato, ou a é primo (e a proposição vale nesse caso) ou a tem um divisor d, 1 < d < a. Considere m o menor desses divisores (PBO). m deve ser primo, caso contrário m teria um divisor próprio que, pelo exercício 3 item (2), divide a contrariando a minimalidade de m. ♦

Lema 9. Para todo inteiro a > 1

a = p1p2 ⋅⋅⋅pn

(18)

onde p_i é primo para todo i, 1 ≤ i ≤ n.

Demonstração. Por indução em a. Se a = 2 o lema vale porque 2 é primo. Dado a > 2 suponha que o lema vale para todo inteiro entre 2 e a − 1, inclusive.

Pela proposição acima, a = pq com p primo; ou q = 1 (e o lema vale nesse caso) ou 2 ≤ q < a e pela hipótese de indução q = p₁p₂ ⋅⋅⋅ p_n, portanto, a = pp₂p_n, o que prova o lema. ♦

Lema 10. Se um primo p divide ab então pa ou pb.

Exercício 16. Prove a seguinte generalização do lema acima: Se um primo p divide a₁a₂…a_n então p |
| a_i para algum i.

Teorema (Teorema Fundamental da Aritmética). Todo inteiro positivo pode ser escrito como produto de fatores primos, e essa fatoração é única a menos da ordem dos fatores primos.

Demonstração. Suponha que existam inteiros positivos com mais de uma fatoração em primos e tome a o menor deles. Digamos que

a = p1p2⋅⋅⋅pn = q1q2 ⋅⋅⋅qm.

(19)

Pela definição de número primo, n = 1 ⇔ m = 1. Podemos assumir n,m ≥ 2. Assim p₁ |
| q₁q₂ ⋅⋅⋅ q_m e pelo exercício anterior p₁ |
| q_i para algum i e como q_i é primo temos p₁ = q_i. Pela propriedade cancelativa do inteiros (página 2) temos

p2⋅⋅⋅pn = q1q2⋅⋅⋅qi−1qi+1⋅⋅⋅qm

(20)

contrariando a minimalidade de a. ♦

Definição 15 (fatoração). A fatoração de um número inteiro a é a representação de |a| como um produto de primos. Escrevemos a fatoração agrupando os fatores iguais

a = pm1pm2⋅⋅⋅pmn 1 2 n

(21)

com p₁ < p₂ < ⋅⋅⋅ p_n. O expoente m_i é dito multiplicidade de p_i.

_____________________________________________________________________

    Dado um inteiro $n > 1$
    Devolve a fatoração de $n$ .

_____________________________________________________________________

Figura 4: Problema da Fatoração.

Não se conhece algoritmo eficiente para esse problema.

Definição 16 (primos relativos, coprimos). Dois inteiros a e b são primos relativos, ou coprimos se mdc(a,b) = 1.

Exercício 17. Mostre que n contém no máximo log ₂n fatores primos.

Exercício 18. (Crivo de Eratóstenes) Prove que o seguinte algoritmo determina todos os números primos até n

__________________________________________

        Dado um número inteiro $n ≥ 2$
        Devolve todos os números primos entre $2$ e $n$ .

        1  liste todos os números de $2$ até $n$ ;
        2  para cada $i = 2,3,...,√n-$
        3      se $i$ está na lista
        4          então apague os múltiplos de $i$ maiores que $i$

_____________________________________________________________________

Figura 5: Crivo de Eratóstenes.

Teorema. Existem infinitos números primos.

Demonstração. Vamos mostrar que para todo inteiro positivo n existe um primo maior que n. Para tal, tome p um fator primo de n! + 1.

2.1. Números de Fermat.

Os números de Fermat são definidos por para todo inteiro n ≥ 0. Em 1640 Fermat mostrou que F_n é primo para n ∈{0,1,2,3,4} e conjeturou que esses números eram primos até que em 1732 Euler mostrou que F₅ é composto. A seguinte tabela3 mostra para quais valores de n as fatorações são conhecidas até o momento, mostra também o número de dígitos de F_n, quantos fatores primos e o número de dígitos desses fatores.

n	dígitos	fatores	dígitos dos fatores	Autores

5	10	2	3, 7	Euler 1732
6	20	2	6, 14	Landry 1880
7	39	2	17, 22	Morrison e Brillhart 1975
8	78	2	16, 62	Brent e Pollard 1981
9	155	3	7, 49, 99	Manasse e Lenstra 1993
10	309	4	8, 10, 40, 252	Brent 1995
11	617	5	6, 6, 21, 22, 564	Brent 1988

Para alguns outros números de Fermat são conhecidos alguns fatores, mas a fatoração completa ainda não é conhecida. Por exemplo, sabe-se que F₁₂ tem 5 fatores primos mais um fator composto de 1187 dígitos. O F₁₄ é o atual primeiro número de Fermat que é sabido ser composto mas que nenhum dos seus fatores é conhecido.4

Édouard Lucas, um matemático francês, provou que os fatores primos de um número de Fermat são da forma k2ⁿ + 1. Em 1857, aos 15 anos, Lucas começou a testar a primalidade de 2¹²⁷ − 1 à mão, usando os números de Lucas. Em 1876, após 19 anos de trabalho, provou que 2¹²⁷ − 1 é primo.

Exercício. Complete o seguinte argumento para dar uma prova da infinitude de números primos: Os números de Fermat satisfazem a recursão ∏ _i=0ⁿ⁻¹F_i = F_n−2 para todo n ≥ 1 (prove). Se m divide F_i e F_n para i < n então m2 (prove). Os números de Fermat são ímpares, portanto m = 1, i.e., quaisquer dois números de Fermat têm máximo divisor comum igual a 1. Assim, existem infinitos números primos (prove).

Aritmética modular

3. Inteiros módulo n

Lembrando o exercício 7, dado n ∈ ℤ⁺ a relação ≡ (mod n) definida para quaisquer a,b ∈ ℤ por

a ≡ b (mod n) ⇔ a ∈ nℤ + b

(22)

é uma relação de equivalência sobre ℤ, ou seja, para inteiros a,b,c valem

a ≡ a (mod n),
a ≡ b (mod n) ⇒ b ≡ a (mod n) e
a ≡ b (mod n) e b ≡ c (mod n) ⇒ a ≡ c (mod n).

Exercício 19. Provem que são equivalentes

a ≡ b (mod n);
na − b;
a modn = b modn.

Proposição 11. Sejam n > 0 um inteiro fixo. Para quaisquer a,b,c,d inteiros valem as seguintes propriedades:

a ≡ b (mod n) ⇒ a + c ≡ b + c (mod n);
a + c ≡ b + c (mod n) ⇒ a ≡ b (mod n);
a ≡ b (mod n) e c ≡ d (mod n) ⇒ ac ≡ bd (mod n).

Demonstração. Se a = nq + b então a + c = nq + b + c, portanto a + c ∈ nℤ + b + c. Isso prova (1).

Se a + c = nq + b + c então a = nq + b, portanto a ∈ nℤ + b. Isso prova (2).

Se a = nq+b e c = np+d então ac = n(npq+qd+pb)+bd, portanto ac ∈ nℤ+bd. Isso prova (3). ♦

Note que o item (2) corresponde a propriedade cancelativa dos inteiros, entretanto, não vale a versão multiplicativa dessa propriedade, ou seja, para c ⁄≡ 0 (mod n)

ac ≡ bc (mod n) ⁄⇒ a ≡ b (mod n)

(23)

por exemplo, 5 ⋅ 3 ≡ 3 ⋅ 3 (mod 6) mas 3 ⁄≡ 5 (mod 6).

Proposição 12. Sejam n > 0 um inteiro fixo e a,b,c inteiros. Então

mdc(c,n) = 1 e ac ≡ bc (mod n) ⇒ a ≡ b (mod n).

(24)

Demonstração. De ac = nq + bc temos que (a − b)c = nq, portanto c |
| nq. De mdc(c,n) = 1 temos, pelo Teorema de Euclides (exerc. 9) que c |
| q, portanto, existe z ∈ ℤ tal que cz = q. Assim, ac = nzc + bc e a proposição segue da propriedade cancelativa dos inteiros. ♦

Exercício 20. Prove que se a ≡ b (mod n) e c ≡ d (mod n) então a + c ≡ b + d (mod n).

Exercício 21. Prove que se a ≡ b (mod n) então a^m ≡ b^m (mod n) para todo m ∈ ℤ⁺.

Exercício 22. Mostre que se p > 1 é primo então

ab ≡ 0 (mod p) ⇒ a ≡ 0 (mod p) ou b ≡ 0 (mod p).

(25)

Dê exemplos onde a implicação falha no caso de p não ser primo.

Exemplo 4. Vamos determinar o resta da divisão de 5⁶⁰ por 26.

Mas 5² ≡−1 (mod 26), portanto 5⁴ ≡ 1 (mod 26). De 5⁶⁰ = 5⁴¹⁵ temos 5⁶⁰ ≡ 1 (mod 26).

Exemplo 5 (divisibilidade por 3). Dado n ∈ ℤ⁺, n = d_t−1 ⋅ 10^t−1 + d_t−2 ⋅ 10^t−2 + ⋅⋅⋅ + d₁ ⋅ 10 + d₀ com d_i ∈ {0,1,...,9} .

De 10 ≡ 1 (mod 3) temos que 10^m ≡ 1 (mod 3), portanto, d⋅10^m ≡ d (mod 3). Logo n ≡∑ _id_i (mod 3).

Exemplo 6 (divisibilidade por 11). Seja n como acima. De 10 ≡ −1 (mod 11) temos que 10^m ≡ (−1)^m (mod 11), portanto n ≡ d₀−d₁+d₂− ⋅⋅⋅ ±d_t−1 (mod 11).

Exemplo 7 (divisibilidade por 7). Para congruências módulo 7 temos 10 ≡ 3 (mod 7), 10² ≡ 2 (mod 7), 10³ ≡ −1 (mod 7) , 10⁴ ≡ −3 (mod 7), 10⁵ ≡ −2 (mod 7), 10⁶ ≡ 1 (mod 7) e daqui em diante os restos se repetem.

Assim, n é divisível por 7 se d₀ + 3d₁ + 2d₂ −d₃ − 3d₄ − 2d₅ + d₆ + 3d₇ + 2d₈ − d₉ − 3d₁₀ ⋅⋅⋅ for divisível por 7.

Exemplo 8 (F₅ é composto). F₅ = 2^2⁵ + 1 = 2³² + 1. Dividindo 2¹⁶ = 65.536 por 641 temos resto 154 e 154² ≡ 640 (mod 641), logo 2³² ≡ 640 (mod 641), portanto 6412³² + 1.

Exercício 23. Prove que se p é primo então p (p)
k para todo k, 0 < k < p.

Exercício 24. Use o exercício acima e o teorema binomial de Newton para provar que

(a+ b)p ≡ ap + bp (mod p)

(26)

para quaisquer inteiros a e b.

Exercício 25. Use indução em n, n > 1, e os exercícios anteriores para provar que

np ≡ n (mod p).

(27)

Exercício 26. Prove o resultado do exercício acima usando a seguinte estratégia: Imagine números escritos na base n, com no máximo p dígitos. Ponha dois números na mesma caixa se eles resultam um do outro de um deslocamento cíclico. Quantos estarão em cada caixa?

3.1. Pequeno Teorema de Fermat.

Seja a ∈ ℤ e p um primo que não divide a. Então

p−1 a ≡ 1 (mod p).

(28)

Demonstração. Considere os múltiplos de a

m1 = a,m2 = 2a, ⋅⋅⋅mp−1 = (p− 1)a.

(29)

Se dois deles são congruentes módulo p, digamos m_r ≡ m_s (mod p) com 1 ≤ r < s ≤ (p − 1), então r ≡ s (mod p), pois mdc(a,p) = 1 e vale a lei cancelativa (propo. 12), mas isso é um absurdo.

Se, para algum 0 < r < p ocorrer m_r ≡ 0 (mod p) então pr pois mdc(a,p) = 1 (lema 10), o que é um absurdo.

Assim, m₁,m₂,…,m_p−1 devem ser congruentes a 1,2,…,p − 1 em alguma ordem. Logo

m1m2 ⋅⋅⋅mp −1 ≡ 1 ⋅2⋅⋅⋅(p − 1) (mod p)

ou seja

1⋅2⋅⋅⋅(p − 1)(ap−1 − 1) ≡ 0 (mod p).

(30)

Como p ⁄1 ⋅ 2 ⋅⋅⋅ (p − 1) devemos ter p(a^p−1 − 1) (propo. 12), isto é, a^p−1 ≡ 1 (mod p). ♦

Corolário. Para todo a ∈ ℤ e todo primo p

ap ≡ a (mod p).

(31)

3.2. Exponenciação modular.

Antes de explorarmos as possíveis aplicações do teorema de Fermat, devemos notar que computar 2ⁿ⁻¹ é extremamente custoso quando n é grande, digamos que com 100 dígitos; isso daria cerca de 10¹⁰⁰ passos o que é impossível de realizar. Em geral a^b avaliado por multiplicações repetidas custa Ω(b(log a)²).

Um jeito mais esperto é “elevar ao quadrado” repetidas vezes, por exemplo, para calcular 2²⁴ podemos começar com 2³ = 8, elevá-lo ao quadrado, o que resulta 2⁶ = 62, elevá-lo ao quadrado, o que resulta 2¹² = 4.096, e elevá-lo ao quadrado, o que resulta 2²⁴ = 16.777.216. Outro exemplo, para calcular 2²⁹ com esse método de trás pra frente teríamos 2²⁹ = 2 ⋅ 2²⁸, a raiz de 2²⁸ é 2¹⁴ cuja raiz é 2⁷ que é 2 ⋅ 2⁶ que por sua vez é 2² ⋅ 2³. Assim, se n é representado com k bits então 2ⁿ é calculado usando menos que 2k multiplicações.

A segunda dificuldade é o tamanho que esses números podem assumir. Nesse caso, se queremos verificar divisão por n então podemos tomar o resto da divisão por n sempre que uma operação resulta num número maior que n. Por exemplo, para verificar se 25 |
| 2²⁴ − 1 começamos como acima, 2³ = 8 que ao quadrado resulta 2⁶ = 64 e 64 mod25 = 14, elevando ao quadrado temos 2¹² e 14² = 196, como 196 mod25 = 21 no próximo passo obtemos 2²⁴ por um lado e 21² = 441 pelo outro; 441 mod25 = 16 e como 25 ⁄16 − 1 deduzimos que 25 não é primo.

Resumindo, a^b é avaliado com base na observação de que

{ (ab∕2)2 se b ´e par, ab = a ⋅ab− 1 se b ´e´impar.

(32)

    Dado inteiros não-negativos $a,b$ e $n > 0$
    Devolve $ab mod n$ .

    1   se $b = 0$ então devolva(1);
    2   se $b$ então devolva( $ExpModRec (a,b∕2,n )2 mod n$ );
    3   devolva( $a ⋅ExpModRec (a,b − 1,n ) mod n$ ).

_____________________________________________________________________

Figura 6: ExpModRec(a,b,n)

Exercício 27. Provar no algoritmo acima O(log b) quadrados são executados, ∑ _ib_i multiplicações por a são executadas, onde b_k…b₁b₀ é a representação binária de b e que a complexidade é O((log b)(log a)²).

O seguinte algoritmo é uma versão iterativa do algoritmo acima. Seja b_kb_k−1…b₁b₀ a representação binária de b, b = ∑ _i=0^kb_i2ⁱ, e defina

i−1 i−2 0 ci = bkc2 + bk− 12 + ⋅⋅⋅+ bk− i+12 di = a i modn

para i ≥ 1 com c₀ = 0 e d₀ = 1. Dessa forma podemos calcular d_i+1 a partir de d_i da seguinte forma

se b_k−i = 0 então c_i+1 = 2c_i, senão c_i+1 = 2c_i + 1;
se b_k−i = 0 então d_i+1 = a^c_i+1 modn = (a^c_i)² modn = d_i² modn, senão d_i+1 = a^c_i+1 modn = a ⋅ (a^c_i)² modn = a ⋅ d_i² modn.

Portanto, c_k+1 = b_k2^k + ⋅⋅⋅ + b₁2 + b₀ = b e d_k+1 = a^b modn.

Exemplo 9. Vamos usar essa estratégia para calcular 2²⁴ mod25. Primeiro, 24 em base 2 fica b = 11000.

i	1	2	3	4	5

b_i	1	1	0	0	0
c_i	1	3	6	12	24
d_i	2	8	14	21	16

Portanto 2²⁴ ≡ 16 (mod 25).

Finalmente, o algoritmo baseado nessa idéia é escrito do seguinte modo.

_____________________________________________________________________

    Dado inteiros não-negativos $a$ , $b$ e $n > 0$
    Devolve $ab mod n$ .

    1    $c ← 0$ ;
    2    $d ← 1$ ;
    3   seja $bkbk−1... b1b0$ a representação binária de $b$ ;
    4   para $i$ de $k$ até $0$ passo $− 1$ faça
    5          $c ← 2c$ ;
    6          $d ← d ⋅ d mod n$ ;
    7         se $bi = 1$ então
    8             $c ← c+ 1$ ;
    9             $d ← d ⋅ a mod n$ ;
   10   devolva( $d$ ).

_____________________________________________________________________

Figura 7: ExpMod(a,b,n)

Para provar que esse algoritmo funciona usamos a técnica do invariante do laço: imediatamente antes de cada iteração do for na linha 4 valem

c é o valor do prefixo b_kb_k−1…b_i+1;
d = a^c modn.

Inicialmente, antes da primeira rodada, o prefixo é vazio e d = 1 = a⁰ modn.

Sejam c′ e d′ os valores de c e d ao final de uma iteração, portanto antes da próxima iteração. Então c′← 2c caso b_i = 0 ou c′← 2c + 1 caso b_i = 1 de modo que c estará correto antes da próxima iteração. Se b_i = 0 então d′ = d² modn = (a^c)² modn = a^c′ modn. Se b_i = 1 então d′ = d²a modn = (a^c)²a modn = a^c′ modn. Em ambos os casos d = a^c modn antes da próxima iteração.

Para verificar o término, ao final temos i = −1, assim c = b e d = a^c modn = a^b modn.

Exercício 28. Se as entradas a,b,n têm tamanho m então o número total de operações é O(m³).

4. Sistemas de congruências

Dados inteiros a,b,n, n > 0, vamos estudar as soluções de

aX ≡ b (mod n ).

(33)

Existe inteiro x tal que ax ≡ b (mod n) se, e somente se, existe y ∈ ℤ tal que ax + ny = b. Pelo teorema 1.2, aℤ + nℤ = mdc(a,n)ℤ, portanto, ax + ny = b tem solução se e só se b ∈ mdc(a,n)ℤ.

Proposição 13. A equação aX ≡ b (mod n) admite solução se e somente se mdc(a,n) |
| b.♦

Tome d = mdc(a,n) e b₁ tal que b = b₁d. Pelo teorema de Bézout existem r,s ∈ ℤ tais que d = ar + ns, portanto ar ≡ d (mod n).

Note que x₀ = rb₁ é uma solução da equação (33) pois

ax modn = arb modn [ar ≡ d (mod n)] 0 1 = db1 modn [b = b1d] = b modn,

portanto ax₀ ≡ b (mod n) (exerc. 19). Também, x_t = rb₁ + n
d

t, para 1 ≤ t ≤ d − 1 são soluções da equação (33) pois

an | axt modn = arb1 +---t modn [d|a] d = arb1 modn [b = b1d] = ax0 modn.

Agora suponha que x seja uma solução de (33) e seja y ∈ ℤ tal que ax + ny = b. Para x₀ = rb₁ e y₀ = sb₁ vale ax₀ + ny₀ = b (verifique). Logo ax + ny = ax₀ + ny₀, donde

a(x− x0) = n (y0 − y)

(34)

e dividindo essa equação por d obtemos a₁(x − x₀) = n₁(y₀ − y), onde a₁d = a e n₁d = n. Agora, n₁ |
| a₁(x−x₀) e mdc(a₁,n₁) = 1, portanto, n₁ |
| (x−x₀), ou seja, existe t ∈ ℤ tal que x − x₀ = tn₁, portanto

n x = x0 +-t. d

(35)

Substituindo em (34)

a- y = y0 − dt.

(36)

Conseqüentemente, todas as soluções da congruência são da forma

n x0 +-dt,t ∈ ℤ.

(37)

Exercício 29. Prove que x_t ⁄≡ x_h (mod n) para h≠t, 0 ≤ h,t ≤ d − 1.

Teorema. Dados inteiros a,n, n > 0, d = mdc(a,n) e b um múltiplo de d; escrevendo d = ar + ns e b = db₁ a equação aX ≡ b (mod n) tem d soluções distintas módulo n, dadas por

{ n- } rb1 + dt modn : 0 ≤ t ≤ d− 1 .

(38)

Ademais, qualquer outra solução é congruente a alguma dessas soluções.

Demonstração. Pela proposição 13 e pelo exercício 29 resta mostrar que se x ∈ ℤ é solução então x ≡ x_h (mod n) para algum h ∈ {0,1,...,d − 1} . Mas x é solução, portanto, x = rb₁ + n
d t para algum t ∈ ℤ.

Pelo teorema da divisão t = dq + r e substituindo em x temos

n- n- x = rb1 + d (dq + r) = rb1 + nq+ d r

(39)

portanto, x modn = rb₁ + nq + n
d r modn = rb₁ + n
d r modn e como 0 ≤ r < d o teorema segue. ♦

Corolário 14. Para n > 1, se mdc(a,n) = 1 então aX ≡ b (mod n) tem única solução módulo n.

Corolário 15 (Inverso multiplicativo). Para n > 1, aX ≡ 1 (mod n) tem solução se e somente se mdc(a,n) = 1. A única solução é denotada por a⁻¹ modn.

As soluções de (33) podem ser computadas eficientemente, assim como o inverso multiplicativo, quando esses existem.

_____________________________________________________________________

    Dado inteiros $a,b,n$ com $n > 0$
    Devolve as soluções de $aX ≡ b (mod n)$ , caso existam.

    1    $(d,r,s) ←$ Euclides_estendido $(a,b)$ ;
    2   se $d||b$ então
    3         $x0 ← r(b∕d) mod n$ ;
    4        para $t$ de $0$ até $d− 1$ faça
    5             devolva( $x0 + (n∕d)t mod n$ )
    6   senão devolva(não há solução).

_____________________________________________________________________

Figura 8: Soluções de equação modular.

Esse algoritmo realiza O(log n + mdc(a,n)) operações aritméticas.

Exercício 30. Determine a complexidade do algoritmo acima.

Exercício. Mostre que o inverso multiplicativo de a módulo n pode ser encontrado em tempo O(log(a)log(n)), para todo n > 1 e a tal que mdc(a,n) = 1.

Exercício 31. Sejam a,n ∈ ℤ, b ∈ dℤ onde d = mdc(a,n), e r,s ∈ ℤ tais que d = ar + ns. Escreva a = a₁d, b = b₁d e n = n₁d. Prove que as equações

aX ≡ b (mod n ) e X ≡ rb1 (mod n1)

(40)

têm as mesmas soluções.

Teorema (Teorema chinês do resto5 ). Sejam n₁,n₂,…,n_k inteiros maiores que 1 e tais que mdc(n_i,n_j) = 1 para todos i≠j, e sejam c₁,…,c_k inteiros arbitrários. Então o sistema

X ≡ ci (mod ni), ∀i ∈ {1,2,...,k}.

(41)

tem uma solução módulo n = n₁n₂ ⋅⋅⋅ n_k.

Demonstração. Escrevemos n = N_in_i e temos mdc(N_i,n_i) = 1. Sejam r_i,s_i ∈ ℤ tais que r_iN_i + s_in_i = 1, para todo i ∈ {1,2,...,k} .

Tomamos x₀ = ∑ _i=1^kc_ir_iN_i vamos mostrar que é solução. Primeiro N_i ≡ 0 (mod n_j) ∀i≠j, logo

∑k ciriNi ≡ cjrjNj (mod nj) (∀j ∈ {1,...,k}). i=1

(42)

Ainda, de N_jr_j + n_js_j = 1 temos N_jr_j ≡ 1 (mod n_j) (∀j), logo x₀ ≡ c_jr_jN_j ≡ c_j (mod n_j) (∀j).

Agora vamos mostrar que a solução é única módulo n. Assuma que para x ∈ ℤ vale x ≡ c_i (mod n_i) para todo i. Então x ≡ x₀ (mod n_i) (∀i) donde n_i(x − x₀) (∀i), logo n(x − x₀) (justifique), ou seja x ≡ x₀ (mod n). ♦

Exemplo 10. Considere o sistema

X ≡ 2 (mod 2) X ≡ − 1 (mod 3) X ≡ 4 (mod 7).

Seguindo a notação da demonstração, n = 42, N₁ = 21, N₂ = 15 e N₃ = 6.

i	r_i	s_i

1	1	−10
2	−1	3
3	−1	7

e x₀ = 2 ⋅ 1 ⋅ 21 + (−1)(−1)14 + 4(−1)6 = 32. Ainda, toda solução inteira é da forma 32 + 42t, t ∈ ℤ.

Exercício 32. Sejam n₁,n₂,…,n_k inteiros positivos, e sejam a₁,…,a_k e b₁,…,b_k inteiros arbitrários tais que mdc(a_i,n_i) |
| b_i para todo i. Prove que o sistema

aiX ≡ bi (mod ni), ∀i ∈ {1,2,...,k} .

(43)

tem solução.

Exercício 33. Mostre que as soluções do exemplo 10 são soluções do sistema

6X ≡ 2 (mod 4) 2X ≡ 1 (mod 3) 4X ≡ 2 (mod 7).

Exemplo 11 (Partilha de senhas). O problema e dados inteiros n > k ≥ 1 determinar uma estratégia para que n pessoas partilhem uma senha s ∈ ℤ sem conhece-la de modo que

qualquer subconjunto de k pessoas permite calcular s facilmente,
para menos que k pessoas quaisquer é muito difícil computar s.

A idéia e tomar uma lista L = {m1 < m2 < ⋅⋅⋅ < mn} números inteiros tais que mdc(m_i,m_j) = 1 para todo i≠j e é possível escolher s

M < s < N

(44)

onde N = m₁m₂ ⋅⋅⋅ m_k e M = m_n−k+2m_n−k+3m_n.

Note que o produto de quaisquer k números de L é maior que N, o produto de menos que k é menor que M e s > m para todo m ∈ L. Cada pessoa recebe um par (m,s_m) com m ∈ L e s_m = s modm. Note que s > s_m.

Em um grupo de t pessoas temos o sistema

X ≡ si (mod mi) ∀i ∈ {1,2,...,t}

(45)

cuja solução x₀ ≡ s (mod m₁m₂ ⋅⋅⋅ m_t). Agora,

nesse caso m₁m₂m_t ≥ N > s e, pelo teorema chinês do resto, existe uma única solução x₀ módulo m₁m₂m_t, como s é solução x₀ = s.
nesse caso m₁m₂m_t < M < s e x₀≠s, mas como s é solução devemos ter s = x₀ + y(m₁m₂m_t), com
$M < x0 + y(m1 ⋅⋅⋅mt) < N,$ (46)

e podemos escolher os módulos de modo que esse intervalo seja muito grande, o que torna a busca por y inviável.

Exercício 34. Verifique o protocolo acima de partilha de senha para o caso k = 2 com L = {11,13,17,19,23} .

Exercício 35. Num teatro duas tropas se enfrentam numa cena de batalha. Uma tropa tem 100 mosquetes e depois de atirar tantos tiros quanto possíveis lhes sobraram 13 cartuchos. A outra tropa tem 67 mosquetes e ao fim lhes restam 32 cartuchos. Supondo que a cada salva de tiros cada soldado atirou apenas uma vez determine o número mínimo de cartuchos de cada tropa no início da apresentação.

Exercício 36. Resolva X² + 42X + 21 ≡ 0 (mod 105). Dica: fatore 105 e resolva a equação para módulo cada fator e use o teorema chinês do resto.

Exercício 37. A teoria do Biorritmo diz que os estados físico, mental e emocional de uma pessoa oscilam periodicamente, a partir do dia do nascimento, em ciclos de 23, 29 e 33 dias, respectivamente. Dado que os dias mais positivos dos ciclos físico, mental e emocional são, respectivamente, o 6^o, o 7^o e o 8^o dias de cada ciclo, quantas vezes os três ciclos estão simultaneamente no ponto máximo nos primeiros 10 anos de vida?

Exercício 38. Mostre que nas condições do teorema chinês do resto uma solução pode ser computada em tempo O(log ²n). Dica: use as fórmulas da prova do teorema e mostre que o produto de k inteiros pode ser feita em tempo O(log ²n) sem assumir que k é constante. Mostre que dados n₁,…,n_k, z e n = ∏ _in_i os inteiros z modn_i podem ser calculados em tempo O(log ²n).

Exercício 39 (Teorema Chinês do resto generalizado). Sejam n₁,n₂,…,n_k inteiros maiores que 1 e sejam c₁,…,c_k inteiros arbitrários. Então o sistema

X ≡ c (mod n ), ∀i ∈ {1,2,...,k}. i i

(47)

tem solução se e somente se c_i ≡ c_j (mod mdc(n_i,n_j)) para todo i≠j. Caso exista, a solução é única módulo mmc(n₁,n₂,…,n_k).

Exercício 40. Prove que no caso do exercício anterior a existência pode ser decidida em tempo O(log ²n) e, caso exista, a única solução modular pode ser determinada em tempo O(log ²n), onde n = n₁n₂ ⋅⋅⋅ n_k.

4.1. Inteiros módulo n.

Definição 17 (sistema completo de resíduos). S ⊂ ℤ é um sistema completo de resíduos módulo n se para todo a ∈ ℤ existe um b ∈ S tal que a ≡ b (mod n).

Exemplo 12 (sistema de completo de resíduos mod5). Alguns sistemas completos de resíduos módulo 5 são os conjuntos:

{− 2,− 1,0,1,2}, {0,1,2,3,4}, {1,2,3,4,5}, {12,24,35,− 4,18} .

Fixe um natural n > 1. Retomando a definição 8 e o exercício 6, pág. 9 temos [a]_n = [b]_n se e somente se a ≡ b (mod n) e, ainda, se [a]_n≠[b]_n então [a]_n ∩ [b]_n = ∅. Cada elemento de uma classe [ ]_n é um representante da classe, por exemplo, −2 e 10 são representantes da classe [4]₆. Como dois inteiros representam a mesma classe de resíduo módulo n se e somente se tem o mesmo resto na divisão por n o número de classes é n − 1.

Definição 18 (forma reduzida). Uma classe representada na forma [a]_n com 0 ≤ a < n dizemos que ela está no forma reduzida.

Definição 19 (ℤ_n). Dado n > 1 inteiro

ℤn = {[0]n,[1]n,[2]n,...,[n − 1]n}

(48)

é o conjunto dos inteiros módulo n. Em geral, se S é um sistema completo de resíduos módulo n

ℤn = {[a]n: a ∈ S }.

(49)

No ℤ_n introduzimos uma operação de soma e outra de multiplicação da seguinte forma

[a]n + [b]n = [a + b]n [a]n ⋅[b]n = [a ⋅b]n

Exercício 41. Mostre que as operações definidas acima não dependem da escolha dos representante das classes.

Exercício 42. Mostre que nos inteiros módulo n valem as seguinte propriedades:

Associatividade:

∀[a]_n,[b]_n,[c]_n ∈ ℤ_n

(50) [a]+ ([b] + [c]) = ([a] + [b]) +[c] n n n n n n (51) [a]n ⋅([b]n ⋅[c]n) = ([a]n ⋅[b]n) ⋅[c]n.

Elemento neutro da adição:

∀[a]_n ∈ ℤ_n

[a]n + [0]n = [a]n

(52)

e [0]_n é a única classe que satisfaz essa sentença.

Inverso aditivo:

∀[a]_n ∈ ℤ_n,∃![b]_n ∈ ℤ_n

[a]n + [b]n = [0]n.

(53)

[b]_n é denotado por −[a]_n.

Elemento neutro do produto:

∀[a]_n ∈ ℤ_n

[a]n ⋅[1]n = [a]n

(54)

e [1]_n é a única classe que satisfaz essa sentença.

Comutatividade:

∀[a]_n,[b]_n ∈ ℤ_n

(55) [a]n + [b]n = [b]n + [a]n (56) [a]n ⋅[b]n = [b]n ⋅[a]n.

Distributiva:

∀[a]_n,[b]_n,[c]_n ∈ ℤ_n

[a] ⋅([b] + [c] ) = [a] ⋅[b] + [a] ⋅[c]. n n n n n n n

(57)

Exercício 43. Mostre que vale

Cancelativa:

∀[a]_n,[b]_n,[c]_n ∈ ℤ_n

[a]n + [b]n = [a]n + [c]n ⇒ [b]n = [c]n

(58)

mas que, em geral,

[a] ⋅[b] = [a] ⋅[c] ⁄⇒ [b] = [c]. n n n n n n

(59)

Definição 20 (divisor de zero). Para n > 1, um elemento não-nulo [a]_n ∈ ℤ_n é um divisor de zero se existe [b]_n ∈ ℤ_n não-nulo tal que [a]_n[b]_n = [0]_n.

Lema 16. [a]_n ∈ ℤ_n não-nulo é divisor de zero se e somente se mdc(a,n)≠1.

Demonstração. Se [a]_n é um divisor do zero então [a]_n[b]_n = [ab]_n = [0]_n para algum [b]_n ∈ ℤ_n não-nulo, ou seja, n |
| ab. Se mdc(a,n) = 1 então n |
| b pelo teorema de Euclides (exerc. 9) e nesse caso [b]_n = [0]_n, contradição.

Se mdc(a,n) = d > 1 então dx = a e dy = n para algum x ∈ ℤ e algum y ∈ ℤ. Assim, ay = dxy = nx portanto [ay]_n = [0]_n e como y < n temos que [y]_n é não-nulo, ou seja, [a]_n é divisor do zero. ♦

Corolário. Se p > 1 é primo então ℤ_p não contém divisores de zero.♦

Lema 17. ℤ_n não contém divisores de zero se e somente se n é primo.

Demonstração. O se é o corolário anterior, vamos provar o somente se. Suponha que ℤ_n não contém divisores do zero. Se n for composto então existe d, divisor próprio de n, tal que n = dp com 1 < d,p < n. Assim [d]_n[p]_n = [0]_n com [d]_n,[p]_n≠[0]_n contrariando o fato de não haver divisores de zero em ℤ_n. ♦

Proposição 18. A propriedade cancelativa do produto vale em ℤ_n se e somente se n é primo.

Demonstração. Se n é primo então ℤ_n não contém divisores do zero o que significa que se [a]_n[c]_n = [b]_n[c]_n e [c]_n≠[0]_n então ([a]_n − [b]_n)[c]_n = [0]_n e assim [a]_n − [b]_n = [0]_n, ou seja, [a]_n = [b]_n.

Agora, se vale a cancelativa então de [a]_n[c]_n = [0]_n e [c]_n não-nulo tiramos que [a]_n[c]_n = [0]_n[c]_n implica [a]_n = [0]_n, ou seja, ℤ_n não tem divisores do zero e pelo resultado anterior n é primo. ♦

Definição 21 (elemento invertível do ℤ_n, inverso). Para n > 1, [a]_n ∈ ℤ_n é invertível se existe [b]_n ∈ ℤ_n tal que [a]_n[b]_n = [1]_n. Nesse caso, [b]_n é chamado inverso de [a]_n

Lema 19. [a]_n ∈ ℤ_n não-nulo é invertível se e somente se mdc(a,n) = 1.

Demonstração. Se mdc(a,n) = 1 então pelo corolário 15 existe b ∈ ℤ tal que ab ≡ 1 (mod n) ou seja [ab]_n = [1]_n portanto [a]_n é invertível.

Se mdc(a,n) = d > 1 então existe [b]_n não-nulo tal que [a]_n[b]_n = [0]_n (lema 16). Assim se [a]_n for invertível, como inverso [c]_n, temos

[b]n = [b]n([a]n[c]n) = ([b]n[a]n)[c]n = [0]n,

(60)

contrariando o fato de [b]_n ser não-nulo. ♦

Corolário. Se p > 1 é primo então todo elemento não-nulo de ℤ_p é invertível.♦

4.2. Invertíveis módulo n.

Definição 22 (sistema completo de invertíveis módulo n). A ⊂ ℤ com mdc(b,n) = 1 para todo b ∈ A é um sistema completo de invertíveis módulo n se para todo a ∈ ℤ tal que mdc(a,n) = 1 existe um b ∈ A tal que a ≡ b (mod n).

Definição 23 (ℤ_n^∗).

∗ ℤn = {[a]n: mdc (a,n) = 1},

(61)

alternativamente, ℤ_n^∗ = {[a]n : a ∈ A } onde A é um sistema completo de invertíveis.

Exercício 44. Prove que se mdc(a,n) = mdc(b,n) = 1 então mdc(ab,n) = 1 e conclua que o produto de duas classes de ℤ_n^∗ é uma classe de ℤ_n^∗.

Exercício 45 (Teorema Chinês do resto, versão 2). Se mdc(m,n) = 1 então a função

f: ℤmn → ℤn × ℤm ( ) [a]mn ↦→ [a]n,[a]m

é uma bijeção e f(ℤ_mn^∗) = ℤ_m^∗× ℤ_n^∗.

Definição 24 (função de Euler).

φ(n) = |ℤ∗n|.

(62)

Usando o exercício 45 podemos concluir que se mdc(m,n) = 1 então φ(mn) = φ(m)φ(n) e, indutivamente, se mdc(n_i,n_j) = 1 para todo i≠j então (exerc. 44) φ(n₁n₂ ⋅⋅⋅ n_k) = φ(n₁)φ(n₂)φ(n_k).

Se p é primo então ℤ_p = {[0]n,[1]n,...[p− 1]n} logo φ(p) = p − 1. Ainda, para potências de primo temos φ(p^k) = p^k−1(p − 1) pois se p^ka então a = qp onde 0 ≤ q < p^k−1, logo há p^k−1 múltiplos de p.

Agora, se n = p₁^m₁ ⋅⋅⋅ p_k^m_k é a fatoração de n então

∏k ∏k ∏k ∏k φ(n) = φ(pmi) = pmi−1(pi − 1) = pmi p−1(pi − 1) i=1 i i=1 i i=1 i i=1 i

ou seja,

( ) ∏k 1- φ(n) = n 1 − pi . i=1

(63)

Exercício 46 (Prova alternativa de (63)). Sejam p_i, 1 ≤ i ≤ k, o primos da fatoração de n e denote por A_i o conjunto dos múltiplos de p_i menores ou iguais a n. Use o princípio de inclusão-exclusão para provar (63).

Teorema (Teorema de Euler). Sejam a,n ∈ ℤ, n > 0 e mdc(a,n) = 1. Então

φ(n) a ≡ 1 (mod n).

(64)

Demonstração. Tome A = {x1,x2,...,xφ(n)} um sistema completo de invertíveis módulo n e forme o conjunto A ⋅ a = {x1a,x2a,...,x a}
φ(n) . Como a é invertível

xia ≡ xja (mod n ) ⇒ xi ≡ xj (mod n ).

Também, temos que x_ia modn ∈ A pois mdc(x_ia,n) = 1 (exerc. 44) logo existe uma permutação π tal que x_ia ≡ x_π(i) (mod n), portanto,

φ(n) x1x2⋅⋅⋅xφ(n)a ≡ xπ(1)xπ(2)⋅⋅⋅xπ(φ(n)) (mod n)

e como mdc(x₁x₂ ⋅⋅⋅ x_φ(n)) = 1 temos a^φ(n) ≡ 1 (mod n). ♦

4.3. Computação com inteiros módulo n.

Operações importantes, principalmente em criptografia de chave pública. Quando se trata de computação com inteiros módulo n assumimos o ℤ_n com os representantes da classes na forma reduzida.

Teorema. Duas classes podem ser somadas e subtraídas em tempo O(log n) e multiplicadas e divididas em tempo O(log ²n).

Somar [a]_n e [b]_n é tomar a soma dos representantes c = a + b e se c ∈{0,1,…,n− 1}, então não há mais nada pra fazer, mas se n ≤ c < 2n então devolver c − n. Caso c = a − b e c ∈{0,1,…,n − 1} então devolver c, senão caso −n < c < 0 então o representante de [c]_n é c + n. Isso pode ser feito em tempo O(log n).

Para computar [a]_n ⋅ [b]_n tomamos c = ab e em seguida c modn. Como o quociente da divisão é menor que n o custo total é O(log n).

Para determinar o inverso multiplicativo de [a]_n executamos o algoritmo estendido de Euclides para o par (a,n) e obtemos d = mdc(a,n) e um inteiro x tal que ax ≡ d (mod n) e |x| < n (justifique); se d = 1 devolva x ou x + n (caso x seja negativo). O tempo total de computação é O(log ²n).

5. Uma hierarquia de estruturas algébricas

No que segue X é um conjunto e ⊕,⊙: X × X → X são duas operações binárias sobre X.

Definição 25 (semigrupo). (X,⊕) é um semigrupo se ⊕ é associativa. (X,⊕) é um semigrupo abeliano se ⊕é associativa e comutativa.

Exemplo 13. (ℤ,+), (ℤ,⋅), (ℤ_n,+), (ℤ_n^∗,⋅), (ℤ_n,⋅) são semigrupos abelianos.

Definição 26 (monóide). Um semigrupo (X,⊕) é um monóide se admite elemento neutro, i.e., existe e ∈ X tal que a⊕e = e⊕a = a para todo a ∈ X. Analogamente ao semigrupo, define-se monóide abeliano.

Exemplo 14. Os semigrupos do exemplo anterior são monóides.

Definição 27 (grupo). Um monóide (X,⊕) é um grupo se todo elemento tem inverso, i.e., para todo a ∈ X existe −a ∈ X tal que a ⊕ (−a) = (−a) ⊕ a = e. Analogamente ao monóide, define-se grupo abeliano.

Exemplo 15. (ℤ,+) é um grupo, (ℤ,⋅) não é um grupo, (ℤ_n,+) é um grupo, (ℤ_n,⋅) não é um grupo, (ℤ_n^∗,⋅) é um grupo.

Definição 28 (anel). (X,⊕,⊙) é um anel se (X,⊕) é um grupo abeliano, (X,⊙) é um semigrupo e vale a distributiva: ∀x,y,z ∈ X

z ⊙ (x ⊕ y) = z ⊙ x⊕ z ⊙ y (x⊕ y)⊙ z = x⊙ z ⊕ y ⊙ z.

anel comutativo se o semigrupo é comutativo (abeliano).

Definição 29 (anel com unidade). (X,⊕,⊙) é um anel com unidade se (X,⊙) tem elemento neutro. No que segue denotamos o elemento neutro de ⊕ por 0 e denotamos o elemento neutro de ⊙ por 1.

Exemplo 16. (ℤ,+,⋅) é um anel comutativo com unidade, (ℤ_n,+,⋅) é um anel comutativo com unidade.

Definição 30 (domínio de integridade). Um anel comutativo (X,⊕,⊙) é um domínio de integridade se não contém divisores do zero, i.e., se ab = 0 então a = 0 ou b = 0.

Definição 31 (anel de divisão). Um anel (X,⊕,⊙) é um anel de divisão se se (X \{0},⊙) é um grupo.

Definição 32 (corpo). Um anel de divisão comutativo é um corpo.

Exercício 47. Determine quais são as estruturas satisfeitas pelo ℤ_m com as operações + e ⋅, para cada m ≥ 2. Prove que (ℤ_p,+,⋅) é um corpo se e só se p > 1 é primo.

6. Polinômios

Seja (K,+,⋅) um corpo.

Definição 33 (polinômio, K[X], grau, mônico). Um polinômio sobre K com indeterminada X é uma expressão formal

∑ f(X ) = aiXi = a0 + a1X + a2X2 + ⋅⋅⋅+ anXn + ... i≥0

(65)

onde a_i ∈ K são os coeficiente de f(X) e existe n ∈ ℤ⁺ tal que a_i = 0 para todo i > n. O conjunto de todos os polinômios sobre K é denotado por K[X]. O grau de f(X) é n = max{i: a_i≠0} e nesse caso escrevemos f(X) = ∑ _i=0ⁿa_iXⁱ.

Note que o grau do polinômio que tem todos os coeficientes nulos, chamado polinômio identicamente nulo sobre K não está definido. Se o polinômio tem grau n e a_n = 1 então ele é dito mônico.

Em K[X] definimos soma e produto de polinômios da seguinte forma. Sejam f(X) = ∑ _i=0ⁿa_iXⁱ e g(X) = ∑ _i=0^mb_iXⁱ dois polinômios

∑n i (66) (f + g)(X ) = (ai + bi)X i=0 n∑+m ∑ k (67) (f ⋅g)(X ) = (aibj)X k=0 i0+≤ji=≤kn 0≤j≤m

Exercício 48. Prove que (K[X],+,⋅) é um domínio de integridade, onde o elemento neutro da soma é o polinômio identicamente nulo, aquele com todos os coeficiente 0, e o elemento neutro da multiplicação é o polinômio constante igual a 1 (a₀ = 1 e a_i = 0 para i > 1).

Observação 9. Não confunda polinômio com função polinomial. Por exemplo, no corpo ℤ_p (p primo) f : ℤ_p → ℤ_p dada por f(x) = x^p − x é nula pelo teorema de Fermat. O polinômio X^p − X não é o polinômio identicamente nulo sobre o ℤ_p, pois dois polinômios são iguais se e somente se têm os mesmos coeficientes. Esse fenômeno, dois polinômios diferentes induzirem a mesma função polinomial não não ocorre em corpos infinitos como, por exemplo, ℚ, ℝ e ℂ.

Teorema (Teorema da divisão para polinômio). Sejam f(X),g(X) ∈ K[X] com g(X)≠0. Então existem únicos q(X),r(X) ∈ K[X] tais que

f(X ) = g(X )⋅q(X) + r(X )

(68)

onde r(X) = 0 ou o grau de r(X) é menor que o grau de g(X).

Demonstração. Se f(X) é nulo então basta tomar q(X) = r(X) = 0. Sejam n e m os graus de f(X) e g(X), respectivamente, e a_i e b_i os coeficientes de f(X) e g(X), respectivamente. Se n < m podemos tomar q(X) = 0 e r(X) = f(X). Então vamos assumir que n ≥ m e provar o teorema por indução em n.

Para n = 0 basta tomar q(X) = a₀b₀⁻¹ e r(X) = 0. Suponha n > 0 e assuma que o teorema da divisão vale para polinômios de grau menor que n.

Tome

−1 n−m f1(X ) = f(X )− g(X)anbm X

(69)

que tem grau menor que n, portanto, pelo hipótese de indução

f (X) = g(X )q (X )+ r (X) 1 1 1

(70)

com r₁(X) nulo ou de grau menor que o grau de g(X). Das duas últimas equações tiramos que

( ) f(X ) = g(X ) q1(X )+ anbm−1Xn −m + r1(X )

(71)

com r₁(X) nulo ou de grau menor que o grau de g(X).

Para mostrar a unicidade suponha que

f(X ) = g(X)q1(X)+ r1(X) = g(X )q2(X )+ r2(X)

com q₁(X)≠q₂(X). Então g(X)(q₁(X) −q₂(X)) = r₁(X) −r₂(X) é uma igualdade entre polinômios de graus diferentes, um absurdo. ♦

Exercício 49 (Teorema da divisão para polinômio num anel). Sejam A um domínio de integridade f(X),g(X) ∈ A[X] com g(X)≠0 e com coeficiente líder invertível em A. Então existem únicos q(X),r(X) ∈ A[X] tais que

f(X ) = g(X )⋅q(X) +r(X )

(72)

onde r(X) = 0 ou o grau de r(X) é menor que o grau de g(X).

Definição 34 (g(X) divide f(X)). Dizemos que g(X) divide f(X) se r(X) = 0 no teorema da divisão.

Definição 35 (raiz de um polinômio). Dizemos que b ∈ K raiz do polinômio f(X) = ∑ _i=0ⁿa_iXⁱ ∈ K[X] se f(b) = ∑ _i=0ⁿa_ibⁱ = 0

Exercício 50. Prove que b ∈ ℤ_p é raiz do polinômio f(X) ∈ K[X] se e somente se X − b divide f(X).

Teorema (Número de raízes de um polinômio). Um polinômio f(X) ∈ K[X] de grau n tem no máximo n raízes.

Demonstração. Para n = 0 os polinômios não têm raiz. Seja f(X) um polinômio de grau n > 0 e suponha que polinômios de grau n−1 têm no máximo n−1 raízes.

Se f(X) não tem raiz então o teorema está provado.

Suponha que a ∈ K é uma raiz de f(X). Então, pelo exercício acima, f(X) = (X −a)q(X) donde tiramos que o grau de q(X) é n− 1. Por hipótese q(X) tem no máximo n − 1 raízes.

Como não há divisores do zero em K[X] (é um domínio de integridade) se f(b) = 0 então b − a = 0 ou q(b) = 0, logo toda raiz de f(X) diferente de a tem que ser raiz de q(X). Portanto, f(X) tem no máximo n raízes. ♦

7. Grupos e subgrupos

Por esta seção estamos assumindo que (X,∘) é um grupo abeliano com |X| finito. A ordem de X é |X|.

Usaremos a notação multiplicativa, ou seja, com o elemento neutro denotado por 1, vamos denotar por a⁻¹ o inverso de a em X com relação a operação do grupo.

Definição 36 (subgrupo, ordem). Dado um grupo (X,∘) um subconjunto de X que é um grupo com o operação de X chamado de subgrupo.

A ordem de um subgrupo, assim como a ordem de um grupo, é o número de elementos no subconjunto.

Exercício 51. Prove que se H ⊂ X é tal que 1 ∈ H e a∘b ∈ H para todos a,b ∈ H então H é subgrupo.

Teorema (Teorema de Lagrange). A ordem de qualquer subgrupo divide a ordem do grupo.

Demonstração. Se H é um subgrupo de X então podemos definir a seguinte relação de equivalência sobre X

a ≡ b (mod H ) ⇔ a ∈ H ∘ b = {h ∘b: h ∈ H} .

(73)

A classe de equivalência de b é denotada por [b]_H = {a ∈ X : a ≡ b (mod H )} .

É fácil notar que |[b]_H|≤|H|, mas vale, de fato, a igualdade entre essas cardinalidades

H → [b]H h ↦→ h∘ b

é uma bijeção. Claramente, a função acima é sobrejetora. Agora, sejam h₁ e h₂ elementos distintos de H. Se h₁ ∘ b = h₂ ∘ b então h₁ ∘ b ∘ b⁻¹ = h₂ ∘ b ∘ b⁻¹, portanto, h₁ = h₂. Assim, a função é injetora.

Portanto [b]_H tem H elementos para qualquer b ∈ X, ou seja, todas as classes de equivalência têm a mesma cardinalidade de H. Como as classes de equivalência particionam X temos que |H| divide |X|. ♦

Se H é subgrupo de X então denotamos por X∕H o conjunto das classes de equivalência modH, definido em (73). Note que a operação [a]_H ∘ [b]_H = [a ∘ b]_H está bem definida e (X∕H,∘) é um grupo.

Observação 10. O grupo no teorema acima não precisa ser abeliano. Na definição acima se X não é abeliano então X∕H não está definido para todo H, somente para os subgrupos normais. Não trataremos disso neste texto.

Exercício 52. Mostre que |X∕H| = |X|∕|H|.

Definição 37 (Homomorfismo de grupos). Sejam (X,∘) e (Y,×) grupos. Uma função f : X → Y é um homomorfismo se para quaisquer a,b ∈ X

f(a∘b) = f (a) ×f (b).

Se, além disso, f é bijetora então f é um isomorfismo.

Exercício 53. Seja n = p₁^m₁p₂^m₂ ⋅⋅⋅ p_k^m_k. Use o teorema chinês dos restos para provar que ℤ_n^∗ é isomorfo a ℤ_p₁^m₁^∗× ℤ_p₂^m₂^∗×× ℤ_{p_k^m_k}^∗.

Teorema (Teorema do homomorfismo). Sejam (X,∘) e (Y,×) grupos com identidades 1_X e 1_Y, respectivamente, e f um homomorfismo. Então

im(f) = é subgrupo de Y ;
ker(f) = é um subgrupo de X;
X∕ker(f) é isomorfo a im(f).

Demonstração. Os itens (1) e (2) ficam como exercício. Vamos mostrar (3). Defina

¯f: X ∕ker(f) → im (f) [a]ker(f) ↦→ f(a).

A função está bem definida pois se [a]_ker(f) = [b]_ker(f) então a ∘ b⁻¹ ∈ ker(f); se f(a ∘ b⁻¹) = 1_Y então f(a) = f(b). Não é difícil verificar que f é homomorfismo.

Note que im(f) = im(f) logo f é sobrejetora. Agora, se [a]_ker(f)≠[b]_ker(f) e f([a]_ker(f)) = f([b]_ker(f)) então f([a]_ker(f) ∘ [b]_ker(f)⁻¹) = 1_Y, ou seja, [a ∘ b⁻¹] ∈ ker(f), logo [a]_ker(f) = [b]_ker(f), uma contradição. Portanto, f é injetiva. ♦

Definição 38. Para a ∈ X e k ∈ ℤ

(| 1, se k = 0, ak = { k−1 |( a∘−ak −1, se k > 0, (a ) , se k < 0.

Definição 39 (⟨a⟩, subgrupo gerado por a).

{ k } ⟨a⟩ = a : k ∈ ℤ

(74)

é um subgrupo, chamado subgrupo gerado por a.

Exercício 54. Prove que a^m ∘ aⁿ = a^m+n e que (a^m)ⁿ = a^mn.

Definição 40 (ordem de a, ord_X(a)). A ordem de a em X, denotada ord_X(a) é a ordem do subgrupo gerado por a.

Note que para a ∈ X a seqüência a⁰,a¹,a²,…,aⁿ,… deve em algum momento repetir elementos, ou seja, existe m ∈ ℤ⁺ tal que a^m = aⁿ para n < m. Para o menor m para o qual isso ocorre deve valer que n = 0, caso contrário a^m−n = 1 e m−n < m contrariando a minimalidade de m. De outra forma

{ k } ⟨a⟩ = a : k ∈ ℤ e 0 ≤ k ≤ ordX (a)− 1 .

Portanto, a ordem de a em X é o menor k ∈ ℤ⁺ tal que a^k = 1.

Exercício 55. Deduza o teorema de Euler (pág. 78) do teorema de Lagrange.

Lema 20. Para todo a ∈ X, a^k = 1 se e somente se ord_X(a) |
| k.

Demonstração. Se k = qord_X(a) então a^k = a^qord_X(a) = (a^ord_X(a))^q = 1.

Por outro lado, se a^k = 1 então tome q,r ∈ ℤ tal que k = ord(a)q + r com 0 ≤ r < ord(a) dados pelo teorema da divisão. Então a^k = a^ord(a)q+r = a^r e como r < ord(a) temos r = 0. ♦

Corolário. a^k = a^ℓ se e só se k ≡ ℓ (mod ord_X(a)).♦

Corolário. Se X tem ordem n então a^k = a^{k modn}, para todo a ∈ X.♦

Exemplo 17. No (ℤ_n,+) — aqui usaremos notação aditiva — se a tem ordem k então k[a]_n = [0]_n, ou seja, ka é um múltiplo de n e pela definição de ordem é o menor múltiplo de a que é múltiplo de n, ou seja ka = mmc(n,a). Portanto, para todo a ∈ ℤ_n

mmc (n,a) n ordℤn(a) = ---------= -------- . a mdc (a,n)

(75)

Pela equação acima, se mdc(a,n) = 1 então ord_{ℤ_n}(a) = n, ou seja, todo b ∈ ℤ_n é da forma ka para algum inteiro positivo k.

Proposição 21. Se a ∈ X tem ordem n então

ord (at) = mmc-(t,n)-= ---n---- X t mdc(t,n)

(76)

Demonstração. Se a^t em ordem k então a^kt = 1 e pelo corolário do lema 20, kt ≡ 0 (mod n) e k é o menor inteiro positivo tal que kt é múltiplo de n, ou seja

mmc (t,n ) n k = ----t----= mdc-(t,n).

(77)

♦

Definição 41 (grupo cíclico, gerador). Dizemos que um grupo X é cíclico se X = ⟨a⟩. Nesse caso dizemos que a é um gerador de X.

Exemplo 18. (ℤ_n,+) é cíclico e 1 é um gerador. Em geral, (ℤ_n^∗,⋅) não é cíclico, e.g., (ℤ₈^∗,⋅) não é cíclico, mas (ℤ₄^∗,⋅) é cíclico6 .

Corolário 22. Se X é cíclico de ordem n então X tem φ(n) geradores.

Demonstração. Seja a um gerador de X. Para todo b ∈ X, existe t ∈ ℤ⁺ tal que a^t = b, portanto, ord_X(b) = n∕mdc(t,n), logo os geradores de X são os a^t ∈ X tais que mdc(t,n) = 1, donde tiramos que há φ(n) geradores. ♦

Exercício 56. Prove que se |X| é primo então X é cíclico, mais que isso, prove também que X = ⟨a⟩ para qualquer a ∈ X.

Exercício 57. Prove que se p > 1 é primo, a^{p^m} = 1 e a^{p^m−1}≠1 então ord_X(a) = p^m.

Exercício 58. Prove que se ord_X(a₁) = n₁ e ord_X(a₂) = n₂ e mdc(n₁,n₂) = 1 então ord_X(a₁ ∘ a₂) = n₁n₂.

7.1. Considerações computacionais a respeito de ordem em ℤ_n e ℤ_n^∗.

De acordo com o exemplo 17 é fácil determinar a ordem de um elemento do (ℤ_n,+), entretanto, esse não é o caso do (ℤ_n^∗,⋅). O algoritmo trivial toma a ∈ ℤ_n^∗ e calcula todas as potências a^k, o que é inviável se |ℤ_n^∗|é grande, o que é o caso em criptografia.

Mesmo a ordem de ℤ_n^∗ é difícil de computar quando n não é primo, ou seja, não é conhecido algoritmo eficiente para o seguinte._______________________________

    Dado inteiro $n > 1$
    Devolve $φ(n)$ .

_____________________________________________________________________

Figura 9: Problema da ordem do ℤ_n^∗.

Observação 11. Se uma fatoração de n é conhecida então podemos computar φ(n) em tempo polinomial usando (63) (pág. 77). Por outro lado, é sabido que dado n e φ(n) podemos computar em tempo polinomial uma fatoração de n, o que parece indicar que φ(n) é tão difícil computacionalmente quanto fatoração.

Exercício 59. Suponha que existe um algoritmo que dados inteiros n > 1 e a ∈ ℤ_n^∗ devolve ord_{ℤ_n^∗}(a) em tempo polinomial em log n. Mostre como usar esse algoritmo para para computar em tempo polinomial uma fatoração de n.

O seguinte resultado mostra como calcular a ordem de um elemento de ℤ_p^∗ quando é conhecida a fatoração de p − 1.

Lema 23. Seja a ∈ X e m = p₁^m₁p₂^m₂ ⋅⋅⋅ p_k^m_k positivo tal que a^m = 1. Então

∏k ordX(a) = pmii−fi, i=1

(78)

onde f_i é o maior inteiro não-negativo tal que a^{m∕p_i^f_i} = 1, para todo i ∈{1,2,…,k}.

Demonstração. Seja k = ord_X(a). Pelo lema 20 temos k |
| m portanto k = p₁^r₁p₂^r₂ ⋅⋅⋅ p_k^r_k com 0 ≤ r_i ≤ m_i para todo i.

Para determinar r₁ tome a seqüência

am ∕pm11,am∕pm11−1,am∕pm11−2, ...,am∕p1,am

e seja f₁ o maior inteiro não-negativo tal que a^{m∕p₁^f₁} = 1 (a primeira ocorrência de 1). Então temos

f f+1 am∕p11 = 1 e am∕p11 ⁄= 1 ou f1 = m1.

De a^{m∕p₁^f₁} = 1 temos que k divide m∕p₁^f₁, ou seja,

|m1− f1 m m k|p1 p2 2⋅⋅⋅pk k

mas de a^{m∕p₁^f₁+1}≠1 temos que k não divide m∕p₁^f₁+1, ou seja

k ⁄ ||pm11 −f1−1pm22 ⋅⋅⋅pmkk ,

isso só pode ocorrer se r₁ = m₁ − f₁. Analogamente, r_i = m_i − f_i para todo i ∈ {2,...,k} . ♦

Corolário 24. Dado n ∈ ℤ⁺, se aⁿ = 1 e a^n∕p≠1 para todo p primo e divisor de n, então a tem ordem n.♦

Demonstração. Basta notar que (a^{n∕p^m})^p = a^{n∕p^m−1} logo a^{n∕p^m}≠1, para todo inteiro m > 1. ♦

Quando usamos um grupo cíclico em criptografia, freqüentemente precisamos conhecer o gerador desse grupo. Note que no corolário acima a recíproca vale. Logo temos o seguinte resultado.

Teorema. Se X é cíclico de ordem n = p₁^m₁p₂^m₂ ⋅⋅⋅ p_k^m_k então a é um gerador de X se e somente se a^n∕p_i≠1 para todo i ∈ {1,2,...,k} .

Como o número de fatores k é no máximo log ₂n, testar se a é gerador pode ser feito de modo eficiente. Na próxima seção veremos como determinar os geradores do ℤ_p^∗.

Exercício 60. Dados inteiros m₁,m₂,…,m_k > 1, sejam m = m₁m₂ ⋅⋅⋅ m_k e m_i′ = m∕m_i. Para a ∈ ℤ_n, mostre como computar a^m₁′,a^m₂′,…a^m_k′ com O(log(k)log(m)) multiplicações.

8. Raízes primitivas

Agora veremos como determinar um gerador do ℤ_p^∗ para p primo. Primeiro vamos provar que esse grupo é cíclico.

Teorema. Se p > 1 é primo então (ℤ_p^∗,⋅) é cíclico.

Demonstração. Tome a fatoração

∏k p− 1 = pmii. i=1

(79)

O polinômio X^{(p−1)∕p_i} − [1]_p ∈ ℤ_p[X] tem no máximo (p − 1)∕p_i < p − 1 raízes, portanto, existe [a_i]_p ∈ ℤ_p^∗ tal que

(p−1)∕p [ai]p i⁄= [1]p.

(80)

Fazemos

(p−1)∕pmii qi = ai

e notamos que

pmi pmi−1 qii ≡ api−1 ≡ 1 (mod p) e qii ≡ a(ip−1)∕pi⁄≡ 1 (mod p).

(81)

Pelo exercício 57 ord_{ℤ_p^∗}([q_i]_p) = p_i^m_i.

Usando uma generalização do exercício 58 temos ord_{ℤ_p^∗}([q₁q₂ ⋅⋅⋅ q_k]_p) = p − 1, portanto, é um gerador do grupo. ♦

Exercício 61. Seja n > 1. Prove que se para cada fator primo p de n − 1 existe um inteiro a tal que [a]_nⁿ⁻¹ = [1]_n e [a]_n^(n−1)∕p≠[1]_n, então n é primo.

Definição 42 (raiz primitiva módulo p). Seja p > 1 primo. Uma raiz primitiva módulo p é um gerador de ℤ_p^∗.

Portanto, ℤ_p^∗ admite raiz primitiva para qualquer p > 1 primo.

Observação 12. Os elementos de ℤ_p são as raízes da equação X^p−1 − [1]_p = [0]_p (teo. de Fermat), portanto, podemos determinar todas as raízes a partir de um gerador, ou raiz primitiva.

Exemplo 19. O ℤ₁₁^∗ é um grupo de ordem 10 = 2 ⋅ 5. Para simplificar, vamos escrever ℤ₁₁ = {1,2,...,10} . Assim, a é um gerador se a² ⁄≡ 1 (mod 11) e a⁵ ⁄≡ 1 (mod 11)


a	1	2	3	4	5	6	7	8	9	10


a² mod11	1	4	9	5	3	3	5	9	4	1

a⁵ mod11	1	10	1	1	1	10	10	10	1	10

Logo, os geradores são 2,6,7,8. Se escolhemos um elemento aleatoriamente com probabilidade 1∕10 e repetimos a escolha de modo independente, o número esperado de rodadas até sair um gerador do ℤ₁₁^∗ é 10∕4. Se usarmos o fato de que 1 e −1 não são geradores podemos melhorar a expectativa para 8∕4 = 2. Essa é a idéia do algoritmo a seguir.

Como já dissemos, freqüentemente precisamos conhecer o gerador desse grupo._

    Dado inteiro $p > 1$ primo
    Devolve uma raiz primitiva módulo $p$ .

_____________________________________________________________________

Figura 10: Problema da Raiz Primitiva mod p.

Não se conhece algoritmo eficiente para determinar um gerador de ℤ_p^∗ a menos que seja dado a fatoração de p − 1.

Seguindo a demonstração do teorema anterior precisamos, de fato, de um modo eficiente de achar a_i tal que vale (80), para cada fator p_i de p − 1 (79).

A imagem do homomorfismo f : ℤ_p^∗→ ℤ_p^∗ definido por f(x) = x^{(p−1)∕p_i} é um subgrupo de ℤ_p^∗ de ordem p_i.

Sejam g uma raiz primitiva, x = g^k e y = g^ℓ, y≠x. Então f(x) = f(y) se e só se k(p − 1)∕p_i ≡ ℓ(p − 1)∕p_i (mod p − 1), se e somente se k ≡ ℓ (mod p_i). Portanto, a pré-imagem f⁻¹(x), para qualquer x, tem cardinalidade p_i^m_i−1 ∏_j≠ip_j^m_j = (p− 1)∕p_i. Assim, |f(ℤ_p^∗)| = p_i e se escolhemos x ∈ ℤ_p^∗ com probabilidade uniforme então a probabilidade de f(x) = 1 é 1∕p_i.

_____________________________________________________________________

    Dado inteiros positivos $p1,m1,p2,m2,...,pk,mk$
    Devolve gerador de $ℤ ∗$, $p = 1+ ∏k pmi p i=1 i$ .

    1   para $i$ de $1$ até $k$
    2      repita
    3          escolha $a ∈ ℤ∗ p$ aleatoriamente;
    4           $(p− 1)∕pi b ← a mod p$ ;
    5      até que $b ⁄= 1$ ;
    6    $(p−1)∕pmi qi ← a i mod p$ ;
    7   devolva( $∏k q ← i=1 qi mod p$ ).

_____________________________________________________________________

Figura 11: Raiz primitiva de ℤ_p^∗.

Para provar que o algoritmo funciona basta notar que no final da i-ésima iteração da linha 1 q_i^{p_i^m_i} ≡ 1 (mod p) e q_i^{p_i^m_i−1} ⁄≡ 1 (mod p).

O tempo do algoritmo depende do número de rodadas da linha 2. Se a é escolhido uniformemente no passo 3 então b está distribuído uniformemente num subgrupo de ℤ_p^∗ de ordem p_i temos, como vimos acima que b = 1 com probabilidade 1∕p_i, logo, se X_i é o número de rodadas do repita para i fixo, então X_i é uma variável aleatória com distribuição geométrica com probabilidade de sucesso 1 − 1∕p_i, portanto, o valor esperado de X_i é 1∕(1 − 1∕p_i) ≤ 2. No total, o número esperado de rodadas X = ∑ _i=1^kX_i ≤ 2k.

As exponenciações nas linhas 4 e 6 podem ser feita em tempo O(log ³p) (exerc. 28), assim como o produto na linha 8. Portanto o tempo esperado é O(k log ³p) = O(log ⁴p).

Exercício 62. Dê uma prova detalhada para o seguinte argumento usado acima: f(x) = f(y) se e só se k(p−1)∕p_i ≡ ℓ(p−1)∕p_i (mod p−1), se e somente se k ≡ ℓ (mod p_i).

Exercício 63. Dê uma prova detalhada para: a pré-imagem por f de qualquer elemento tem cardinalidade p_i^m_i−1 ∏_j≠ip_j^m_j.

Exercício 64. Dê uma prova detalhada para o seguinte argumento usado acima: Assim, |f(ℤ_p^∗)| = p_i e se escolhemos x ∈ ℤ_p^∗ com probabilidade uniforme então a probabilidade de f(x) = 1 é 1∕p_i.

O seguinte algoritmo probabilístico para construir um gerador do ℤ_p^∗ é assintoticamente mais eficiente que o algoritmo 11 acima.

Exercício 65 (Algoritmo para determinar gerador). Suponha que são dados inteiros positivos p₁,m₁,p₂,m₂,…,p_k,m_k como acima.

Dado a ∈ ℤ_p^∗ mostre como computar a ordem de a em tempo O(k log ³p) (dica: lema 23).
Use o exercício 60 para melhorar o tempo para O(log k log ³p).
Modifique o algoritmo do item anterior para construir um gerador do ℤ_p^∗ em tempo esperado O(log k log ³p).

Exercício 66. Decida se o seguinte algoritmo funciona corretamente

__________________________________________________________________

    Dados inteiros positivos $p ,m ,p ,m ,...,p ,m 1 1 2 2 k k$
    Devolve gerador de $∗ ℤ p$ , $∏k mi p = 1+ i=1pi$ ,

    1   repita
    2      escolha $∗ a ∈ ℤp$ aleatoriamente;
    3       $i ← 1$ ;
    4      enquanto $(p− 1)∕pi (a ⁄≡ 1 (mod )p e i ≤ k)$ faça
    5                      $i ← i+ 1$ ;
    6   até que $i = k + 1$ ;
    7   devolva( $a$ ).

_____________________________________________________________________

Figura 12: Raiz primitiva de ℤ_p^∗.

Exercício 67. Deduza que φ(n) = Ω(n∕log n) de (63), pág. 77, e de que há ≤ log ₂n fatores na fatoração de n.

Exercício 68. Use o exercício anterior para deduzir a complexidade esperada (média) do algoritmo 12.

Observação 13. A necessidade de se ter uma fatoração não inviabiliza totalmente o algoritmo 11 acima porque o que se faz na prática é gerar um número “fatorado” n e testar a primalidade de n+1. Ou, ainda, podemos escolher um primo da forma 2q + 1 para q primo, portanto os fatores de p − 1 são 2 e q.

9. Logaritmo discreto

Seja X um grupo cíclico de ordem n e a ∈ X um gerador. Queremos computar a inversa da função exp_a: ℤ → X definida por exp_a(k) = a^k.

Definição 43 (logaritmo discreto). Se a gera um grupo de ordem n, então para todo b ∈⟨a⟩ existe k ∈{0,1,…,n − 1} tal que a^k = b.

Dizemos que k é o logaritmo discreto em X de b na base a.

Notação 44. k = dlog_a(b).

O problema computacional do logaritmo discreto em X pode ser formulado da seguinte maneira

_____________________________________________________________________

    Dado $a ∈ X$ de ordem $n$ e $b ∈ X$
    Devolve $min{k ∈ ℤ+ : b = ak}$ .

_____________________________________________________________________

Figura 13: Problema do Logaritmo Discreto.

A dificuldade do problema nessa formulação depende da representação de X. Se a representação é aditiva como (ℤ_n,+) o problema do logaritmo discreto em X é resolver ak ≡ b (mod n) que é fácil, se a representação é multiplicativa como (ℤ_n^∗,⋅) (cíclico) então o problema é difícil, não se conhece algoritmo eficiente para o seguinte problema.

No caso dos resíduos de inteiros, o logaritmo discreto é um isomorfismo, ou seja, (ℤ_p^∗,⋅) é isomorfo ao grupo aditivo (ℤ_φ(p),+).

Exemplo 20. Omitindo os colchetes [ ] para simplificar, a função dlog₂: ℤ₁₁^∗→ ℤ₁₀ dada por

(ℤ₁₁^∗,⋅)	(ℤ₁₀,+)

1	0
2	1
3	8
4	2
5	4
6	9
7	7
8	3
9	6
10	5

satisfaz dlog₂(a⋅b) = dlog₂(a) + dlog₂(b), onde a soma e o produto operam nos respectivos grupos. O caso geral é tratado no exercício a seguir.

Exercício 69. Seja a uma raiz primitiva módulo p. Verifique que a função dlog_a: ℤ_p^∗→ ℤ_p−1 dada por [a]_p^k[k]_p−1 é um isomorfismo.

Exercício 70 (Mudança de base). Prove que se a,b são geradores então dlog_b(c) = dlog_a(c)∕dlog_a(b).

Exemplo 21. Para p = 1990 é sabido que 3 é uma raiz primitiva. Assim,

ℤ∗= {3k modp : 0 ≤ k ≤ p − 2}. p

Sabemos computar rapidamente 3⁷⁸⁹ modp, usando o algoritmo 7, entretanto, não sabemos resolver eficientemente a equação 3^x ≡ 1452 (mod 1999).

Observação 14. Em aplicações criptográficas X = ℤ_p^∗ para p ≥ 2¹⁰²⁴ o que torna uma busca exaustiva por dlog_a(b) de complexidade exponencial.

Exemplo 22 (Troca de chaves—protocolo Diffie–Hellman–Merkle). 7 cíclico X de ordem n e um gerador g de X, de conhecimento público, Alice e Bob estabelecem um chave comum da seguinte forma

Alice sorteia a ∈, computa A = g^a e manda-o para Bob;
Bob sorteia b ∈, computa B = g^b e manda-o para Alice;
Alice computa B^a e Bob computa A^b e a chave secreta comum entre eles é k = A^b = B^a.

Se um espião, conhecendo g e X, intercepta A e B então o problema é determinar a tal que g^a = A, determinar b tal que g^b = B, e com isso feito (que é a parte difícil se for feita uma escolha apropriada de X) computar k = g^ab.

Um parte importante para a segurança do protocolo é a escolha de X, g e n. Comentamos acima que não é para todo X que o problema do logaritmo discreto é difícil. Usualmente X = ℤ_n^∗ e para segurança, n deve ser primo ou ter um ter um fator primo grande (se os fatores forem pequenos o algoritmo Pohlig–Hellman determina a e b eficientemente). Padrões atuais (ansi x9.42) definem os seguinte domínios para os parâmetros envolvidos, considerando X = ℤ_p^∗

primo usado como módulo nas operações, com 2^L−1 < p < 2^L, onde L ≥ 1024 e L é um múltiplo de 256.
fator primo de p − 1 tal que p = jq + 1 e q > 2^m−1. ℤ_p^∗ tem um subgrupo cíclico de ordem q.
Um gerador do subgrupo de ℤ_p^∗ de ordem q.

Um problema nesse protocolo é que o interceptador pode assumir o papel de Alice para Bob e o de Bob para Alice e assim conhecer a chave para decodificar alguma mensagem. Isso pode ser evitado usando-se assinaturas digitais, que veremos adiante.

Observação 15. A capacidade de computar logaritmo discreto eficientemente implica na violação do protocolo de Diffie–Hellman–Merkle, não se sabe se a recíproca vale.

Criptografia

10. Sistemas criptográficos

Um sistema de codificação é uma quina (,,,,) de conjuntos onde

é o espaço dos textos comuns (plaintext);
é o espaço dos textos cifrados (chipertext);
é o espaço das chaves;
é o espaço das funções de codificação E_k: →, onde k ∈;
é o espaço das funções de decodificação D_k: →, onde k ∈;

tais que para cada e ∈ existe d ∈ tal que D_d(E_e(p)) = p.

Exemplo 23 (Cifra de César). Essa cifra identifica o alfabeto com o ℤ₂₆, = ℤ₂₆ e , = {a,b,...,z} . Para e,d ∈ ℤ₂₆ temos as funções

Ee(x) = (x+ e) mod26 e Dd(x) = (x − d) mod26.

Agora, estenda o sistema para que os textos sejam seqüências de de letras do alfabeto. Por exemplo, para a chave e = d = 3

Normal: abcdefghijklmnopqrstuvwxyz
Cifrado: defghijklmnopqrstuvwxyzabc

Normal: A ligeira raposa marrom saltou sobre o cachorro cansado
Cifrado: d oljhlud udsrvd pduurp vdowrx vreuh r fdfkruur fdqvdgr

Exemplo 24 (Cifra de Vigenère). A cifra de Vigenère (1523-1596) é um método de encriptação baseado em trabalhos dos matemáticos italianos Leon Alberti (1404), Giovanni Porta (1525) e do alemão Johannes Tritemius (1492). Funciona como as cifras de César, entretanto, a cifra de uma letra depende da posição dela no texto.

Informalmente, a cifragem ocorre do seguinte modo. Escolhemos uma palavra chave, por exemplo ENGLISH e escrevemos essa palavra repetidamente até que a string obtida tenha o mesmo número de letras que o texto que será codificado, por exemplo ENGLISHISALLGREEKTOGERMANS. Usamos uma tabela 26 × 26 com as linhas e colunas indexadas pelo alfabeto, a primeira linha é composta pelo alfabeto na seqüência usual, a segunda é a seqüências deslocada ciclicamente uma posição para esquerda, a terceira duas posições, e assim por diante. A i-ésima letra da cifra é obtida na posição (l,c) da tabela, onde l é a linha que corresponde a i-ésima letra da chave e c é a coluna que corresponde a i-ésima letra do texto. No nosso exemplo

chave ENGLISHENGLISHENGLISHENGLI
texto FINNISHISALLGREEKTOGERMANS
cifra JVTYQKOMFGWTYYIRQEWYLVZGYA

baseado na tabela de Vigenère:

Essa cifragem é poderosa quando usada com uma língua pouco conhecida como o Quechua8 . Durante a Segunda Grande Guerra Mundial o americanos usaram-no com a língua do povo Navajo com sucesso, os japoneses nunca conseguiram quebrar esse código.

Friedrich Kasiski foi o primeiro a publicar, em 1863, um ataque com sucesso sobre a cifra de Vigenère, mas Charles Babbage já havia desenvolvido o mesmo método um pouco antes, em 1854.

A força dessa cifra reside no fato de impedir uma análise baseada na freqüência das ocorrências dos caracteres, entretanto, a repetição da chave a torna vulnerável caso o comprimento dela seja descoberto.

Os sistemas têm duas grandes classes, os simétricos e os assimétricos ou de chave pública.

Criptossistemas simétricos tem as chaves de codificação e decodificação trivialmente relacionadas (ou, d(e) pode ser facilmente computável), freqüentemente iguais, e supõem-se secretas.
Criptossistemas assimétricos tem as chaves de codificação e decodificação diferentes, a chave e pode ser feita pública mas d(e) é secreta e não pode ser computada eficientemente.

Definições usuais

alfabeto:: denotado por Σ, é o conjunto de símbolos elementares que compõem os textos;
palavra:: ou string é uma seqüência finita de símbolos do alfabeto;
tamanho:: ou comprimento de uma palavra é o número de símbolos do alfabeto que a compõem.
Σⁿ:: conjunto das palavras de tamanho n;
Σ^∗:: conjunto das palavras de tamanho n, para todo n ∈ ℤ⁺. λ é a palavra vazia e tem comprimento 0.

10.0.1. Cifras afim. As cifras de César e Vigenère são exemplos de cifras afim.

Nesses sistemas = = Σ = ℤ_m. Cada chave é um par (a,b) ∈ ℤ_m × ℤ_m tal que mdc(a,m) = 1 (a é inversível módulo m). As funções de codificação e decodificação são

(82) E(a,b)(x) = ax + b modm (83) D (a′,b)(x) = a′(x− b) modm

e a chave decodificadora que corresponde a (a,b) é (a⁻¹ modm,b).

Exemplo 25. Considere o alfabeto usual com 26 letras identificado com o ℤ₂₆ com a chave (a,b) = (7,3).

b	a	l	d	e
1	0	11	3	4
10	3	2	24	5
k	d	c	y	f

e a decodificação pode ser lida na tabela de baixo pra cima.

Essa codificação pode ser quebrada se se conhece a correspondência entre dois pares de letras, por exemplo b → k e d → y corresponde a 1a + b ≡ 10 (mod 26) e 3a + b ≡ 24 (mod 26), respectivamente. Isolando b na primeira equivalência e substituindo na segunda temos 2a + 10 ≡ 24 (mod 26), ou seja, a + 5 ≡ 12 (mod 13), portanto a = 7 e b = 3.

Uma generalização n-dimensional do caso anterior: as funções sobre = = ℤ_mⁿ são da forma ℤ_mⁿ → ℤ_mⁿ

⃗ (84) E(A,⃗b)(⃗x) = A ⃗x+ b modm (85) D(A′,⃗b)(⃗x) = A ′(⃗x − ⃗b) modm

onde A e A′ são matrizes e

vetores de dimensão n. A cifragem é feita sobre blocos de tamanho n.

A chave decodificadora que corresponde a (A,b) é (det(A)⁻¹ modm,b).

Essa cifras são quebradas se o atacante conhece n + 1 pares (P,C) ∈×. Suponha que um atacante conheça

(⃗pi,A ⃗pi +b modm ), 0 ≤ i ≤ n.

Então, para

_i = A

_i + b

( ) A ⃗p1 − ⃗p0,⃗p2 − ⃗p0,...,⃗pn − ⃗p0 ≡ (⃗c1 − ⃗c0,...,⃗cn − ⃗c0) (mod m)

e se det(P)=det ₁ − ₀, ₂ − ₀,…, _n − ₀é invertível então A ≡ CP⁻¹ modm e ⃗
b = ₀ − A ₀.

10.1. One-time pad.

Gilbert Sandford Vernam era um engenheiro da AT&T Bell Labs em 1917 quando inventou e patenteou o seguinte sistema de crifagem (cifra de Vernam): dada uma chave k, escolhida previamente e armazenada numa fita de papel perfurado9 ,

Ek(x) = xxork e Dk (y) = yxork.

(86)

O fato da chave ser re-usada tornava o sistema inseguro. Pouco tempo depois Joseph Mauborgne, na época capitão do exército americano, propôs que a informação contida na fita fosse aleatória e usada uma única vez (one-time pad). Claude Shannon10 , na época da 2^a Grande Guerra, provou que o one-time pad é inquebrável.

Definição 45 (cifra de Vernam, one-time pad). A cifra de Vernam é o criptossistema com = = ={0,1}ⁿ com as funções de codificação e decodificação dadas em (86). Se as chaves são strings aleatórias escolhidas uniformemente em e usadas uma única vez então o sistema é chamado one-time pad.

Observação 16. 11 Uma versão desse sistema é usado no RC4, um algoritmo muito usado em protocolos conhecidos, como Secure Socket Layers (SSL) (para proteger o tráfego Internet) e WEP (para a segurança de redes sem fios). Em algumas aplicações podem converter-se em sistemas inseguros, porém, alguns sistemas baseados em RC4 são seguros o bastante num contexto prático.

10.1.1. Sigilo Perfeito. Fixamos um sistema com ,, finitos e uma distribuição de probabilidade Pr: → [0,1] tal que Pr(P) > 0 (∀P ∈). A idéia de sigilo perfeito é a seguinte: escolhemos um texto de acordo com a distribuição Pr e o ciframos. Entregamos ao adversário o texto cifrado C e perguntamos qual a probabilidade do texto que foi cifrado? Se o adversário não pode fazer melhor do que responder Pr(P), ou seja, o conhecimento de C não torna uns textos mais prováveis e outros menos prováveis do que eles são, significa que ele não ganhou informação com o conhecimento de C e temos segredo perfeito.

Formalmente, defina o espaço amostral × onde a distribuição Pr é determinada por uma escolha P e uma escolha de K feitas independentemente, e defina as variáveis aleatórias

k: K × P → K (K,P ) ↦→ K P: K × P → P (K,P ) ↦→ K C: K × P → {0,1}∗ (K,P ) ↦→ EK (P )

(87)

Definição 46 (sigilo perfeito). Um criptossistema simétrico nas condições acima tem sigilo perfeito se para quaisquer P ∈ e todo possível C ∈

Pr(P = P|C = C ) = PrP (P )

(88)

para toda distribuição Pr.

Exemplo 26. Tome = {0,1}, = {a,b} e = {A,B} com


P	0	1

Pr(P)	1∕4	3∕4


K	A	B

Pr(K)	1∕4	3∕4


K	A	B

E_K(0)	a	b

E_K(1)	b	a

resulta em


C	a	b

Pr(C)	5∕8	3∕8


(P\|C)	(0\|a)	(1\|a)	(0\|b)	(1\|b)

Pr(P\|C)	1/10	9/10	1/2	1/2

não tem, sigilo perfeito pois se o adversário recebe C = a então ele tem quase certeza de que o texto cifrado foi a.

Exemplo 27. One-time pad com = = ={0,1}². A seguinte tabela tem entradas Pr(C = C|P = P); fixado P as possíveis cifras são PxorK onde K varia sobre toda chave possível, portanto, independente de P as cifras são equiprováveis.

		C	00	01	10	11
Pr(P)	P

1∕6	00		1/4	1/4	1/4	1/4
1∕3	01		1/4	1/4	1/4	1/4
1∕4	10		1/4	1/4	1/4	1/4
1∕4	11		1/4	1/4	1/4	1/4

A tabela abaixo mostra Pr(P = P|C = C), a probabilidade do texto ser P dado que o adversário viu C

		C	00	01	10	11
Pr(P)	P

1∕6	00		1∕6	1∕6	1∕6	1∕6
1∕3	01		1∕3	1∕3	1∕3	1∕3
1∕4	10		1∕4	1∕4	1∕4	1∕4
1∕4	11		1∕4	1∕4	1∕4	1∕4

Nesse exemplo temos sigilo perfeito pra essa distribuição particular.

Lema 25. Para o one-time pad da definição 45

Pr(C = C|P = P ) =-1 2n

para qualquer P ∈

e qualquer C ∈ {0,1}ⁿ e para qualquer distribuição de probabilidade sobre

Demonstração. Fixado P, temos C = PxorK se e só se K = PxorC. Como K é escolhida uniformemente a probabilidade é (1∕2)ⁿ. ♦

Teorema. O one-time pad tem sigilo perfeito.

Demonstração. Usando o teorema de Bayes

Pr(P = P|C = C ) = Pr(C =-C-|P-=-P)Pr(P-=-P)= 2−nPr(P =-P-) Pr(C = C ) Pr(C = C) 2−nPrP (P = P) = --Pr(C-=-C)---

e no numerador temos

Pr(C = C) = ∑ Pr(C = C |P = X )Pr(P = X ) = ∑ 2−nPr(P = X ) X ∈P X∈P −n ∑ −n = 2 PrP(P = X ) = 2 . X∈P

Disso segue o teorema. ♦

Observação 17. O one-time pad não é o único sistema que possui sigilo perfeito, mas é o mais simples. Foi o primeiro a ser descoberto.

Exercício 71 (Teorema de Shannon). Dados um sistema com ,, finitos e uma distribuição de probabilidade Pr: → [0,1] tal que Pr(P) > 0 (∀P ∈), esse sistema tem sigilo perfeito se e somente se as chaves têm distribuição uniforme e se para todo P ∈ e todo C ∈ existe um único K ∈ tal que E_K(P) = C.

Exercício 72. Prove que não existe sistema de codificação com sigilo perfeito se os textos de n bits usam chaves de n − 1 bits.

Observação 18 (Curiosidades12 ). Enquanto one-time pads são seguras se gerado e usado corretamente, pequenos erros puderam viabilizar criptoanálises bem sucedidas:

Em 1944-1945, a agência da segurança do exército americano quebrou um sistema one-time pad usado pelo ministério do exterior alemão para seu tráfego de alto-nível, codinome GEE (Erskine, 2001). GEE era insegura porque as chaves não eram completamente aleatórias - a máquina usada gerar as chaves produziu saídas previsíveis.
Em 1945 os Estados Unidos descobriram que as mensagens Camberra-Moscou estavam cifradas com one-time pad. Entretanto a one-time pad usada era a mesma usada por Moscou para mensagens de Washington-Moscou. Combinado com o fato de que algumas das mensagens de Camberra-Moscou incluíram documentos britânicos conhecidos pelo governo, isto permitiu que algumas das mensagens cifradas fossem quebradas.
As one-time pads foram empregadas por agências do espionagem Soviéticas para comunicações secretas com os agentes e os controladores dos agentes. A análise mostrou que as chaves foram geradas pelos datilógrafos que usavam máquinas de escrever reais. Este método é, naturalmente, não verdadeiramente aleatório, porque faz determinadas seqüências de chaves mais prováveis do que outras, contudo provou ser geralmente eficaz. Sem cópias do material chave usado, somente alguma falha no método da geração ou re-utilização das chaves ofereceram esperança para as criptoanálises. No fim dos anos 40, as agências de inteligência dos Estados Unidos e do Reino Unido podiam quebrar alguns one-time pad soviéticos durante a 2^a Grande Guerra em conseqüência dos erros feitos na geração e na distribuição de chaves. Uma desconfiança é que o pessoal do Centro de Moscou esteve apressado pela presença das tropas alemãs, as quais estavam do lado de fora de Moscou no fim de 1941 e no inicio de 1942, e produziu mais de uma cópia do mesmo material chave durante esse período. Este esforço que durou uma década foi apelidado de VENONA13 (BRIDE era o nome anterior); produziu uma quantidade considerável de informação, incluindo informação sobre espiões soviéticos. Mesmo assim, somente uma porcentagem pequena das mensagens interceptadas foi decifrada inteiramente ou parcialmente.

No que segue identificamos do ℤ_n com {0,1,...,n− 1}

, para todo n.

11. RSA

É um criptossistema assimétrico; deve o seu nome a três professores do MIT: Ron Rivest, Adi Shamir e Len Adleman14 , que o publicaram em 197815 .

Tome = = ℤ_n onde n é o produto de dois primos n = p⋅q. Uma chave pública é um par (e,n), onde e ∈ ℤ_φ(n)^∗\{1}. As funções de codificação são

Ee (P ) = P e modn.

(89)

A chave de decodificação correspondente é d = d(e) = e⁻¹ modφ(n). Essa é a chave privada e deve ser mantida em segredo.

As funções de decodificação são

d Dd (P ) = P modn.

(90)

Essas funções são computadas eficientemente pelo algoritmo 7.

Proposição 26. Se P ∈ ℤ_n então D_d(e)E_e(P) = P.

Demonstração. Se d = d(e) então D_dE_e(P) = P^ed modn com ed = 1 + rφ(n) para algum r ∈ ℤ. Logo P^ed = P^1+rφ(n) = PP^p−1^(q−1)r, mas se p ⁄ |
| P então

( )(q− 1)r P Pp−1 ≡ P (mod p)

(91)

pois P^p−1 ≡ 1 (mod p) pelo teorema de Fermat (pág. 44). Também, P^ed ≡ P (mod p) se pP, ou seja,

ed P ≡ P (mod p).

(92)

Analogamente, vale

Ped ≡ P (mod q).

(93)

De (92) e (93) temos que pqP^ed − P, ou seja, P^ed ≡ P (mod n), assim

D (E (P )) ≡ Ped ≡ P (mod n). d e

(94)

Como P < n, temos P^ed modn = P. ♦

Observação 19. A chave privada d = d(e) é computada eficientemente a partir de e e φ(n) pelo algoritmo de Euclides estendido (algoritmo 8).

Exemplo 28. Tome os primos p = 61 e q = 53, portanto n = pq = 3233. A função de Euler é φ(n) = (p−1)(q−1) = 3120. Escolhemos e = 17 e obtemos d = 2753. A chave pública é 17. Se o texto comum é m então o texto cifrado é c = m¹⁷ mod3233. A chave privada é 2753. O texto decifrado é dada por m = c²⁷⁵³ mod3233.

Por exemplo, para codificar m = 123, calculamos c = 123¹⁷ mod3233 = 855 usando o algoritmo 7. Para decodificar c = 855, calculamos com o algoritmo 7, m = 855²⁷⁵³ mod3233 = 123.

Observação 20. Se P > n então uma alternativa para usar o RSA é fazer o seguinte. Usamos Σ = ℤ_N de modo que teremos blocos em Σ^k, onde k = ⌊logN n⌋ . Assim a palavra m₁m₂…m_k pode ser vista como um número

k P = ∑ m Ni−1 i=1 i

na base N e

∑k ∑k 0 ≤ P ≤ (N − 1)Ni−1 = (N − 1) N i−1 = (N − 1)(N k−1 − 1) < n. i=1 i=1

A segurança do RSA é baseada na dificuldade computacional do Problema RSA:

_____________________________________________________________________

Dado uma chave pública $(e,n)$ e um inteiro $c$
Devolve um inteiro $p$ tal que $pe = c mod n$ .

_____________________________________________________________________

Figura 14: Problema RSA.

Acredita-se que esse problema seja equivalente ao problema da fatoração.

Conjectura 27 (Rivest, Shamir e Adleman). Um algoritmo eficiente para o problema RSA implica num algoritmo eficiente para o problema da Fatoração.

Se φ(n) puder ser determinado eficientemente a partir de n e e então a fatoração de n pode ser computada eficientemente: supondo que n = pq, de φ(n) = (p− 1)(q − 1) temos que p + q = n + 1 − φ(n). Também, (p − q)² = (p + q)² − 4n. De p + q e p − q é fácil determinar p e q. De φ(n) obtem-se a chave privada d através do algoritmo de Euclides estendido.

Ainda, se d, diretamente, puder ser computado eficientemente a partir de n e e, então pode-se computar a fatoração de n eficientemente. Como a recíproca claramente é verdadeira, esses problemas são computacionalmente equivalentes.

Exercício 73 (Determinar d a partir de (e,n) implica em fatorar n). Assuma que existe um algoritmo que compute d a partir de n e e. Prove que

aed−1 ≡ 1 (mod n) ∀a ∈ ℤ∗n.

(95)

Seja s inteiro tal que ed − 1 = 2^st com t ímpar. Prove que existe i ∈{1,2,…,s} tal que

i−1 i a2 t ⁄≡ ±1 (mod n) e a2t ≡ 1 (mod n)

(96)

para pelo menos metade de todos os a ∈ ℤ_n^∗. Prove que

i−1 mdc(a2 t − 1,n) ´e um divisor de n.

(97)

Baseando-se nos fatos acima, escreva um algoritmo aleatorizado que em média com 2 rodadas de sorteio determina um divisor de n. Mostre um algoritmo aleatorizado de tempo polinomial que determina fatoração de n.

Do ponto de vista prático, a segurança depende de maneira fundamental da escolha dos primos. São conhecidos casos de quebra do RSA na prática por causa de escolhas ruins. Essa escolha depende entre outras coisas do estado-da-arte dos algoritmos de fatoração. Algumas heurísticas resultam em algoritmos eficientes de fatoração para casos particulares, por exemplo, quando |p − q|é pequeno. Também, o tamanho dos primos é importante, não é seguro usar primos de 512 bits como já foi feito, atualmente usa-se pelo menos 2048 bits. Isso deve-se essencialmente a tecnologia, processadores estão ficando mais rápidos e para instâncias pequenas de problemas intratáveis a computação é factível.

Veja mais sobre segurança e aspectos práticos do RSA nas seções 8.2.2 e 8.2.3 no Handbook of Applied Cryptography.

Exercício 74. Como pode ser a cifra do texto 100000 usando RSA com p = 11, q = 29, n = 319 e e = 3. Qual o valor de d?

Exercício 75. Prove que

Ee(P1)Ee(P2 ) ≡ Ee(P1 ⋅P2) (mod n).

(98)

Exercício 76. Prove que para todo inteiro r

(P re)d ≡ Pdr (mod n).

(99)

Exercício 77 (Ataque do módulo comum). Considere que P é cifrado com duas chaves distintas (e,n) e (f,n) tais que mdc(e,f) = 1. Mostre como P pode ser recuperado a partir dos textos cifrados P^e modn e P^f modn nesse caso.

Exercício 78 (Ataque cíclico). Sejam (e,n) chave pública, P um texto comum e C o texto cifrado correspondente. Prove que existe um inteiro positivo k tal que C^{e^k} ≡ C (mod n) e que C^{e^k−1} ≡ P (mod n). Esse ataque é viável na prática?

Exemplo 29 (Gerando um par de chaves RSA com openSSL). Exemplo de uma seqüência de comandos para gerar um par de chaves privada, pública de 32 bits e o último comando mostra os parâmetros usados, e,n,d,p,q; as outras variáveis são usadas para acelerar a computação.

$ openssl genrsa -out private_key.pem 32
Generating RSA private key, 32 bit long modulus
.+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++
e is 65537 (0x10001)
~$ openssl rsa -pubout -in private_key.pem -out public_key.pem
writing RSA key
~$ openssl rsa -text -in private_key.pem
Private-Key: (32 bit)
modulus: 2883180901 (0xabd9d965)
publicExponent: 65537 (0x10001)
privateExponent: 386553605 (0x170a5705)
prime1: 58403 (0xe423)
prime2: 49367 (0xc0d7)
exponent1: 49169 (0xc011)
exponent2: 17825 (0x45a1)
coefficient: 48081 (0xbbd1)
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MC0CAQACBQCr2dllAgMBAAECBBcKVwUCAwDkIwIDAMDXAgMAwBECAkWhAgMAu9E=
-----END RSA PRIVATE KEY-----

O texto acima segue o seguinte padrão de apresentação:

An RSA private key should be represented with the ASN.1 type
RSAPrivateKey:
RSAPrivateKey ::= SEQUENCE {
    version           Version,
    modulus           INTEGER, -- n
    publicExponent    INTEGER, -- e
    privateExponent   INTEGER, -- d
    prime1            INTEGER, -- p
    prime2            INTEGER, -- q
    exponent1         INTEGER, -- d mod (p-1)
    exponent2         INTEGER, -- d mod (q-1)
    coefficient       INTEGER, -- (inverse of q) mod p
    otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

12. Rabin

Como no caso anterior o criptossistema de Rabin é assimétrico e baseado na dificuldade do problema de fatoração. A vantagem aqui é que foi provado que quebrar o código é equivalente à fatoração.

Tome = = ℤ_n onde n é o produto de dois primos n = p ⋅ q.

A chave pública é n e a chave privada é (p,q). Dado o texto comum P, a codificação de P é C = P² modn. A codificação e feita extraindo-se a raiz quadrada de C módulo n e decidindo-se por quais das quatro raízes é o texto.

Exercício 79. Sejam p e q primos e tome u = p^q−1 − q^p−1. Mostre que u² ≡ 1 (mod p), u² ≡ 1 (mod q) e u² ≡ 1 (mod n).

Mostre que se x₀ é solução de x² ≡ a (mod n) então também são soluções −x₀, ux₀ e −ux₀.

Para facilitar (não é necessário, apenas aumenta a eficiência) a extração de raiz quadrada podemos escolher p ≡ q ≡ 3 (mod 4)______________________________

    Dado inteiros $c$ e $n = pq$ , onde $p,q ≡ 3 (mod )4$ são primos
    Devolve raiz quadrada de $c$ módulo $n$ .

    1   Determine $a,b$ tais que $ap+ bq = 1$ ;
    2   Compute $r = c(p+1)∕4 mod p$ ;
    3   Compute $s = c(q+1)∕4 mod q$ ;
    4   Compute $x = (aps+ bqr) mod n$ ;
    5   Compute $y = (aps − bqr) mod n$ ;
    6   Devolva( $(x, − x mod n, y, − y mod n)$ ).

_____________________________________________________________________

Figura 15: Raiz quadrada de c módulo n.

Exercício 80. Prove que o algoritmo acima está correto.

A segurança agora é baseada na dificuldade computacional do Problema da raiz quadrada módulo n, para n composto:_____________________________________

    Dado $n$ composto e $a$ um resíduo quadrático módulo $n$
    Devolve $x$ tal que $x2 ≡ a (mod n)$ .

_____________________________________________________________________

Figura 16: Problema da raiz quadrada módulo n.

Se a fatoração n = pq é conhecida então como vimos acima sabemos resolver esse problema eficientemente. A recíproca também vale como mostra o exercício a seguir.

Exercício 81. Suponha que exista um algoritmo eficiente que, dado a e n determina de modo eficiente uma solução de x² ≡ a (mod n). Sorteie b ∈ ℤ_n^∗ e compute b² modn, em seguida use o algoritmo anterior para determinar uma solução x de X² ≡ b² (mod n). Com probabilidade 1
2 temos x ⁄≡±b (mod n). Prove que nesse caso mdc(b − x,n) ∈{p,q}.

Exercício 82. Prove que se n é um inteiro composto ímpar e a ∈ ℤ_n^∗ então o número de soluções de X² ≡ a² (mod n) é 2^k, onde k é o número de fatores primos distintos de n.

13. Elgamal

Proposto pelo egípcio Taher Elgamal em 1985. É um sistema assimétrico com chave pública (p,g,A), onde p é um primo, g é uma raiz primitiva de ℤ_p^∗ e A = g^a ∈ ℤ_p^∗. A chave privada correspondente é o logaritmos discreto a = dlog_gA.

O espaço dos textos comuns é o ℤ_p. A função de codificação correspondente a chave pública (p,g,A) é

( ) E (p,g,A)(b,P) = gb modp, Ab ⋅P modp

(100)

onde b ∈{1,…,p− 2}é sorteado uniformemente. Portanto é um protocolo probabilístico, o que acredita-se dificulta muito a criptoanálise. Note que o mesmo texto pode ter cifras diferentes por causa de sorteios diferentes. A função de decodificação que inverte essa cifragem é

Da(B,C ) = Bp− 1− a ⋅C modp.

(101)

Dessa forma

( ) ( ( )) Da E(p,g,A)(b,P ) = Da gb modp, Ab ⋅P modp b p− 1− a a b = (g modp ) ⋅(g modp ) ⋅P modp = g(p−1)b ⋅P modp = P.

(102)

Exemplo 30. Seja (23,7,4) uma chave pública, e 6 a chave privada. Para codificar o texto 7, sorteamos b = 3 e enviamos (21,11). O receptor computa 21²³⁻¹⁻⁶ ⋅ 11 mod23 = 7.

Observação 21. As exponenciações podem ser calculadas previamente (e mantidas em segredo) o que torna a codificação bastante rápida, bastando fazer uma multiplicação modular.

A segurança do Elgamal é baseada na dificuldade computacional do Problema de Diffie–Hellman:_______________________________________________________

    Dado $p$ um primo, $g$ uma raiz primitiva módulo $p$ e
os elementos $ga mod p$ e $gb mod p$
    Devolve $gab mod p$ .

_____________________________________________________________________

Figura 17: Problema de Diffie–Hellman.

Um algoritmo eficiente para esse problema implica na quebra do El Gamal, conhecidos uma cifra g^b modp,(g^a)^b ⋅ P modp e a chave pública (p,g,g^a) esse algoritmo pode ser usado para calcular g^−ab modp e resolver (g^a)^b ⋅ P modp para P, e vice-versa.

Exercício 83. Mostre que um algoritmo eficiente para o Problema do Logaritmo Discreto (veja seção 9) implica num algoritmo eficiente para o Problema de Diffie–Hellman.

Conjectura 28. Quebrar o Elgamal implica num algoritmo eficiente para o problema do Logaritmo Discreto.

14. Assinaturas digitais

Esquemas de assinaturas digitais podem ser derivados desses sistemas criptográficos assimétricos.

Notação 47. Se P é um texto comum, denotamos por ass(P) uma assinatura digital de P.

Dizemos que uma assinatura é universalmente forjável se um adversário pode forjar uma assinatura digital sem conhecer a chave privada.

14.0.2. RSA. Alice quer enviar um documento P com uma assinatura s para Bob. Sejam (e,n) e d = d(e) um par de chaves RSA pública e privada, respectivamente, de Alice. Alice computa s = P^d modn e envia (P,s) para Bob. Para a verificação da assinatura Bob verifica se P = s^e modn.

Proposição 29. A assinatura RSA é universalmente forjável se é permitido ao adversário pedir para assinar algumas mensagens.

Demonstração. No papel do adversário, escolha r ∈ ℤ_n^∗ e peça para assinar mr modn e r⁻¹ modn. Note que ass(m₁ ⋅ m₂) = ass(m₁)ass(m₂) (veja exercício 75). ♦

14.1. Rabin.

Alice quer enviar um documento P com uma assinatura s para Bob. Sejam (p,q) e n um par de chaves RSA privada e pública, respectivamente, de Alice. Alice computa s = P^1∕2 modn e envia (P,s) para Bob. Para a verificação da assinatura Bob verifica se P = s^e modn.

Proposição 30. O sistema pode ser quebrado se é permitido ao adversário pedir para assinar algumas mensagens.

Demonstração. No papel do adversário, escolha r tome P = r² e peça para assinar P até obter uma resposta diferente de r. Se a resposta for diferente de r então as duas raízes podem ser usadas para fatorar n. ♦

Exercício 84. Mostre que o adversário pode assinar alguma mensagem, não necessariamente uma de sua escolha, apenas conhecendo a chave pública.

14.2. Elgamal.

Alice quer enviar um documento P com uma assinatura s para Bob. Sejam (p,g,A) e a um par de chaves RSA pública e privada, respectivamente, de Alice. Alice sorteia k ∈ ℤ_p−1^∗, computa r = g^k modp e s = (P − ar)(k⁻¹ modp − 1) modp − 1, envia (P,(r,s)) para Bob. Para a verificação da assinatura Bob verifica se g^P = A^rr^s modp.

Proposição 31. Um adversário pode assinar alguma mensagem, não necessariamente uma de sua escolha, apenas conhecendo um par (P,ass(P)).

Demonstração. O adversário escolhe v invertível módulo p−1, escolhe u, computa r = g^uA^v modp, computa s = −rv⁻¹ modp−1 e P = su modp−1. Assim, (r,s) é uma assinatura de P. ♦

Exercício 85. Qual é o problema de se usar o mesmo k para toda assinatura? Qual é o problema de se usar um gerador previsível para a escolha de k?

14.3. DSA.

é uma variante mais eficiente (rápido) do El Gamal adotado como padrão nos Estados Unidos. Não serve como criptossistema.

Escolha das chaves: Alice escolhe um primo 2¹⁵⁹ < q < 2¹⁶⁰ e um primo grande p ∈{2^511+64t,…,2^512+64t}, onde 0 ≤ t ≤ 8, e qp − 1.
Alice escolhe uma raiz primitiva g módulo p e computa x = g^(p−1)∕q modp e, finalmente, sorteia a ∈{1,2,…,q − 1} e computa A = g^a modp. As chaves públicas e privadas são (p,q,g,A) e a, respectivamente.
Assinatura: Para assinar P, Alice sorteia k ∈ ℤ_q^∗ e computa
$r = (gk modp ) modq e s = (k− 1 modq )(P + ar) modq.$

Então ass(P) = (r,s).
Verificação: Bob recebe (P,(r,s)) e verifica
(1) 1 ≤ r,s ≤ q − 1;
(2) r = ((g^{(s⁻¹P) modq}A^{(rs⁻¹) modq}) modp) modq;

Exercício 86. Mostre que sob as hipóteses na escolha das chaves valem: q tem 160 bits e p entre 512 e 1024 bits, p é múltiplo de 64 logo sua expansão binária tem de 8 a 16 strings de comprimento 64. Prove que se qp − 1 então ℤ_p^∗ contém um elemento de ordem q. Mostre que x tem ordem q em ℤ_p^∗.

Exercício 87. Prove que A ∈ ⟨g⟩ ⊂ ℤ_p^∗ e que esse subgrupo tem ordem aproximadamente 2¹⁶⁰.

O ganho de eficiência vem do fato que no Elgamal são feitas exponenciações com expoentes tão grandes quanto p enquanto que no DSA os expoentes são números de 160 bits.

Para o DSA também vale que

Proposição 32. Um adversário pode assinar alguma mensagem, não necessariamente uma de sua escolha, apenas conhecendo um par (P,ass(P)).

A prova e deixada como exercício. Esse ataque pode ser evitado: se trocarmos as ocorrências do texto P nos protocolos de assinatura e verificação por h(P) onde h é uma função de hash criptográfico então o esquema continua válido e a proposição acima deixa de ser verdade. O mesmo vale para o Elgamal.

Se um adversário puder computar logaritmo discreto no subgrupo ⟨g⟩⊂ ℤ_p^∗ então ele é capaz de determinar a chave privada da Alice e assinar documentos. Esse é o único ataque geral conhecido ao DSA e atualmente não se sabe levar vantagem do fato de dlog ser computado em um subgrupo de ℤ_p^∗ de ordem > 2¹⁵⁹.

15. Primalidade revisitada

Pelo que vimos, devemos ter mecanismos eficientes para obter números primos. De um modo geral, esses primos são gerados da seguinte forma______________________

      Gere um número ímpar do tamanho apropriado.
      Teste se o número gerado é primo.
      Se não for primo então volte para o passo 1.

_____________________________________________________________________

Figura 18: Gerador genérico de números primos.

Para a primeiro passo, usualmente é sorteado um número dentre todos os números ímpares do tamanho desejado. Pelo Teorema dos Números Primos a quantidade de números primos até n é n∕lnn, assintoticamente. Como metade desses números são pares, as fração de números primos é < 2∕lnn, por exemplo a proporção deles até 2²⁰⁴⁸ é ≤ 2∕2048ln2 ≈ 7∕5000.

Para o segundo passo, como a probabilidade de um número sorteado n ter um fator pequeno é alta, antes de passarmos para o algoritmos mais sofisticados, testamos se algum inteiro até um limiar M é divisor próprio de n. A proporção dos candidatos descartados nessa fase é ∏ _p=1,primo^M(1 − 1∕p) ≈ 1∕lnM. O valor de M depende, entre outras coisas, do algoritmo usado a seguir nesse passo e uma boa estratégia pode ser determiná-lo experimentalmente. Atualmente, o usual é um número da ordem de 10¹².

Vimos na seção 2 que é conhecido um algoritmo de tempo polinomial em log n para decidir primalidade, entretanto ainda é impraticável usar esse algoritmo com instâncias grandes. Aqui há duas alternativas viáveis, testes aleatorizados que podem errar mas com um probabilidade muito pequena (veja observação 8) e algoritmos determinísticos que decidem o problema da da Primalidade quando restringimos a entrada, por exemplo para números de Fermat (veja seção 2.1).

As próximas seções apresentam alternativas para o passo 2. Na seção 19 discutimos brevemente geradores de números primos.

A seguinte entrada foi retirada do manual do Maxima16 , um sistema de computação algébrica, e é um exemplo típico de como a primalidade de um número é testada na prática.

Função: primep (n)

    Teste de primalidade. Se primep  (n) retornar false, n é um número
    compostro e se  esse teste retornar true, n é  um número primo com
    grande probabilidade.

    Para n menor que 341550071728321 uma versão deterministica do teste
    de Miller-Rabin é usada. Se primep (n) retornar true, então n é um
    número primo.

    Para n maior  que 34155071728321 primep usa primep_number_of_tests
    que é os  testes de pseudo-primalidade de Miller-Rabin  e um teste
    de pseudo-primalidade  de Lucas. A probabilidade que  n irá passar
    por  um teste  de Miller-Rabin  é menor  que 1/4.  Usando  o valor
    padrão 25 para primep_number_of_tests, a probabilidade de n passar
    no teste sendo composto é muito menor que 10^-15.

Variável de opção: primep_number_of_tests

    Valor padrão: 25

    Número de testes de Miller-Rabin usados em primep.

No que segue identificamos o ℤ_n com {0,1,...,n − 1}

, para todo n.

16. Teste de Fermat

De acordo com o teorema de Fermat, dados inteiros n e a, se n é primo e não divide a então aⁿ⁻¹ ≡ 1 (mod n), portanto, qualquer outro resultado indica que n é composto. Entretanto, o teorema não garante que se aⁿ⁻¹ ≡ 1 (mod n) então n é primo. Por exemplo 2³⁴⁰ ≡ 1 (mod 341) mas 341 = 11 ⋅ 31.

Definição 48 (pseudo-primo). Um número inteiro ímpar e composto n é um pseudo-primo para a base a se aⁿ⁻¹ ≡ 1 (mod n).

Assim, 341 é pseudo-primo para a base 2. De fato, é o menor pseudo-primo para a base 2. Podemos descobrir que 341 é composto testando-o contra outras bases e nesse caso 3³⁴⁰ ≡ 54 (mod 341) o que atesta que 341 é composto. Entretanto, estender essa estratégia não produz um algoritmo eficiente para decidir primalidade, como veremos a seguir.

Todo n > 1 ímpar e composto é pseudo-primo para as bases 1 e n − 1. Não há números que sejam pseudo-primos para toda base a ∈{2,…,n− 2} pois se mdc(a,n) > 1 então aⁿ⁻¹ ⁄≡ 1 (mod n). Isso garante que se incrementamos a base e fazemos o teste de Fermat então o mais longe que iremos é até o menor divisor primo de n, mas isso pode não ser muito melhor do que usar crivo de Eratóstenes (dado no exercício 18).

Exemplo 31. Testar primalidade de 10471357350880434151684603802033528
526913077464985215455699379117762699733064822510844685769516730761
652160510194271214128021140230710440669128221618836326458128548136
9054808044171 = 2827554835337072870547521843211213457668614806974
48 703443857012153264407439766013042402571 × 37033260045095264880
23456 099083350582733994873563592630385840178271946361725689882577
69601 envolveria 10⁹⁹ tentativas, aproximadamente, o que é impraticável.

Uma saída é sortear a ∈{2,3,…,n − 2} uniformemente e verificar se aⁿ⁻¹ ≡ 1 (mod n); se sim devolva “primo, provavelmente” senão devolva “composto, certamente”. No caso n = pq, com p,q primos, por exemplo, temos n − φ(n) = p + q − 1 inteiros tais que mdc(a,n) > 1; no exemplo 31 isso dá uma probabilidade menor que (2 × 10¹⁰⁰)10⁻¹⁹⁹ = 2 × 10⁻⁹⁹ de sortear um divisor próprio de n. Resta a esperança de que aⁿ⁻¹ ⁄≡ 1 (mod n) para muitos a ∈{2,…,n − 2} tais que mdc(a,n) = 1.

Se pseudo-primos forem raros então poderíamos esperar que isso dá uma boa chance de descobrir uma testemunha a.

Exemplo 32 (pseudo-primos são raros17 ). Existem 21.853 pseudo-primos na base 2 menores que 2,5 × 10¹⁰, enquanto que a quantidade de primos é 1.091.987.405. No caso das bases 2 e 3 juntas, há apenas 23 pseudo-primos para ambas as bases no intervalo entre 1 e 100 mil.

__________________________________________________________________

    Dado um inteiro ímpar $n ≥ 3$ e o número de rodadas $k$
    Devolve $n$ é composto ou  provável primo.

    1   repita
    2      sorteie $a ∈ {2,3,...,n− 2}$ uniformemente;
    3      se $an−1 ⁄≡ 1 (mod )n$ então devolva(composto);
    4   até completar $k$ ;
    5   devolva(provável primo).

_____________________________________________________________________

Figura 19: Teste de Fermat.

Usando o algoritmo de exponenciação modular (algoritmo 7) para cada teste na linha 3, o teste de Fermat tem complexidade O(k log ³n).

Se o algoritmo responde composto então a resposta está certa, senão pode ocorrer que n é um número pseudo-primo para todas as bases escolhidas no laço repeat, nesse caso o algoritmo erra.

Se n é composto e ímpar então defina

∗ Ln = {a ∈ ℤn: n ´e pseudo-primo para a}.

(103)

Se o algoritmo respondeu errado então todos os sorteios escolheram algum elemento de L_n que é um o subgrupo do ℤ_n^∗. Logo, pelo Teorema de Lagrange, m|L_n| = |ℤ_n^∗| e se L_n for subgrupo próprio temos m ≥ 2, portanto, nesse caso a probabilidade do algoritmo errar em k sorteios independentes é menor que (1∕2)^k. Entretanto, pode ocorrer m = 1 e nesse caso o algoritmo responde certo somente se escolher a tal que mdc(a,n) > 1, o que pode ser extremamente raro.

16.1. Números de Carmichael.

Existem inteiros pseudo-primos para todas as bases coprimas a eles, i.e., existe n tal que L_n = ℤ_n^∗.

Definição 49 (números de Carmichael). Um número composto n é um número de Carmichael se

an−1 ≡ 1 (mod n) para todo a tal que mdc(a,n) = 1.

(104)

Números de Carmichael são extremamente raros, nos inteiros positivos até 10¹⁸ a quantidade18 de números de Carmichael é 1.401.644 enquanto que 24.739.954.287.740.860 é a quantidade19 de primos. Sobre a distribuição desses números, se c(n) é a quantidade de números de Carmichael até n, então é sabido que

lnnlnlnlnn- n2∕7 < c(n) < ne− lnlnn .

Note que desse fato podemos concluir que há infinitos números de Carmichael.

Exemplo 33. A densidade dos números de Carmichael até 10²⁵⁶ é menor que 0,8 × 10⁻⁵⁸. A seguinte figura mostra um gráfico da densidade c(n)∕n máxima dos números de Carmichael para n ∈ [0,10²⁵⁶]

Proposição 33 (Critério de Korselt). Um número inteiro n > 1 divide aⁿ−a para todo inteiro a se, e somente se, cada fator primo p de n satisfaz (i) p² ⁄ |
| n; e (ii) p − 1 |
| n − 1.

Demonstração. Seja n tal que n |
| aⁿ − a para todo a ∈ ℤ. Suponha que existe um fator primo p de n tal que p² |
| n. Como n |
| pⁿ − p temos p² |
| pⁿ − p que implica em ppⁿ⁻¹ − 1, um absurdo. Logo, vale (i). Agora, seja p um fator primo de n e a uma raiz primitiva módulo p. Claramente, a e p são coprimos. Como pn temos que pa(aⁿ⁻¹ − 1), ou seja, paⁿ⁻¹ − 1 e como a é raiz primitiva módulo p temos p − 1n − 1. Assim, vale (ii).

Para a recíproca, considere um inteiro positivo n que satisfaz (i) e (ii) e seja p uma fator primo de n. Para qualquer inteiro a, se pa então paⁿ − a, senão temos a^p−1 ≡ 1 (mod p), pelo teorema de Fermat, e por (ii) temos aⁿ = aaⁿ⁻¹ = aa^(p−1)q ≡ a (mod p). Logo paⁿ − a para todo fator primo p de n. Disso temos que ∏ _pnpaⁿ − a, ou seja, aⁿ ≡ a (mod n). ♦

Teorema. n é um número de Carmichael se e semente se n é um composto que satisfaz o critério de Korselt.

Demonstração. Exercício. Mostre também que todo número de Carmichael é ímpar. ♦

Corolário 34. Todo número de Carmichael tem pelo menos 3 fatores primos.

Demonstração. Se n = pq então q − 1qp − q e p − 1 ⁄qp − 1, absurdo. ♦

Exercício 88 (Há infinitos pseudo-primos para qualquer base fixa). Sejam a > 1 e p > 2 primo. Mostre que

a2p −-1 a2 − 1

(105)

é pseudo-primo para a base a.

Exercício 89 (Generalização do teorema de Euler). Prove que

aλ(n) ≡ 1 (mod n),

(106)

para todo a ∈ ℤ_n^∗, onde n = p₁^m₁p₂^m₂ ⋅⋅⋅ p_k^m_k e

λ(n ) = mmc (φ(pm11 ),φ (pm22),...,φ (pmkk )).

(107)

Exercício 90. Prove que λ(n) é o menor inteiro positivo k tal que a^k = 1 para todo a ∈ ℤ_n^∗.

Exercício 91. Prove que se n é um número de Carmichael então λ(n) |
| n − 1; vale a recíproca?

17. Teste de Miller–Rabin

O teste de Miller–Rabin deriva de uma primeira versão, de Miller, determinística mas baseada na validade da hipótese de Riemann generalizada (ainda uma conjectura). Rabin introduziu a aleatoriedade que dispensa essa hipótese20 .

A idéia desse teste é que se n é primo então para a ∈ ℤ_n^∗ temos aⁿ⁻¹ ≡ 1 (mod n) então a^(n−1)∕2 ≡ 1 (mod n) ou a^(n−1)∕2 ≡−1 (mod n); no primeiro caso temos a^(n−1)∕4 ≡ 1 (mod n) ou a^(n−1)∕4 ≡−1 (mod n), e assim por diante até que teremos ou a^{(n−1)∕2^j} ≡−1 (mod n) para algum j ou a^r ≡ 1 (mod n) para r ímpar. Por outro lado, se em algum momento temos uma raiz quadrada de 1 módulo n diferente de ±1 (veja exercício 82 abaixo), então por repetidas exponenciações a 2 temos aⁿ⁻¹ ⁄≡ 1 (mod n). Portanto, se n é primo então a seqüência a^2⁰r,a^2¹r,a^2²r, ⋅⋅⋅ ,a^{2^sr} módulo n é da forma (1,1,…,1) ou (−1,…,−1,1,1,…,1), mas se essa seqüência for da forma (…,b) com b≠1 ou (…,b,1,1,1,…,1) então n é composto e a é uma testemunha desse fato.

Proposição 35. Sejam n um primo ímpar e r,s inteiros tais que n − 1 = 2^sr com r ímpar. Seja a um inteiro tal que mdc(a,n) = 1. Então ou a^r ≡ 1 (mod n) ou a^{2^jr} ≡−1 (mod n) para algum j, 0 ≤ j ≤ s − 1.

Demonstração. Seja a como no enunciado, considere a seqüência

a20r,a21r,a22r,⋅⋅⋅,a2sr

(108)

e seja t o menor inteiro tal que a^{2^tr} ≡ 1 (mod n); note que a^{2^sr} = aⁿ⁻¹ ≡ 1 (mod n), portanto t está bem definido. Então, ou t = 0 e temos a^r ≡ 1 (mod n) ou t ≥ 1 e

a2tr − 1 = (a2t−1r +1)(a2t−1r − 1);

como n divide a^{2^tr} − 1 e, pela escolha de t, não divide a^{2^t−1r} − 1, necessariamente na^{2^t−1r} + 1, ou seja, a^{2^t−1r} ≡−1 (mod n). ♦

Exemplo 34. Seja n = 561, o menor número de Carmichael. Temos 560 = 2⁴35. Para a = 2 temos 2³⁵ ≡ 263 (mod 561), 2^2¹35 ≡ 263 (mod 561), 2^2⁴35 ≡ 263 (mod 561), finalmente 2^2³35 ≡ 263 (mod 561), portanto, n é composto.

O algoritmo original de Miller, citado acima, é baseado no fato de valer a recíproca da proposição acima supondo a validade da hipótese de Riemann generalizada.

Definição 50 (pseudo-primo forte). Dizemos que um inteiro composto ímpar n é um pseudo-primo forte para a base a, 1 ≤ a < n, se para n− 1 = 2^sr com r é ímpar vale

(109) ar ≡ 1 (mod n) ou (110) a2jr ≡ − 1 (mod n ) para algum j,0 ≤ j < s.

Defina para n composto e ímpar tal que

′ ∗ L n = {a ∈ ℤ n: n ´e pseudo-primo forte para a}.

(111)

Exemplo 35. Para n = 91(= 7 × 13), n − 1 = 90 = 2¹ × 45. Como 9r = 945 ≡ 1 (mod 91) temos que 91 é pseudo-primo forte para a base 9. Ainda,

L′ = {1,9,10,12,16,17,22,29,38,53,62,69,74,75,79,81,82,90}. 91

Vamos chamar a ∈ ℤ_n^∗\ L_n′ de testemunha do fato de n ser composto.
_____________________________________________________________________

    Dado um inteiro ímpar   $n ≥ 3$ e $r,s$ tais que   $n− 1 = 2sr$ com $r$
    ímpar e  uma base $a$
    Devolve verdedeiro se   $a$ é testemunha do fato ‘‘ $n$ é composto’’
    ou falso caso contrário.

    1    $x0 ← ar mod n$ ;
    2   para $i$ de $1$ até $s$ faça
    3           $xi ← xi−12 mod n$ ;
    4           se $xi = 1$ e $xi−1 ⁄= 1$ e $xi−1 ⁄= n− 1$ então
    5                   devolva(verdadeiro);
    6   se $xs ⁄= 1$ então devolva (verdadeiro);
    7   devolva(falso).

_____________________________________________________________________

Figura 20: Testemunha(n,a,r,s)

__________________________________________________________________

    Dado um inteiro ímpar $n ≥ 3$ e o número de rodadas $k$
    Deolve $n$ é composto ou  provável primo.

    1   determine $s$ e $r$ tal que $n − 1 = 2sr$ com $r$ ímpar;
    2   repita
    3      sorteie $a ∈ {2,3,...,n− 2}$ uniformemente;
    4      se Testemunha( $n,a,r,s$ ) então devolva(composto);
    5   até que complete $k$ rodadas;
    6   devolva(provável primo).

_____________________________________________________________________

Figura 21: Teste de Miller–Rabin.

Cada divisão por 2 na linha 1 custa O(log n), portanto, no pior caso o custo é O(log ²n). O custo de Testemunha() é essencialmente o de s = O(log n) multiplicações módulo n, cada uma custa O(log ²n), portanto a complexidade de pior caso do teste é O(k log ³n).

O próximo resultado mostra que o número de testemunhas é abundante, o que propicia um ambiente bom para algoritmos aleatorizado.

Note que se n é primo então L_n′ = ℤ_n^∗ segue da proposição 35.

Teorema. Para todo n ≥ 3 composto e ímpar

′ n−-1- |L n| ≤ 4

(112)

Demonstração. Seja n = p₁^m₁p₂^m₂ ⋅⋅⋅ p_k^m_k um inteiro ímpar e composto com n − 1 = 2^sr para r ímpar. Defina

{ } t = max j: ∃b ∈ ℤ ∗n, b2j ≡ − 1 (mod n) .

(113)

Note que que (−1)^2⁰ ≡−1 (mod n) e que t < max{ℓ: 2^ℓ |
| λ(n)} (veja exercícios 89 e 90). Defina

m = 2tr

e os subgrupos

∗ M ⊂ L ⊂ K ⊂ J ⊂ ℤn.

(114)

onde

{ ∗ n−1 } J = a ∈ ℤ∗n: am ≡ 1 (mod n)mi ; K = {a ∈ ℤn : a ≡ ±1 (mod pi )∀i}; L = {a ∈ ℤ∗n : am ≡ ±1 (mod n)}; M = {a ∈ ℤ∗n : am ≡ 1 (mod n)}.

L_n′⊆ L: Se a ∈ L_n′ então ou a^r ≡ 1 (mod n), portanto a^{2^tr} ≡ 1 (mod n), ou a^2ⁱr ≡−1 (mod n) para algum i, 0 ≤ i ≤ t, logo a^{2^tr} ≡±1 (mod n), ou seja a ∈ L.

Para provar o teorema notemos que |M| |
| |K|, |M| |
| |L|, |K| |
| |J| e |L| |
| |ℤ_n^∗|, pelo teorema de Lagrange. Pela afirmação do parágrafo anterior o teorema segue de 4|L|≤|ℤ_n^∗|. Para provar esse fato, considere que

|ℤ∗n|= |ℤ∗n||J||K-|≥ |ℤ∗n||K| = |ℤ-∗n||K-|∕|M-|. |L| |J ||K| |L | |J ||L| |J| |L |∕|M |

(115)

Vamos provar daí que |ℤ_n^∗|∕|L|≥ 4.

Primeiro, |L|∕|M| = 2: defina a relação de equivalência sobre L por a ≡ b (mod M) se e somente se ab⁻¹ ∈ M. Logo a ≡ b (mod M) se e só se em a^mb^−m ≡ 1 (mod n). Mas a^m ≡±1 (mod n) e b^−m ≡±1 (mod n), portanto a ≡ b (mod M) se e só se a^m ≡ b^−m (mod n). Logo, as duas classes de equivalência em L∕M são {a ∈ L : am ≡ 1 (mod n)} e {a ∈ L: am ≡ − 1 (mod n)} .

Agora, vamos provar que |K|∕|M| = 2^k. Defina

G = {a ∈ ℤ∗n: a ≡ ±1 (mod pmi)∀i} i

e note (eq. (113)) que para todo a ∈ G existe x tal que x^{2^t} ≡ a (mod p_i^m_i)∀i, e que K = {a ∈ ℤ ∗n: am ∈ G}

. Portanto, f : K → G dada por f(a) = a^m é sobrejetora e ker(f) = M. Pelo teorema do homomorfismo (teo. 7, pág. 90) |K|∕|M| = |G| = 2^k, onde a última igualdade segue do teorema chinês do resto (veja exercício 53).

Voltando para (115) temos

∗ ∗ ∗ |ℤn| ≥ |ℤ-n||K-|∕|M-|= |ℤn|2k−1 |L | |J| |L |∕|M | |J|

(116)

portanto, se k ≥ 3 então |ℤ_n^∗|≥ 4|L|. Se k = 2 então n não é um número de Carmichael, pelo corolário 34, logo existe a ∈ ℤ_n^∗ tal que aⁿ⁻¹ ⁄≡ 1 (mod n), ou seja, J≠ℤ_n^∗. Como J é um subgrupo próprio |ℤ_n^∗|∕|J|≥ 2, portanto, |ℤ_n^∗|≥ 4|L|.

Finalmente, se k = 1 então n = p^e com e ≥ 2. Usando o isomorfismo entre os grupos (ℤ_n^∗,⋅) e (ℤ_φ(n),+) temos que o número de soluções módulo n de xⁿ⁻¹ ≡ 1 (mod n) é igual ao número de solução módulo φ(n) de (n − 1)x ≡ 0 (mod φ(n)), nesse caso |J| = mdc(n − 1,φ(n)) = mdc(p^e − 1,(p − 1)p^e−1) = p − 1. Exceto quando p^e = 9 vale |ℤ_n^∗|∕|J| = p^e−1 ≥ 4; no caso n = 9 verifica-se que L_n′ = {−1,1}≤ (n − 1)∕4. ♦

Corolário 36. O teste de Miller–Rabin erra com probabilidade menor que (1∕4)^k. ♦

Exercício 92. Prove as inclusões da equação (114).

Exercício 93. Prove que L_n definido em (103) contém L_n′ definido em (111).

Observação 22. Para a maioria dos inteiros compostos n a quantidade de bases para as quais n é pseudo-primo forte é bem pequeno, menor que φ(n)∕4. Por exemplo, para n = 105 temos L₁₀₅′ = {1,104}. Entretanto, existe inteiro n tal que |L_n|∕φ(n) = 1∕4, como é o caso do 91, temos |L_n′| = 18, como vimos no exemplo 35, e φ(n) = 72.

18. Primos de Mersenne

Os maiores primos conhecidos ao longo da história tem sido, quase sempre, números de Mersenne. Isso ocorre devido à forma eficiente como é comprovada a primalidade de números de Mersenne.

Definição 51 (números de Mersenne, primo de Mersenne). Um número de Mersenne é um inteiro positivo da forma M_n = 2ⁿ − 1, para n > 1, se M_n é primo então é chamado primo de Mersenne.

O teste de Lucas-Lehmer é baseado na seguinte caracterização de primos de Mersenne que não será provado21 neste texto.

Teorema. Para todo n > 1 o número de Mersenne M_n = 2ⁿ − 1 é primo se e somente se

n é primo;
a seqüência definida para todo i ≥ 0 por u₀ = 4 e u_i+1 = (u_i² − 2) modn satisfaz u_n−2 = 0.

__________________________________________________________________

      Dado um número de Mersenne $m = 2n − 1$ com $n ≥ 3$
      Devolve $m$ é composto ou $m$ é primo.

      1   determine se $2n − 1$ tem um fator entre $2$ e $√n--$ ;
      2    $u ← 4$ ;
      3   para $u$ de $1$ até $n − 2$ faça
      4          $u ← (u2 − 2) mod Mn$
      5         se $u = 0$ então devolva(primo);
      6   devolva(composto).

_____________________________________________________________________

Figura 22: Teste de Lucas–Lehmer.

Exercício 94. Mostre que a complexidade do teste de Lucas–Lehmer é O(log ³n).

Não é sabido se existem infinitos primos de Mersenne. Também, não se sabe se existem infinitos primos p para os quais M_p é composto.

Conjectura 37. Existem infinitos primos p para os quais M_p é primo.

O seguinte resultado serve para “descartar” alguns números de Mersenne.

Proposição 38. Seja p primo tal que p ≡ 3 (mod 4). Então 2p + 1 é primo se e somente se 2p + 1M_p.

Demonstração. Ponha q = 2p + 1 e suponha que qM_p. Se q não é primo então tem fator r com r ⁄≡ 1 (mod p) pois r < p. Se 2p + 1M_p então r é um fator de M_p. Se rM_p então 2^p ≡ 1 (mod r), como p é primo ord_{ℤ_r^∗}(2) = pr − 1, ou seja, r ≡ 1 (mod p), uma contradição, portanto q é primo.

Se q é primo então M_p = 2^p − 1 = 2^(q−1)∕2 − 1 ≡ 0 (mod q) (exercício). ♦

Observação 23. Primos de Mersenne têm uma história longa, os pitagóricos batizaram de perfeito todo número n tal que a soma dos divisores positivos vale 2n, por exemplo 6, 28 e 496 são perfeitos. Euclides notou que se M_p é primo então 2^p−1M_p é perfeito. Não é difícil provar quer todo número perfeito par é da forma 2^p−1M_p para p primo e M_p primo. A seguinte conjectura é uma das mais antigas da matemática.

Conjectura 39. Não existe número perfeito ímpar.

Observação 24. Note que se p é primo, M_p composto e q é um fator primo de M_p então 2^p ≡ 1 (mod q), logo 2 tem ordem p em ℤ_q^∗, portanto pq − 1, dai p < q. Desse fato podemos derivar uma demonstração de que existem infinitos números primos.

18.1. Teste baseado em fatoração.

Existem alguns testes para primalidade de n baseados na fatoração de n + 1 ou de n− 1. Esses testes funcionam bem quando essas fatorações são fáceis como é o caso dos números de Fermat e de Mersenne.

O próximo teste é aleatorizado e funciona se é conhecida a fatoração e n− 1. A idéia é que se existe a tal que

aⁿ⁻¹ ≡ 1 (mod n) e
a^(n−1)∕p ⁄≡ 1 (mod n) para todo p primo e divisor de n − 1.

então pelo corolário 24 (página 101) a tem ordem n − 1, como n − 1 deve dividir φ(n) ≤ n − 1 temos que φ(n) = n − 1, ou seja, n é primo. Suponha que n é primo; se sorteamos a e aplicamos os testes (1) e (2) então a probabilidade de escolher um elemento de ordem n − 1 é φ(n − 1)∕(n − 1) (veja corol. 22), portanto, o número esperado de sorteios até descobrirmos uma testemunha de que n é primo é μ = n − 1∕φ(n − 1). Usando o fato que para todo n ≥ 5

φ(n) >---n--- 6lnlnn

(117)

então μ < 6lnln(n − 1).

_____________________________________________________________________

    Dado inteiros positivos $n$ , $k$ e os fatores primos de $n − 1$
    Devolve $n$ é provável composto ou primo.

    1   repita
    2       sorteie $a ∈ {2,3,...,n− 1}$ uniformemente;
    3       se $an−1 ≡ 1 (mod n)$ então
    4            para cada fator primo $p$ de $n − 1$ faça
    5                  se $a(n−1)∕p ⁄≡ 1 (mod n )$ devolva(primo);
    6   até que complete $k$ iterações;
    7   devolva(provável composto).

_____________________________________________________________________

Figura 23: Teste de Lucas.

A probabilidade do número de rodadas até encontrar uma testemunha ser maior que k é, usando a desigualdade de Markov, menor que μ∕k. Com k = 12lnlnn essa probabilidade é menor que 1∕2 e com k = lnn a probabilidade tende a zero.

Cada iteração no algoritmo calcula uma exponencial para cada fator primo de n. Uma exponenciação modular custa O(log ³n) e são O(log n) fatores, portanto a complexidade é O(k log ⁴n).

O teste de Lucas requer uma fatoração completa de n − 1. O seguinte resultado permite um teste conhecendo-se somente uma parte da fatoração.

Teorema (Pocklington, 1914). Suponha n − 1 = q^kR com q primo que não divide R. Se existe um inteiro a tal que aⁿ⁻¹ ≡ 1 (mod n) e mdc(a^(n−1)∕q − 1,n) = 1, então todo fator primo de n é congruente a 1 módulo q^k.

Demonstração. Seja p um divisor primo de n, e seja m a ordem de a módulo p. Então m |
| n − 1 (primeira hipótese sobre a), mas não divide (n − 1)∕q (segunda hipótese), logo q^k |
| m. O resultado segue de m |
| p − 1. ♦

Corolário 40. Se n− 1 = FR, com F > R, e para todo fator primo q de F existe a > 1 tal que (i) aⁿ⁻¹ ≡ 1 (mod n) e (ii) mdc(a^(n−1)∕q − 1,n) = 1, então n é primo.

Demonstração. Tome q^k a maior potência de q que divide F. Todo fator primo de n deve ser côngruo a 1 módulo q^k, portanto côngruo a 1 módulo F; F > √--
n implica que n é primo. ♦

Exercício 95 (teste de Pépin, 1877). Seja F_n = 2^2ⁿ + 1 o n-ésimo número de Fermat (veja seção 2.1). Prove que F_n é primo se e somente se 3^{(F_n−1)∕2} ≡ −1 (mod F_n) (Dica: o “se” segue do exercício 61, a prova do “somente se” precisa de um resultado chamado de lei da reciprocidade quadrática, veja a entrada da Wikipedia para

teste de Pépin.)

Exercício 96 (teste de Proth, 1878). Uma quantidade relevante do maiores primos conhecidos são caracterizados pelo resultado a seguir, devido a fácil implementação desse teste. Prove o seguinte:

Seja n = r2^s + 1 com 2^s > r. Então n é primo se e somente se existe um inteiro a tal que a^(n−1)∕2 ≡−1 (mod n).

Seja n = rq^s + 1 com q primo e q^s > r. Prove que se existe um inteiro a tal que aⁿ⁻¹ ≡ 1 (mod n) e mdc(a^(n−1)∕q − 1,n) = 1, então n é primo.

Exercício 97. Derive algoritmos para testar primalidade para os casos particulares tratados nos dois exercícios acima. Determine a complexidade dos algoritmos.

19. Como gerar de números primos

A seguir veremos com um pouco mais de detalhes a técnica dada no começo dessa seção para gerar primo: sorteie um número e teste primalidade até que tenha-se um número primo.

19.1. Gerar números pequenos.

Com a tecnologia atual números até 10¹² são rapidamente gerados por boas implementações do Crivo de Eratóstenes.

Uma técnica mais recente é o Crivo de Atkin–Bernstein22 que testa inteiros representados por formas quadráticas, por exemplo, um inteiro positivo p ≡ 1 (mod 4) não-divisível por um quadrado é primo se e somente se o número de soluções (x,y) positivas de 4x² + y² = p é ímpar. Um dos autores mantém uma implementação desse algoritmo em http://cr.yp.to/primegen.html onde afirma que a implementação gera os 50.847.534 primos até 1.000.000.000 em 8 segundos em um Pentium II-350. O crivo de Atkin–Bernstein computa primos até n realizando O(n∕log log n) operações enquanto que o crivo de Eratóstenes realiza O(n) operações.

19.2. Gerar prováveis primos.

Vamos assumir que temos uma fonte de bits aleatórios que fornece bits com distribuição uniforme e em tempo constante.

Notação 52. Escrevemos s ←_R{0,1}^k nos algoritmos para denotar que s recebe da fonte uma string de k bits aleatórios. Denotamos por (s)₁₀ o número s em notação decimal.

__________________________________________________________________

    Dado inteiro positivo $M$ de $k$ bits
    Devolve um inteiro escolhido uniformemente em   ${0,1,...,M − 1}$ .

    1   repita
    2      $s ← {0,1}k$ aleatoriamente;
    3      $n ← (s)10$ ;
    4   até que $n < M$ ;
    5   devolva( $n$ ).

_____________________________________________________________________

Figura 24: Gerador de números aleatórios.

Denote por I, T e N as variáveis aleatórias “número de iterações do repeat”, “tempo de execução” e “valor devolvido”, respectivamente. Note que n na linha 3 tem distribuição uniforme sobre o conjunto {0,1,…,2^k − 1}, portanto, Pr(n < M) = M∕2^k. A variável I tem distribuição geométrica com probabilidade de sucesso M∕2^k, portanto o número esperado de iterações é E(I) = 2^k∕M ≤ 2. O tempo do algoritmo é T = O(k)I, logo E(T) = O(k). Note que Pr(N = n|n < M) = 1∕M.

Uma versão mais eficiente seria devolver n modM, o que evitaria a execução de mais que uma iteração do repita, entretanto, o resultado não tem distribuição uniforme em {0,…,M}. Isso pode ser visto tomando M = 5, teríamos qualquer um dos números 0,1,2 duas vezes mais prováveis que os números 3 e 4.

Exercício 98. Suponha que temos uma fonte de bits aleatórios que devolve 1 com probabilidade p e 0 com probabilidade q = 1 − p, independentemente, onde p≠q. Mostre como obter bits com distribuição uniforme dessa fonte.

Observação 25. Para obtermos n aleatório uniformemente no intervalo B = {a,…,b} basta executar o algoritmo acima com M = b − a e devolver n + a.

Notação 53. Denotamos por n ←_RB o fato de n receber um inteiro do intervalo B dado pelo algoritmo 24 segundo a observação 25 acima.

__________________________________________________________________

    Dado inteiro positivo $M$ de $k$ bits
    Devolve um primo escolhido uniformemente em ${2,...,M }$ .

    1   repita
    2      $n ← {2,3,...,M }$ aleatoriamente;
    3   até que Teste_Primo( $n$ );
    4   devolva( $n$ ).

_____________________________________________________________________

Figura 25: Gerador de números primos aleatórios.

Denote por I, T e N as variáveis aleatórias “número de iterações do repeat”, “tempo de execução” e “valor devolvido”, respectivamente. Na análise desse algoritmo vamos usar o teorema dos números primos donde derivamos que se π(n) é a quantidade de primos menores ou iguais a n então π(n) = Θ(n∕log n). Na linha 2 temos Pr(n primo) = π(M)∕(M − 1), portanto, E(I) = (M − 1)∕π(M) = Θ(k).

Vamos supor que Teste_Primo(n) é um algoritmo determinístico que decide primalidade. Considere o conjunto de instâncias B = {2,3,…,M} e denote por TP(n) o tempo gasto pelo algoritmo determinístico para decidir primalidade numa instância n ∈ B. Então o tempo esperado, se todas as instâncias são eqüiprováveis, é

∑M T P(n) μM = --n=2------, M − 1

o tempo esperado numa iteração é O(k) + μ_M, logo

E (T ) = (E(TP )+ O(k))E (I) = (μ + O(k))O (k). M

Observação 26. É razoável supormos que μ_M = Ω(k) e assim podemos escrever E(T) = O(kμ_M).

Agora, se Teste_Primo(n) é um algoritmo aleatorizado que devolve falso caso n é composto e verdadeiro caso n seja, provavelmente, primo (equivalentemente, devolve composto ou provável primo com a notação que já usamos), então o tempo esperado de execução envolve a distribuição de probabilidade em I e a distribuição dos bits aleatórios usados pelo algoritmo de teste de primalidade

∑M ∑M μM = E (T P(n))Pr(n ) =--n=2E-(T-P(n)). n=2 M − 1

Entretanto, com a utilização desses algoritmos o repita pára nas entradas primas e pseudo-primas, ou seja, podemos afirmar que o tempo esperado de execução do algoritmo 25 não aumenta quando usamos um teste probabilístico ao invés de um determinístico.

Seja Teste_Primo(n) um algoritmo aleatorizado como acima com probabilidade de responder errado no máximo ε, para algum ε > 0.

Numa iteração do laço, seja C o evento “n, sorteado na linha 2, é composto”, que ocorre com probabilidade δ, e S o evento “Teste_Primo(n), na linha 3, declara n primo”. A probabilidade do algoritmo 25 devolver um número composto numa iteração é Pr(C ∩ S).

O número esperado de iterações do repita é E(I) = 1∕Pr(S). De

-- -- -- Pr(S) = Pr(S ∩C )+ Pr(S ∩ C ) = Pr(S ∩ C )+ Pr(C ) > Pr(C )

temos

1 1 1 E (I) = -----≤ ------= ----. Pr(S) Pr(C) 1− δ

(118)

A probabilidade do algoritmo 25 devolver um número composto é dada por Pr(N é composto) = ∑ _i≥1Pr(C_i), onde C_i é o evento “devolve um composto na i-ésima iteração”. Claramente, Pr(C_i) = Pr(C ∩ S)Pr(I ≥ i), logo

∑ Pr(Ci) = Pr(C ∩ S)∑ Pr(I ≥ i) = Pr(S|C)Pr(C)E(I) i≥1 i≥1 Pr(S|C )Pr(C ) Pr(S|C) ε = ------------ ≤ ------- ≤ -----. α 1− δ 1− δ

Teorema. No algoritmo 25, se δ é a probabilidade de n receber um número composto na linha 2 e ε é a probabilidade de Teste_Primo(n) errar linha 3 então

Pr(N ˊe composto) ≤-ε--. 1− δ

(119)

Corolário 41. Se Pr(N = n|n < M) é uniforme então

Pr(N ˊe composto) = εO(k),

(120)

onde k é o número de bits de M.

19.3. Números primos com k bits.

O postulado de Bertrand garante que para todo inteiro positivo n existe um primo p tal que n < p < 2n. Uma versão mais forte desse famoso resultado23 garante que existem mais que n∕(3log(2n)) primos nesse intervalo.

Esse fato garante que existem mais que 2^k−1∕(3log(2^k)) ≈ 2^k−1∕k primos com k bits para todo k ≥ 2. Assim, a probabilidade de um sorteio (uniforme) no intervalo {2^k−1,…,2^k − 1} produzir um primo é ≈ 1∕(2k), logo E(I) = O(k) e o algoritmo 25 modificado de acordo com a observação 25 erra com probabilidade 2kε, aproximadamente.

19.4. Usando o teste de Miller–Rabin.

No caso do teste de Miller–Rabin vimos, corolário 36, que ε < (1∕4)^t, onde t é o número de rodadas. Da seção anterior resulta que o gerador de primos baseado no teste de Miller–Rabin erra com probabilidade menor que

( ) 1 t 4 2k

(121)

O tempo esperado de execução do teste de Miller–Rabin é μ_M = O(tk³), portanto, gerar um número primo tem tempo esperado E(T) = (O(tk³ + O(k))O(k) = O(tk⁴). Esse tempo está superestimado se observarmos que quando n é composto então esperamos que o teste de Miller–Rabin termina antes das t rodadas.

Seja Z o número de rodadas do teste; quando n é primo Y = t e quando n é composto esse fato é detectado com probabilidade pelo menos 3∕4.

E (Y ) = E(Y|n primo()Pr(n primo ))+ E(Y |n c(omp)osto)Pr(n composto) π(M-)- 4 -π(M-) 4 t- = tM − 1 + 3 1− M − 1 = 3 + O k .

Com essa estimativa μ_M = O(k³ + tk²) e E(T) = O(k⁴ + tk³).

Como já foi comentado, o teste de primalidade do número sorteado pode ser mais eficiente se testamos na força-bruta os casos pequenos. Assim, um gerador de prováveis primos baseado no teste de Miller–Rabin pode ser escrito como
_____________________________________________________________________

    Dado inteiros positivos $k$ e $t$
    Devolve um inteiro de $k$ bits, provavelmente primo.

    1    $n ←R {2k− 1,...,2k − 1}$ ;
    2   se $n$ é par então volte para a linha 1;
    3   se $m ⁄ ||n$ para todo $m ≤ B$ então
    4       se Miller--Rabin( $n,t$ ) devolve primo então devolva( $n$ );
    5       senão volte para linha 1.

_____________________________________________________________________

Figura 26: Gerador de prováveis primos.

Certamente, o algoritmo acima não tem probabilidade de erro maior que (121). Boas estimativas24 para ε mostram que (121) está superestimada freqüentemente. Por exemplo, se for possível tolerar a probabilidade de erro de (1∕2)⁸⁰, então para gerar um número de 1000 bits é suficiente tomar t = 3.

Ainda, podemos combinar esse teste com algumas informações conhecidas25 sobre pseudo-primos fortes para a base a que abreviamos a-pspf:

Se n < 1.373.653 é 2-pspf e 3-pspf, então n é primo.
Se n < 25.326.001 é 2,3,5-pspf, então n é primo.
Se n < 118.670.087.467 é 2,3,5,7-pspf, então n = 3.215.031.751 ou é primo.
Se n < 2.152.302.898.747 é 2,3,5,7,11-pspf, então n é primo.
Se n < 3.474.749.660.383 é 2,3,5,7,11,13-pspf, então n é primo.
Se n < 341.550.071.728.321 é 2,3,5,7,11,13,17-pspf, então n é primo.

Os primeiros três deles são de Pomerance, Selfridge e Wagstaff26 , e todos os outros são devidos a Jaeschke27 . No mesmo artigo Jaeschke considerou outros conjuntos de primos e encontrou resultados ligeiramente melhores

Se n < 9.080.191 é 31,73-pspf, então n é primo.
Se n < 4.759.123.141 é 2,7,61-pspf, então n é primo.

e por Charles Geathouse28

Se n < 1.122.004.669.633 é 2,13,23,1662803-pspf, então n é primo ou n = 46.856.248.255.981.
Se n < 10¹6 é 2,3,7,61,24251-pspf, então ou n = 46.856.248.255.981 ou n é primo.

19.5. Usando o teste de Fermat.

O que faz o teste de Fermat apropriado para gerar números primos aleatoriamente é a raridade dos pseudo-primos; usando estimativas de Pomerance29 é possível provar que um número de 1024 bits escolhido aleatoriamente será pseudo primo na base 2 com probabilidade menor que 10⁻⁴¹.

Observação 27 (Primos no PGP30 ). O teste Fermat é usado pelo PGP com k = 4 para gerar números primos. A chance do PGP gerar um número de Carmichael é menor que 1 em 10⁵⁰.

Su Hee Kim e Carl Pomerance31 consideraram a probabilidade Pr(x) que um pseudo-primo menor que x é composto. Mais especificamente, dado x então Pr(x) é a probabilidade de n ser composto dado que

n é escolhido aleatoriamente com 1 < n ≤ x;
a é escolhido aleatoriamente com 1 < a < n − 1;
aⁿ⁻¹ = 1 (mod n).

dígitos de x	limitante para Pr(x)

500	2.3 × 10⁻⁵⁵
700	1.8 × 10⁻⁸²
1000	1.2 × 10⁻¹²³
2000	8.6 × 10⁻²⁶²
5000	7.6 × 10⁻⁶⁸⁰
10000	1.6 × 10⁻¹³³¹
100000	1.3 × 10⁻¹⁰⁵⁸⁴

Por exemplo, se você escolher um aleatoriamente um número ímpar n de 120 dígitos, escolher uma base a tal que n é um pseudo-primo ara a então a a probabilidade de que n é composto é inferior a 0,00000000000528. Foi mostrado por Erds e Pomerance que Pr(x) → 0 conforme x →∞.

20. AKS

20.1. Ideal e Anel quociente.

Seja (A,+,⋅) um anel comutativo.

Definição 54 (ideal). I ⊆ A é um ideal de A se (I,+) é um subgrupo de (A,+) e ai ∈ A para todos a ∈ A e i ∈ I.

Com essa definição a multiplicação em A define naturalmente uma multiplicação em A∕I = {[a]I : a ∈ A } .

Definição 55 (anel quociente). Se I é um ideal do anel A então o conjunto das classe de equivalência módulo I com a soma [a]_I + [b]_I = [a + b]_I e a multiplicação [a]_I[b]_I = [ab]_I é um anel, chamado de anel quociente.

Notação 56 ((a₁,…,a_k)). Dados {a₁,…,a_k}⊆ A denotamos por (a₁,…,a_k) o menor subanel de A que contém {a₁,…,a_k}.

Exercício 99. Mostre que

(a1,...,ak) = {r1a1 + ⋅⋅⋅+ rkak : r1,...,rk ∈ A}.

Exercício 100. Determine ℤ∕(n).

Exercício 101. Considere o anel ℤ_n[X]. Determine o subgrupo ⟨X⟩ do grupo (ℤ_n[X],+) e o ideal (X) do anel (ℤ_n[X],+,⋅).

O anel que interessa no momento é o anel de polinômios ℤ_n[X].

Exercício 102. Todo ideal de ℤ_p[X], para p primo, é da forma (g) para algum polinômio g ∈ ℤ_p[X].

Seja f,g,h ∈ ℤ_p[X], p primo, com g de grau n. Então para [h] ∈ ℤ_p[X]∕(g) temos f ∈ [h] se e somente se gh − f portanto, pelo teorema da divisão para polinômios a classe [h] tem um único polinômio mônico de grau < n, assim toda classe pode ser representada por um polinômio mônico de grau menor que n. Note que [g] = [0], ou seja, supondo que g = Xⁿ + a_n−1Xⁿ⁻¹ + ⋅⋅⋅ + a₁X + a₀ temos

[Xn ] = [− an−1Xn −1 − ⋅⋅⋅− a1X − a0].

(122)

Exemplo 36. Considere o anel quociente ℤ₂[X]∕(X² + X + 1). Claramente,

ℤ2[X]∕(X2 + X + 1) = {[0],[1],[X ],[X + 1]} .

De acordo com (122) temos [X²] = [−X − 1] = [X + 1]. Ainda

[X +1]2 = [X2 + 2X + 1] = [X2 ]+ [2X ]+ [1] = [X ]2 + [1] = [X ].

portanto, a tabela de multiplicação desse anel é

⋅	[0]	[1]	[X]	[X + 1]

[0]	[0]	[0]	[0]	[0]
[1]	[0]	[1]	[X]	[X + 1]
[X]	[0]	[X]	[X + 1]	[1]
[X + 1]	[0]	[X + 1]	[1]	[X]

Teorema. Sejam a e n coprimos. Então n ≥ 2 é primo se e somente se

(X + a)n = Xn + a no anel ℤn[X ].

(123)

Demonstração. Se n é primo, então n divide (n)
i para i ∈ {1,2,...,n − 1} , portanto (X + a)ⁿ = Xⁿ + aⁿ em ℤ_n[X] e (123) segue do teorema de Fermat.

Por outro lado, se n > 1 é composto, seja p^k a maior potência do primo p que divide n. Então n = p^kc e

( ) ( ) n = pk−1c n − 1 . p p − 1

Se p^k divide o lado direito então p (n− 1)
p− 1 , absurdo. Também, como a e n são coprimos mdc(p^k,mdc(a^n−q,p^k) = 1, logo o coeficiente de X^p em (X + a)ⁿ, é não-nulo. ♦

O resultado acima foi a base de um algoritmo probabilístico polinomial de Agrawal e Biswas32 e é uma generalização do pequeno teorema de Fermat.

Exercício 103. Deduza o teorema de Fermat a partir do teorema 20.1.

Exercício 104. Se p é primo e k ≥ 0 inteiro então para todo a ∈ ℤ_p vale a igualdade

(X + a)pk = Xpk + a

(124)

no ℤ_p[X].

Exercício 105. Um polinômio em ℤ_p[X], onde p é primo, é dito irredutível se não pode ser escrito como produto de polinômios de grau menor. Prove que se p(X) é irredutível então ℤ_p[X]∕(h(X)) é um corpo.

20.2. Algoritmo AKS.

O teste dado pelo teorema 20.1 não é prático porque computar os coeficientes do lado esquerdo de (123) toma tempo Ω(n). Uma alternativa seria avaliar tal identidade módulo um polinômio de forma X^r − 1 no anel ℤ_n[X] para uma escolha apropriada de r com r = poly(log n), ou seja, usar o teste

n n r [(X + a)] = [X + a] no anel ℤn[X]∕(X − 1).

(125)

Se n é primo então a equação (125) vale, mas a recíproca não vale. Agrawal, Kayal e Saxena contornaram essa dificuldade mostrando que se (125) vale para uma quantidade polinomial (em log n) de valores de a então n é uma potência de primo.

Teorema. Sejam s,n ∈ ℕ, s ≤ n, inteiros positivos. Sejam q e r primos tais que qr − 1 e n^(r−1)∕q modr ⁄∈{0,1}, e

( ) q+ s − 1 2⌊√r⌋ s ≥ n .

(126)

Se para todo a ∈ {1,2,...,s− 1} vale que a é coprimo a n e vale (125) então n é uma potência de primo.

Antes de provar esse teorema, vamos estabelecer o seguinte.

Proposição 42. Sejam n,r,a,p inteiros, p primo, tais que [(X + a)ⁿ] = [Xⁿ + a] em ℤ_p[X]∕(X^r − 1). Então

ni ni [(X + a) ] = [X + a]

(127)

em ℤ_p[X]∕(X^r − 1) para qualquer inteiro i ≥ 0.

Demonstração. Para i = 0 é trivial e para i = 1 vale por hipótese. A prova segue pro indução, suponha que vale para i ≥ 0. Da hipótese da proposição temos que (X + a)ⁿ = Xⁿ + a + q(X)(X^r − 1) e substituindo n por nⁱ temos

ni n ni+1 ni nir (X + a) = X + a+ q(X )(X − 1)

e como [X^nⁱr − 1] = [0] no anel ℤ_p[X]∕(X^r − 1) temos

ni n ni+1 [(X + a) ] = [X + a]

e usando a hipótese indutiva [X^nⁱ + a]ⁿ = [(X + a)^nⁱ]ⁿ = [X + a]^nⁱ⁺¹, logo

i+1 i+1 [X + a]n = [Xn + a].

♦

Idéia da demonstração do teorema 20.2. Sejam r,q primos tais que q |
| r − 1, p um primo que divide n tal que p^(r−1)∕q modr ⁄∈ {0,1}; tal p existe pois se todos os fatores de n não tivessem a propriedade então n também não teria. Considere os produtos da forma t = nⁱp^j, onde 0 ≤ i,j ≤ ⌊√r-⌋ ; note que 1 ≤ t ≤ n². Como há (+1)² > r pares, pelo princípio da casa dos pombos existem t₁ e t₂ côngruos módulo r. Note que se t₁ = t₂ então n é potência de p.

Usando a proposição anterior, o exercício 104 e o teorema de Fermat

[(X +a)nipj] = [(Xni + a)pj] = [Xnipj +a]

no ℤ_p[X]∕(X^r − 1). Portanto [(X + a)^t_j] = [X^t_j + a](∀j ∈ {1,2} ).

De t₁ ≡ t₂ (mod r) temos X^r − 1|X^t₁ − X^t₂ e da equação acima

t t [(X + a)1] = [(X + a) 2].

Seja h ∈ ℤ_p[X]∕(X^r−1) um fator irredutível (X^r − 1)∕(X − 1) = X^r−1 + ⋅⋅⋅ + X + 1; é sabido, e vamos assumir aqui, que o grau desse polinômio é a ordem (multiplicativa) de p módulo r, portanto maior ou igual a q, caso contrário p^(r−1)∕q ≡ 1 (mod r).

Seja G = ⟨{X + a: a ∈{1,2,…,s − 1}}⟩ subgrupo do grupo multiplicativo do corpo ℤ_p[X]∕(h(X)). Os elementos de G são da forma ∏ _a∈S(X + a)^m_a onde ∑m_a ≤ q − 1. De p^(r−1)∕q ⁄≡ 0,1 (mod r) pode ser mostrado que |G|≥ (q+s− 1)
s .

Note que [(X + a)^t₁] = [(X + a)^t₂] para todo 1 ≤ a < s. Em G temos g^t₁ = g^t₂ para todo g ∈ G. Se t₁≠t₂ então g^t₁ = g^t₂ tem no máximo |t₁ − t₂| soluções num corpo.

( ) |G | ≥ q +s − 1 ≥ n2⌊√r⌋ ≥ n⌊√r⌋p⌊√r⌋ > |t− t | s 1 2

portanto, t₁ = t₂. ♦

Observação 28. É conjeturado que se r > 1 não dividir n e (125) vale, então n é primo ou n² ≡ 1 (mod r).

__________________________________________________________________

    Dado inteiro $n > 1$
    Devolve $n$ é primo ou é composto.

    1   se $n$ é da forma $ab$ para $a ∈ ℤ+$ e $b > 1$
               então devolva(composto);
    2   escolha $q,r,s$ que satisfaçam as hipóteses do teorema 20.2
    3   para $a$ de $1$ até $s − 1$ faça
    4     se $mdc (a,n) > 1$ então devolva(composto);
    5     se $[(X + a)n] ⁄= [Xn + a]$ no $ℤn[X ]∕(Xr − 1)$
               então devolva(composto);
    5   devolva(primo).

_____________________________________________________________________

Figura 27: Teste de primalidade AKS.

Se n é primo as condições das linhas 1 e 4 são falsa. Pelo teorema 20.1 a condição da linha 5 também é falsa, portanto o algoritmo responde primo. Por outro lado, se o algoritmo responde primo, então n não é da forma a^b com b > 1, mdc(c,n) = 1 para todo c ∈ {1,...,s − 1} e (125) vale. Um teorema não trivial de Fouvry33 garante a existência de r e q como na hipótese com

6 √ - r = O(log n) e q ≥ 4 rlog n,

(128)

assim podemos tomar s = 2 √ -
r log n que vale a desigualdade (123), portanto, pelo teorema 20.2 n = p¹.

20.3. Análise da complexidade .

No que segue usaremos a notação (f(n)) para denotar a classe das funções O(f(n)poly(log f(n))).

Exercício 106. Mostre que se f(n) = (log ^kn) então f(n) = O(log ^k+εn), para todo ε > 0.

A linha 1 pode ser feita em tempo (log n).34 Um algoritmo de complexidade (log ³n), mas bastante simples, é o seguinte

_____________________________________________________________________

  1   para $b$ de $2$ até $⌊log n⌋$ faça
  2      $x ← ⌊n1∕b⌋$ ; //por método de Newton//
  3     se $xb = n$ então devolva(sim);
  4   devolva(não).

_____________________________________________________________________

Figura 28: Testa se n = a^b.

Vamos verificar que esse algoritmo executa O(log ²nlog log n) multiplicações. O número de multiplicações é O(log b) para a linha 3 mais o número de multiplicações na linha 2. Nessa linha

_____________________________________________________________________

  1      $ℓ ←$ número de bits de $n$ ;
  2      $x ← 2⌈ℓ∕b⌉$ ;
  3     repita
  4        $⌊ (b−1)x+⌊n∕pb−1⌋⌋ y ← -----b-------$ ;
  5       se $y ≥ x$ então devolva( $x$ );
  6        $x ← y$ ;
  7     até que falso.

_____________________________________________________________________

Figura 29: Método de Newton para ⌊n1∕b⌋

;

A convergência do método de Newton é quadrática, portanto, o repeat é executado no máximo log( ⌈ℓ∕b⌉ ) = O(log log n) vezes, a linha 4 contribui com O(log n) multiplicações, portanto, o método de Newton realiza O(log nlog log n) multiplicações. Com isso, n = a^b pode ser decidido com O(log ²nlog log n) multiplicações de números de tamanho O(log n), logo a complexidade é O(log ⁴nlog log n). Se usamos Transformada Rápida de Fourier, ao invés do algoritmo usual de multiplicação, o custo de cada multiplicação de números de tamanho O(log n) é O(log nlog log n), o que resulta num algoritmo para decidir potência com complexidade O(log ³n(log log n)²) = (log ³n).

Exercício 107. Uma alternativa ao método acima para determinar se n é da forma a^b é com segue: seja k tal que 2^k−1 ≤ n < 2^k; então uma b-ésima raiz de n pertence ao intervalo 2 ≤ n^1∕b < 2 e podemos fazer uma busca binária nesse intervalo. Descreva o algoritmo em detalhes e determine a complexidade.

De volta ao algoritmo 27, o custo da linha 4 é s ⋅ O(log n) = O(slog n).

Na linha 5, [Xⁿ + a] pode ser representado por X^{n modr} + a pois [Xⁿ] = [X^{qr+n modn}] = [(X^r)^qX^{n modr}] = [X^{n modr}] (veja (122)). No lado direito da congruência podemos adaptar facilmente o algoritmo 7 para computar (X + a)ⁿ.

_____________________________________________________________________

  1      $P (X ) ← 1$ ;
  2      $n = bℓ− 1... b0$ em binário;
  3     para $k$ de $ell− 1$ até $0$ faça
  4        $P (X ) ← P(X )2$ ;
  5       se   $bk = 1$ então $P (X) ← P (X )(X + a)$ ;
  6        $P (X ) ← P(X ) mod Xr − 1$ ;
  7     devolva( $P (X )$ ).

_____________________________________________________________________

A linha 6 garante que serão O(log n) multiplicações de polinômios de grau < r, e os coeficientes são de tamanho O(log n), portanto, o custo é O(log n)O(r log ²n), ou O(log n)O(r log nlog log n) se usamos transformada rápida de Fourier para multiplicação de polinômios. Falta computar o custo da linha 6. Como P(X) tem grau no máximo r − 1 temos

2r∑−2 r∑−1 r−∑ 2 P (X)2 = ajXj = ajXj + ajXqjr+j modr j=0 j=0 j=r r∑−1 r−∑ 2 = ajXj + aj+rXj (Xr)qj j=0 j=0

como [X^r] = [1], se fizermos a_2r−1 = 0 então podemos escrever [P(X)²] = [∑ _i=0^r−1(a_j+a_j+r)X^j], o custo no lado direito é O(r log n), que corresponde a r somas de coeficientes no ℤ_n. O custo do laço no algoritmo acima é O(r log ²nlog log n) =

(r log ²n). Finalmente, temos que

(sr log ²n) é a contribuição da linha 5 para a complexidade do algoritmo 27.

Finalmente, de (128) resulta a complexidade polinomial para o AKS: (log ¹²n).

O algoritmo 27 um pouco mais refinado fica da seguinte forma.

_____________________________________________________________________

  Dado inteiro $n > 1$
  Devolve $n$ é primo ou é composto.

  1   se $n = ab$ para $a ∈ ℤ+$ e $b > 1$ então devolva(composto);
  2    $r ← 2$ ;
  3   enquanto $r < n$ faça
  4     se $mdc (n,r) ⁄= 1$ então devolva(composto);
  5     se $r$ é primo maior que $2$ então
  6          seja $q$ o maior fator primo de $r − 1$ ;
  7          se $q > 4√rlog n$ e $n (r −1)∕ q ⁄≡ 1 (mod r)$ pára;
  8      $r ← r+ 1$ ;
  9   para $a$ de $1$ até $2√r- log n$ faça
10   se $[(X + a)n] ⁄= [Xn + a]$ no $ℤn[X ]∕(Xr − 1)$ então
             devolva(composto);
11   devolva(primo).

_____________________________________________________________________

Figura 30: Teste de primalidade AKS.

Exercício 108. O seguinte algoritmo aleatorizado “decide” primalidade. Determine em que caso o algoritmo erra e qual é a probabilidade da resposta errada.

_____________________________________________________________________

    Dado inteiro $n$
    Devolve $n$ é primo ou é composto.

    1    $g ← {p(X ) ∈ ℤn[X ]: p ´e m ˆonico de grau log n }$ aleatoriamente;
    2   se $(X + 1)n = Xn +1$ em $ℤn [X ]∕(g)$ então devolva(primo);
    3   senão devolva(composto).

_____________________________________________________________________

Figura 31: Teste de Agrawal–Biswas.

Observação 29. Veja em http://cr.yp.to/papers.html#aks uma exposição de J. Bernstein sobre o AKS e que contém diversas melhorias, inclusive reduzem as constantes envolvidas no tempo por uma fator de pelo menos 2.000.000. Esta é talvez a melhor fonte no momento para estado-da-arte desse algoritmo.

Apêndice A. Exercícios

Exercício 109. Se trocarmos φ(n) por λ(n) no RSA o sistema funcionaria? Justifique. Se a resposta foi sim, tem alguma vantagem ou desvantagem?

Exercício 110. Considere o seguinte algoritmo para n > 2 ímpar

__________________________________________________________________

   $x ← ⌊√n-⌋$ ;
  se $x2 ⁄= n$ então devolva( $x$ );
  repita
     $x ← x + 1$ ;
     $y ← √x2-−-n-$ ;
  até que $y$ seja inteiro ou $x = (n+ 1)∕2$
  se $y$ inteiro então devolva( $x + y$ e $x− y$ );
  se $x = (n+ 1)∕2$ então devolva( $n$ ).

_____________________________________________________________________

Prove que esse algoritmo retorna divisores n.

Exercício 111. Mostre um algoritmo baseado no exercício anterior que se n = pq com p e q primos tais que |p−q|é pequeno então n pode ser fatorado eficientemente.

Exercício 112. No RSA, suponha que Alice mantenha duas chaves privadas ao invés de uma, a saber as chaves d_p = e⁻¹ modp e d_q = e⁻¹ modq. Quando ela recebe uma mensagem cifrada C = M^e modn ela computa M_p = C^d_p modp e M_q = C^d_q modq e usa o Teorema Chinês do resto para determinar x tal que

{ x ≡ Mp (mod p) x ≡ Mq (mod q)

Prove que x ≡ M modn. É possível recuperar M? Esse esquema é mais eficiente que o apresentado em aula?

Exercício 113. Fixado n, sejam d e (e,n) um par de chaves RSA. Suponha que existe um algoritmo polinomial no tamanho da representação de n que decide se e é invertível módulo φ(n) e em caso positivo devolve o inverso. Mostre que existe um algoritmo de tempo log ^O(1)(n) que computa φ(n)

Exercício 114. Suponha que três servidoras A, B e C usam RSA para autenticação de usuário e as chaves públicas são (3,n_A), (3,n_B) e (3,n_C). Suponha que y_A,y_B,y_C possam ser lidos dos arquivos dos sistemas, onde y_m = x³ modn_m (m ∈{A,B,C}). Mostre que se Alice logar nas três máquinas então a senha dela pode ser computada de modo eficiente.

Exercício 115. Escreva um algoritmo que receba dois polinômios f,g ∈ ℤ_p^[X] com g(X)≠0 e devolva q(X),r(X) ∈ ℤ_p[X] tais que

f(X ) = g(X )⋅q(X) +r(X )

(129)

onde r(X) = 0 ou o grau de r(X) é menor que o grau de g(X).

Determine a complexidade do algoritmo.

Exercício 116. Suponha que temos uma fonte de bits aleatórios que devolve 1 com probabilidade p e 0 com probabilidade q = 1 − p, independentemente, onde p≠q. Mostre como obter bits com distribuição uniforme dessa fonte.

Exercício 117. Prove que com probabilidade maior que zero o seguinte algoritmo não pára.

__________________________________________________________________

     $i ← 0$ ;
    repita
       $i ← i+ 1$ ;
       $s ← {0,1}i$ aleatoriamente;
  até que $s = (0,0...,0)$ ;

_____________________________________________________________________

Exercício 118. O objetivo desse exercício é mostrar que se um adversário consegue decifrar 1% das mensagens codificadas com o RSA então ele consegue decifrar todas.

Suponha que E_(e,n)⁻¹ pode ser computada para εφ(n) elementos do ℤ_n^∗ em tempo t. Prove os enunciados a seguir e conclua que existe um algoritmo aleatorizado que computa E_(e,n)(y), para todo y, em tempo esperado t∕ε.

(a) Mostre que se z ←_Rℤ_n^∗ então z, z^e e z^ey são identicamente distribuídos para todo y ∈ ℤ_n^∗.

(b) Suponha A um algoritmo de tempo t para o qual existe Y ⊆ ℤ_n^∗ com εφ(n) elementos tal que A(y)^e = y para todo y ∈ Y . Prove que

Prz← ℤ∗n(v = a(z): ve = z) ≥ ε


(P\|C)	(0\|a)	(1\|a)	(0\|b)	(1\|b)

Pr(P\|C)	1/10	9/10	1/2	1/2

ALGORITMOS EM TEORIA DOS NÚMEROS E CRIPTOGRAFIA DE CHAVE PÚBLICA

Sumário

1. Inteiros

2. Números primos e fatoração

3. Inteiros módulo n

4. Sistemas de congruências

5. Uma hierarquia de estruturas algébricas

6. Polinômios

7. Grupos e subgrupos

8. Raízes primitivas

9. Logaritmo discreto

10. Sistemas criptográficos

11. RSA

12. Rabin

13. Elgamal

14. Assinaturas digitais

15. Primalidade revisitada

16. Teste de Fermat

17. Teste de Miller–Rabin

18. Primos de Mersenne

19. Como gerar de números primos

20. AKS

Apêndice A. Exercícios