Software de Telecomunicações
Teoria dos números
Prof RG Crespo
Software de Telecomunicações
Teoria números : 1/37
Números primos (1)
O conjunto dos inteiros {...,-2,-1,0,1,2,...} é representado por
ℤ.
Definição: A divisão de a por b (b≥1), a/b, é um par (q,r) tal
que a = q.b+r (q é designado por quociente, r por resto).
b é divisível por a, a|b, sse o resto de a/b for 0 (ex: 3|9)
Nota: A soma e a subtração de dois inteiros é O(log n), o
produto e a divisão de dois inteiros é O(log2n).
Definição: um número p é primo sse existirem apenas dois
divisores (1|p e p|p).
Ex: são primos 1,2,3,5,7,11,13,17,19,…
Prof RG Crespo
Software de Telecomunicações
Teoria números : 2/37
Números primos (2)
Teorema fundamental da aritmética: Qualquer número n
pode ser representado por um produto de números primos.
Ex: 4200 = 23.3.52.7, 10780=22.5.72
2113 - 1= 3391.23279.65993.1868569.1066818132868207
Definição: O maior divisor comum de dois números a b,
gcd(a,b) é o maior inteiro d tal que d|a e d|b.
Basta factorizar os dois números e tomar os primos
comuns com o menor dos expoentes.
Ex: gcd(4200,10780) = 22.5.7 = 140
Prof RG Crespo
Software de Telecomunicações
Teoria números : 3/37
Números primos (3)
Nota1: gcd(a,b)=gcd(b,a).
Nota2: factorização de números é operação custosa
– 1994: a aplicação do QS-Quadratic Sieve distribuída por 1600
computadores conseguiu factorizar número RSA-129 em 8
meses.
– 2005: factorizado número RSA-560.
Definição: Dois números a b são primos entre si, sse
gcd(a,b)=1. Afirma-se que a é co-primo de b.
Ex: 26 e 15 não são primos, mas são primos entre si.
Prof RG Crespo
Software de Telecomunicações
Teoria números : 4/37
Números primos (4)
Algoritmo de Euclides (determina gcd(a,b) sem cálculo da
factorização)
1. Para calcular gcd(a,b), calcular a divisão do maior número pelo menor: a
= q.b+r
2. Se r≠0, voltar ao passo 1 e calcular gcd(r,b).
Se r=0, gcd(a,b) = b
Algoritmo de Euclides é O(log3n)- log n divisões * O(log2n) cada divisão
Ex: Determinar gcd(1547,560)
1547
560
427
133
28
21
=
=
=
=
=
=
2.560 + 427
1.427 + 133
3.133 + 28
4.28 + 21
1.21 + 7
3.7 + 0
Prof RG Crespo
calcular gcd(427,560)
calcular gcd(427,133)
calcular gcd(28,133)
calcular gcd(28,21)
calcular gcd(7,21)
gcd(1547,560)=7
Software de Telecomunicações
por multiplicação
russa
Teoria números : 5/37
Números primos (5)
Proposição: Se d = gcd(a,b), existem dois números u e v tais que
d=ua+vb: para calcular u,v basta inverter o algoritmo de Euclides,
substituindo os restos pelas igualdades anteriores.
Ex:7 = 28 – 1.21 =
28 –1.(133-4.28) ↔ 5.28 - 1.133 =
5.(427 – 3.133) – 1.133 ↔ 5. 427 – 16.133 =
5. 427 – 16.(560 – 1.427) ↔ 21.427 – 16.560 =
21.(1547 – 2.560) – 16.560 ↔ 21. 1547 – 58.560
Nota: a proposição permite facilmente calcular o inverso de um
número módulo M, se M for primo.
1 = gcd(a,M) = ua+bM: logo, a-1 mod M = u.
Prof RG Crespo
Software de Telecomunicações
Teoria números : 6/37
Números primos (6)
Algoritmo estendido de Euclides:determina triplo (d,x,y) tal
que ax+My=d: se d=1, então x=a-1 mod M.
Função Euclides-estendido(a,b)
se b=0 retornar (a,1,0);
k := a/b;
r := a mod b;
(d,x,y) := Euclides-estendido(b,r);
retornar (d,y,x-ky);
Prof RG Crespo
Software de Telecomunicações
Teoria números : 7/37
Números primos (7)
Exemplo: determinar 123-1 mod 1003
•
a
b
k
r
Retorna
1003
123
8
19
(1,13,-106)
123
19
6
9
(1,-2,13)
19
9
2
1
(1,1,-2)
9
1
9
0
(1,0,1)
1
0
-
-
(1,1,0)
123-1 mod 1003 ≡ -106 ≡ 897
Prof RG Crespo
Software de Telecomunicações
Teoria números : 8/37
Números primos (8)
Definição: A função Euler totient, ϕ(n) = #{0≤b<n |
gcd(b,n)=1} indica o número de todos os valores coprimos de n.
– ϕ(1) = 1
– ϕ(p) = p-1, para todos os primos de p
– se n=pq (p,q primos), então ϕ(n) = (p-1)(q-1)
Proposição: Se a for primo relativo de n, então
aϕ(n) = 1 mod n
Prof RG Crespo
Software de Telecomunicações
Teoria números : 9/37
Números primos (9)
Definição: A função π(n) indica o número de primos
menores que n.
Os primos até 25 são: 2, 3, 5, 7, 11, 13, 17, 19 e 23.
Logo, π(3) = 2, π(10) = 4, π(25) = 9.
Teorema números primos: π(n) é da ordem de n/(ln n – a),
com a ≅ 1.
Nota: há zonas em que os primos estão mais concentrados
(ex: 1_000_000_000_061, 1_000_000_000_063) e noutras mais
dispersos.
Prof RG Crespo
Software de Telecomunicações
Teoria números : 10/37
Números primos (10)
Consequência 1: há muitos números primos por onde
escolher!
Ex: π(1020) ∈ O(1020 /19) ≅ 5.2 *1018 (na realidade,
π(1020) = 2 220 819 602 560 918 840 ≅ 2.2 *1018 ) .
Consequência 2: a procura de um primo não é muito pesada.
Em média, os números primos estão afastados O(ln n):
como os pares e múltiplos de 5 não contam, a procura é
0.4 * ln n
Ex: para procurar um primo à volta de 2200 (200 dígitos
binários), devem ser necessários 0.4(ln 2200)=55 testes.
Prof RG Crespo
Software de Telecomunicações
Teoria números : 11/37
Números primos (11)
• Computação distribuída
permite determinar
números primos cada
vez maiores.
• O maior número primo,
identificado em Agosto
2008, é 243,112,609 -1 com
12_978_189 dígitos
decimais.
Nota: Os primos Mersenne possuem a forma 2n-1, sendo
conhecidos 49 (31= 25-1 é primo, mas 2047 = 211-1 não é
primo).
Prof RG Crespo
Software de Telecomunicações
Teoria números : 12/37
Primalidade (1)
Como escolher um número primo?
A. Por aproximação Hardly e Wright, procurar nos valores próximos
prime(n) ∼ n(log n+log log n –1)
Ex: prime(106) ∼ 15 400 000: na realidade é 15 485 863.
Impraticável: para n elevado a distância entre dois primos é O(log n)
e determinar se número é primo custa!
B. Gerar um número aleatório n ímpar, n≠5 e verificar se é primo
com um teste de primalidade (ex, Rabin-Miller). Se não for,
procurar à volta de lg N. Se não conseguir encontrar, gerar novo
número aleatório e procurar nessa zona.
Esta é a estratégia usada na cifra RSA para gerar números
aleatórios de grande dimensão.
Prof RG Crespo
Software de Telecomunicações
Teoria números : 13/37
Primalidade (2)
Peneira de Eratosthenes (“sieve”)
– Descoberto em 250 AC
– Método determinista, mas pouco eficiente para números de grande
dimensão.
1.
2.
3.
4.
Escrever todos os números de 2 an-1.
Fazer d←2 (primeiro primo).
Se n não for divisível por d, eliminar da lista todos os múltiplos
de d.
Se a lista não estiver vazia, d←primo seguinte e regressar a 3.
Se a lista estiver vazia, n é primo
Prof RG Crespo
Software de Telecomunicações
Teoria números : 14/37
Primalidade (3)
[Exemplo] Seja n=17
– Lista: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
d←2: 17 não é divisível por 2!
Eliminados múltiplos de 2 (2 4 6 8 10 12 14 16)
– Lista: 3 5 7 9 11 13 15
d←3: 17 não é divisível por 3!
Eliminados múltiplos de 3 (3 9)
– Lista: 5 7 11 13 15
d←5: 17 não é divisível por 5!
Eliminados múltiplos de 5 (5 15)
– Lista: 7 11 13
d←7: 17 não é divisível por 7!
Eliminados múltiplos de 7 (7)
– ...
Prof RG Crespo
Software de Telecomunicações
Teoria números : 15/37
Primalidade (4)
Teste de Rabin-Miller
1. Calcular k,m (ímpar) tal que n-1= m.2k.
Nota: O cálculo é rápido: deslocar para a direita enquanto a divisão for
par, k é o número de deslocamentos, m é a divisão ímpar.
2. Seleccionar base, tal que 1 ≤ b < n.
3. a ← bm mod n
i.
ii.
Se a=n-1, então n pode ser primo.
Se algum dos valores a2 mod n, a4 mod n, …, a2^(k-1) mod n for igual n-1,
então n pode ser primo.
iii. Se falhar 3.1 e 3.2, então n não é primo.
•
•
Se o número for candidato a primo, efectuar o teste normal
Nota: pode revelar que, afinal, não é primo!
Para números não primos, ¾ dos valores de a acabam no ponto 3.3
Prof RG Crespo
Software de Telecomunicações
Teoria números : 16/37
Primalidade (5)
Exemplo: Vejamos se n=29 é primo
1. 28 = 14.2 = 7 . 22
2. Seleccionar base b=10
3. a ← 107 mod 29 ≡ 17
1. a ≠ 28
2. (107 )2 mod 29 ≡ 28. Pode ser primo (na realidade é!)
Exemplo: Vejamos se n=221 é primo
1. 220 = 110.2 = 55 . 22
2. Seleccionar base b=5
3. a ← 555 mod 221 ≡ 112
1. a ≠ 220
2. (555 )2 mod 221 ≡ 168≠ 220 (nota: como k=2, não existem mais testes)
3. Conclui-se que 221 não é primo (nota: factorizando, tem-se 221=13*17)
Prof RG Crespo
Software de Telecomunicações
Teoria números : 17/37
Primalidade (6)
Teorema pequeno de Fermat (“Fermat Little Theorem”): Se p
é co-primo de a, então ap-1=1 mod p.
Ex: 7 e 3 são co-primos, pelo que 72=1 mod 3.
Igualmente, 390=1 mod 91 [nota: 91 não é primo]
Os números (a,p) são designados pseudo-primos.
Prof RG Crespo
Software de Telecomunicações
Teoria números : 18/37
Congruência (1)
Definição: a é congruente a b módulo M, a≡b mod M, sse
(a–b)|M. M é designado módulo da congruência.
Ex: 17 ≡ 4 mod 26, porque 13|26.
– Os números ZM={0,1,…,M-1} formam um anel de inteiros
módulo M com operadores +,* módulo M.
– Frequentemente, a≡b mod M é representado por a=b modM
• A aritmética modular foi explorada em primeiro lugar por
Gauss.
• A relação de congruência é fundamental na cifra, uma vez
que todas as alterações não devem sair do alfabeto a cifrar/
decifrar.
Prof RG Crespo
Software de Telecomunicações
Teoria números : 19/37
Congruência (2)
• As congruências, com o mesmo módulo, podem ser
somadas / subtraídas ou multiplicadas.
Se a≡b mod M e c≡d mod M, então a±c≡b±d mod M e
ac≡bd mod M.
Ex: 3 = 3 mod 9, 4 = 4 mod 9, logo 3+4 = 7 mod 9
3 = 3 mod 9, 8 = 8 mod 9, logo 3+8 = 2 mod 9
• O zero é elemento neutro da adição.
x+0≡x mod M ≡ 0+x mod M
Prof RG Crespo
Software de Telecomunicações
Teoria números : 20/37
Congruência (3)
Tal como em Z, os aneis ZM possuem inversos aditivos.
Definição: Um inverso aditivo módulo M de a é um valor b
tal que a+b =1 mod M.
Teorema: para cada elemento de um anel ZM, existe um e só
um inverso aditivo.
Ex: 3+6=0 mod 9, logo 6 é inverso aditivo de 3 módulo 9.
Prof RG Crespo
Software de Telecomunicações
Teoria números : 21/37
Congruência (4)
Ao contrário de Z, os aneis ZM possuem inversos
multiplicativos para alguns elementos (não todos!).
Definição: Um inverso multiplicativo módulo M de a, a-1
mod M, é um valor tal que aa-1 =1 mod M.
• A condição pode ser refeita para aa-1 = 1 + Mk, que tem
uma única solução se a e M forem primos entre si (ou seja,
gcd(a,M)=1). Se a M forem primos entre si, para
identificar a-1, basta refazer a igualdade gcd(a,M)=1
1. Determinar os numeros u,v tal que 1 = uM + va
2. a-1 = v
Prof RG Crespo
Software de Telecomunicações
Teoria números : 22/37
Congruência (5)
Ex: Calcular 160-1 mod 839
839 = 5.160 + 39
160 = 4.39 + 4
39 = 9.4 + 3
4 = 1.3 + 1
1 =
=
=
=
4–1.3
4–1.(39-9.4)↔ 10.4-1.39
10.(160-4.39)-1.39 ↔ 10.160-41.39
10.160-41.(839-5.160) ↔ 215.160-41.839
Logo, 160-1 mod 839 = 215
Verificação: 160*215 = 35400 = 1 mod 839
Prof RG Crespo
Software de Telecomunicações
35400
839
-35399
1
41
Teoria números : 23/37
Congruência (6)
Teorema: Num anel ZP todos os elementos não nulos
possuem inverso multiplicativo, sse P for primo.
Prova: pela definição de inverso multiplicativo, aa-1 = 1 + Pk
que tem solução sse a,P forem co-primos. Se todos os
elementos não nulos de ZP forem co-primos, então P é
primo.
Corrolário: a/b em ZP é dada por ab-1 mod P
Ex: 37/160 mod 839 = 37*160-1 = 37*215= 7955 mod 839 =
404
Prof RG Crespo
Software de Telecomunicações
Teoria números : 24/37
Congruência (7)
Definição: a soma módulo 2, a ⊕ b , resulta 1 sse os operandos forem
distintos.
a ⊕ b = a+b mod 2
Propriedades: para quaisquer a,k
– a⊕a=0
– a⊕k⊕k=a
Prof RG Crespo
A
B
A⊕ B
0
0
0
0
1
1
1
0
1
1
1
0
Software de Telecomunicações
Teoria números : 25/37
Eficiência de operações RSA (1)
A grande dimensão dos blocos RSA levou à criação de
bibliotecas de operações.
i.
Produto
Pretende-se avaliar x.y, com valores na ordem 21024≈10308. Cálculo
pelo método matricial (proposto pela primeira vez por Fibonnaci) é
muito ineficiente.
Alternativa: multiplicação russa, com “shift” e somas.
1.
2.
3.
Enquanto y≠1 executar e colocar lado a lado x=2.x e y=y/2
Cortar todos os xi para yi pares
Somar todos os xi para yi ímpares
Complexidade: O(log2n)- log n somas * O(log n) cada soma
Prof RG Crespo
Software de Telecomunicações
Teoria números : 26/37
Eficiência de operações RSA (2)
Exemplo: Cálculo de 52 * 37
multiplicação
matricial
russa
52
104
208
416
832
1664
1924
52
*37
364
156
1924
Prof RG Crespo
Software de Telecomunicações
37
18
9
4
2
1
Teoria números : 27/37
Eficiência de operações RSA (3)
ii. Exponenciação módulo M
Cálcular xc e só depois calcular xcmod N gera valores de dimensão
muito elevada.
Alternativa: em cada multiplicação por x, calcular o módulo para
reduzir os valores intermédios. Exponenciação pode ser efectuada da
esquerda para a direita (solução adoptada aqui), ou da direita para a
esquerda.
1. Representar c = bk-1 … b0
2. Executar algoritmo
z = 1;
for ( i=k-1; i>=0; i-- ) {
if ( bi=1 ) mult=x else mult=1;
z = z2.mult mod N;}
Prof RG Crespo
Software de Telecomunicações
Teoria números : 28/37
Eficiência de operações RSA (4)
Ex: Cálculo de 3037 mod 77 (37 = 100101)
1.
2.
3.
4.
5.
6.
7.
z=1
i = 5; b5=1 ∴ mult= 30;
i = 4; b4=0 ∴ mult= 1;
i = 3; b3=0 ∴ mult= 1;
i = 2; b2=1 ∴ mult= 30;
i = 1; b1=0 ∴ mult= 1;
i = 0; b0=1 ∴ mult= 30;
z = 12 * 30 mod 77 ≡ 30
z = 302 mod 77 ≡ 53
z = 532 mod 77 ≡ 37
z = 372 * 30 mod 77 ≡ 29
z = 292 mod 77 ≡ 71
z = 712 * 30 mod 77 ≡ 2
Complexidade O(lg3n)
Nota: Ataque DPA (“Differential Power Analysis”) baseado
na análise das variações no consumo de energia durante o
cálculo de mult*z dentro do ciclo for.
Prof RG Crespo
Software de Telecomunicações
Teoria números : 29/37
Eficiência de operações RSA (5)
1
xc mod N em hardware
x
z
Lógica
controlo
c
mult mod N
Prof RG Crespo
Software de Telecomunicações
Teoria números : 30/37
Eficiência de operações RSA (6)
iii. Decifra RSA
Decifra mais eficiente com auxílio do CRT
Teorema Chinês dos Restos (CRT-Chinese Remainder
Theorem): Seja N=n1*n2*…*nr com ni,nj (i≠j) coprimos.
–
Qualquer A∈[0,(N-1)] é representado por
(a1=A mod n1, a2=A mod n2, …, ar=A mod nr)
– r A calculado, a partir de (a1, a2,…, ar), pela seguinte equação:
A = ∑ (ai N i N i−1 mod ni ) mod N
i =1
Ni =
N
= n1n2 L ni −1ni +1 L nr
ni
Prof RG Crespo
Software de Telecomunicações
Teoria números : 31/37
Eficiência de operações RSA (7)
Exemplo: Sun-Tsu inicia batalha com 208 soldados e no final
pretende determinar rapidamente os sobreviventes.
Verifica que os sobreviventes
– agrupados em 3, sobram 2 (a1 = A mod 3 ≡ 2)
– agrupados em 5, sobram 3 (a2 = A mod 5 ≡ 3)
– agrupados em 7, sobram 2 (a2 = A mod 7 ≡ 2)
a) N1=5.7=35; N2=3.7=21; N3=3.5=15
b) 35-1 mod 3 = 2, 21-1 mod 5 = 1, 15-1 mod 7 = 1
c) A=2.35.2 + 3.21.1 + 2.15.1 (mod 3.5.7) = 23 mod 105.
Sun-Tsu ou tem 23 ou tem 128 soldados.
Nota: fácil verificar sem ter de agrupar em 11!
Prof RG Crespo
Software de Telecomunicações
Teoria números : 32/37
Eficiência de operações RSA (8)
Por ser o único com acesso a p,q o proprietário pode calcular
mais rapidamente M=Cd mod N,
1. Na construção da cifra RSA tem-se N=pq. Calcular
Cp = C mod p
Cq = C mod q
d p = d mod(p −1)
d q = d mod(q − 1)
d
M q = Cq q mod q
M p = Cp p mod p
d
2. Decifrar mensagem a partir dos resíduos
M = ( M p Rq + M q R p ) mod N
R p = ( p −1 mod q) ⋅ p = p q −1 mod N
Rq = (q −1 mod p) ⋅ q = q p −1 mod N
Prof RG Crespo
Software de Telecomunicações
Teoria números : 33/37
Números aleatórios (1)
Definição: O período de uma sequência é valor mínimo de τ,
tal que s(i+τ)=s(i), para todos 0≤ i<N-τ
Ex: a sequência 010 010 01, de comprimento p=8, possui
período 3.
Definição: Um bloco (“block”) é uma sequência contínua de
1’s e um salto (“gap”) é uma sequência contínua de 0’s.
Uma corrida (“run”) é um bloco ou um salto.
Existem diversos métodos para determinar o grau de
confinação de uma sequência binária pseudo-aleatória
– Princípio de Golomb
– Testes estatísticos (frequência, “poker”, corridas,…)
Prof RG Crespo
Software de Telecomunicações
Teoria números : 34/37
Números aleatórios (2)
Testes estatísticos
– Teste série: as frequências das transições 00, 01, 10, 11 são iguais.
– Teste “poker”: dividir sequência por subsequências com mesmo
número de bits (m≥3)-denominados “poker hands”, e comparar a
distribuição dos valores com o teste χ2.
Princípios de Golomb: primeira tentativa para identificar as
condições necessárias, mas não suficientes!
1. A diferença entre o número de 0’s e 1’s deve ser tão pequena
quanto possível.
Nota: na sequência 101010101010101010101010101010101010,
diferença entre 0’s e 1’s é nula, mas não é aleatória (tal será
detectado pelo terceiro princípio de Golomb).
Prof RG Crespo
Software de Telecomunicações
Teoria números : 35/37
Números aleatórios (3)
2. Em todas as subsequências, metade das corridas são blocos e a
outra metade são saltos.
A frequência de corridas de comprimento i é, pelo menos, (½)i se
o número de corridas for superior a 1; metade das corridas tem
comprimento 1, um quarto das corridas tem comprimento 2,…
Ex: seja 00001100001110001111100001110001101110000100.
À primeira vista a sequência parece ser aleatória, mas não
obedece aos critérios de Golomb.
Comprimento
Blocos
Saltos
Corridas
1
19
25
44 (46%)
2
12
17
29 (30%)
3
6
10
16 (17%)
4
2
4
6 (6%)
5
1
0
1 (1%)
Prof RG Crespo
Software de Telecomunicações
Falha!
Teoria números : 36/37
Números aleatórios (3)
3.
Autocorrelação é de 2 valores
N .C (t ) =
C (t ) =
{KN ,, sese 1t ≤= t0≤ N -1
1 N −1
∑ (2 si − 1)(2 si +t − 1), 0 ≤ t ≤ N − 1
i
N =0
Ex: 011001000111101, gerada pelo LFSR de polinómio conectivo
x4+x3+1, satisfaz os critérios de Golomb.
1.
2.
Número de 0’s é 7, número de 1’s é 8.
Existem 8 corridas:
•
•
•
3.
4 corridas de comprimento 1 (2 saltos, 2 blocos).
2 corridas de comprimento 2 (1 salto, 1 bloco).
1 salto de comprimento 3, 1 bloco de comprimento 4.
C(0)=1, C(t)=-1/15 for 1 ≤ t ≤ 14
Nota: existem bons testes estatísticos, como Diehard
Prof RG Crespo
Software de Telecomunicações
Teoria números : 37/37