Um conceito importante em algoritmos de chave pública e assinatura digital são os logaritmos discretos.Seu entendimento no contexto, passam por conceitos básicos da teoria dos números que descrevemos a seguir.
- Dois números são relativamente primos se não tiverem fatores primos em comum, isto é, se seu máximo divisor comum for 1.
- A função de Euler, Φ (n) é definida como o número de inteiros positivos menores que n, que são relativamente primos com n. Por razões técnicas colocamos Φ(1) = 1.
a) Φ(89) = 88, pois 89 é primo e, consequentemente, os inteiros de 1 à 88 são relativamente primos com 89.
b) Φ(45) = 40, já que 1,2,4,6,7,8,10,11,12,13,14,16,17,18,19,...,44 são os inteiros positivos menores que 45 que são relativamente primos com 45.
- Existe na literatura tabelas para esta função, e se p é primo, então Φ(p) = p-1
- Se p¹q são números primos, então Φ(pq) = Φ(p)Φ(q)=(p-1)(q-1) .
Teorema de Euler : Se t e n são números relativamente primos, então :
tΦ(n) = 1 ( mod n)
- Considere a equação :
tx = 1 ( mod n)
Se t e n são relativamente primos, já sabemos que, x = Φ(n) é solução da equação. O menor valor positivo de x, solução da equação é chamado de ordem de t (mod n) ou extensão do período gerado por t. Para um melhor entendimento deste conceito, veja o exemplo:
71 = 7 ( mod 19)
72 = 11 ( mod 19)
73 = 1 ( mod 19)
74 = 7 ( mod 19)
75 = 11 ( mod 19)
76 = 1 ( mod 19)
Por inspeção na tabela, nota-se que alguns valores de t, gera por otências o conjunto dos inteiros positivos diferente de zero mod 13. Cada um desses inteiros é chamado de raiz primitiva do mod 13. Para o caso, esses números são 2,4,6,10,11. Temos também que, se t é primitiva de n, então:
77 = 7 ( mod 19)
Observamos que, a sequência é periódica de período 3, e neste caso x = 3 é o gerador.Considere agora o primo n = 13 e a tabela :
| t1 | t2 | t3 | t4 | t7 | t6 | t7 | t8 | t9 | t10 | t11 | t12 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 4 | 8 | 3 | 6 | 12 | 11 | 9 | 5 | 10 | 7 | 1 |
| 3 | 9 | 1 | 3 | 9 | 1 | 3 | 9 | 1 | 3 | 9 | 1 |
| 4 | 3 | 12 | 9 | 10 | 1 | 4 | 3 | 12 | 9 | 10 | 1 |
| 5 | 12 | 8 | 1 | 5 | 12 | 8 | 1 | 5 | 12 | 8 | 1 |
| 6 | 10 | 8 | 9 | 2 | 12 | 7 | 3 | 5 | 4 | 11 | 1 |
| 7 | 10 | 5 | 9 | 2 | 1 | 7 | 10 | 5 | 9 | 2 | 1 |
| 8 | 12 | 5 | 1 | 8 | 12 | 5 | 1 | 8 | 12 | 5 | 1 |
| 9 | 3 | 1 | 9 | 3 | 1 | 9 | 3 | 1 | 9 | 3 | 1 |
| 10 | 9 | 12 | 3 | 4 | 1 | 10 | 9 | 12 | 3 | 4 | 1 |
| 11 | 4 | 5 | 3 | 7 | 12 | 2 | 9 | 8 | 10 | 6 | 1 |
| 12 | 1 | 12 | 1 | 12 | 1 | 12 | 1 | 12 | 1 | 12 | 1 |
Por inspeção na tabela, nota-se que alguns valores de t, gera por otências o conjunto dos inteiros positivos diferente de zero mod 13. Cada um desses inteiros é chamado de raiz primitiva do mod 13. Para o caso, esses números são 2,4,6,10,11. Temos também que, se t é primitiva de n, então:
t,t2,t3,...,tΦ(n)
são relativamente primos com p.
A Teoria dos números informa que, os inteiros que tem raízes primitivos são 2,4 e os da forma pk e 2pk onde p é primo maior que 2 e k inteiro positivo.
Considere p primo e t uma raiz primitiva de p. As potências de t de 1 à p-1 tem como valores 1 até p - 1 exatamente uma vez, tomados módulo p. A aritmética modular nos informa que, dado um inteiro b,
b= s mod p, para 0 ≤ s ≤ p -1
Assim, segue-se que para o um inteiro b e t uma raiz primitiva de p, existe um expoente i com
1 ≤ i ≤ p -1, tal que b = ti mod p
definimos o logaritmo discreto de b na base t mod p, como sendo o número i e denota-se por
d logt,p b = i
Existem outras notações para este conceito, e por inspeção na tabela mencionada neste texto,podemos escrever
Este cálculo consiste em resolver o problema : " Dados os números b, t e p primo, encontrar x tal que , b = tx mod p "
exp[(ln p)1/3(ln (ln p)2/3]
são relativamente primos com n. Em particular, se n = p, então :
t,t2,t3,...,tp-1
são relativamente primos com p.
A Teoria dos números informa que, os inteiros que tem raízes primitivos são 2,4 e os da forma pk e 2pk onde p é primo maior que 2 e k inteiro positivo.
O Logaritmo discreto para números primos (interesse criptográfico)
Considere p primo e t uma raiz primitiva de p. As potências de t de 1 à p-1 tem como valores 1 até p - 1 exatamente uma vez, tomados módulo p. A aritmética modular nos informa que, dado um inteiro b,
b= s mod p, para 0 ≤ s ≤ p -1
1 ≤ i ≤ p -1, tal que b = ti mod p
d logt,p b = i
d log11,13 25 = 6
d log2,13 14 = 12
Cálculo do logaritmo discreto
Este cálculo consiste em resolver o problema : " Dados os números b, t e p primo, encontrar x tal que , b = tx mod p "
A dificuldade em resolver este equação para p primo com muitos digitos, apresentada por um algoritmo considerado rápido, é da ordem de :
exp[(ln p)1/3(ln (ln p)2/3]
o que torna-se inviável o tratamento computacional.
Lembre-se que, todo sistema criptográfico é baseado em um problema matemático que é intratável computacionalmente.
Fonte: STALLINGS, William. Criptografia e Segurança de Redes. São Paulo : Pearson Educations, 2008.
