|
|
|
Análise do protocolo |
O matemático "Leonhard Euler" observou que se tivermos dois números primos entre si, x e n, e se começarmos a multiplicar x por ele próprio módulo n várias vezes, alcançaremos o resultado 1 em alguma operação e na multiplicação seguinte por x começaremos de novo com o resultado inicial, x. Assim, para todos os números x primos a n, existe um período Phi(x) de modo a que xPhi(n) = 1 mod(n). Esse número Phi(x), para todos os números é igual ao numero de inteiros menores ou iguais a x que são primos com x.
Euler também descreveu que se x é primo, então Phi(x) = x-1. Isto significa que para qualquer x primo relativo de n, todos os valores ate x são primos relativamente a x e temos xx-1 mod n = 1.
Por exemplo, para n = x = 7, os números 1, 2, 3, 4, 5, e 6 são primos relativos a 7, logo Phi(7) = 6 e 76 mod 7 = 1.
No sistema RSA, temos que n = p*q, com p e q primos. Então Phi(n) é o número de inteiros menores ou iguais a n que não têm p ou q como factor.
Podemos tirar proveito desta prova no teorema apresentado em: [Joh03].
|
|
|
Análise do protocolo |