matemática computacional pt2

Prévia do material em texto

MATEMÁTICA 
COMPUTACIONAL 
AULA 6 
 
 
 
 
 
 
 
 
 
Prof. Luis Gonzaga de Paulo 
 
 
 
 
2 
 
CONVERSA INICIAL 
O uso da matemática na solução de problemas computacionais requer o 
conhecimento de diversos tipos de operações, fórmulas, teoremas e métodos 
de cálculos desenvolvidos ao longo da história da civilização. Alguns desses 
conhecimentos são milenares, e foram aperfeiçoados com o passar do tempo, 
derivando-se em outros ou servindo de base para novas formas de solução. 
Nesta aula, vamos abordar alguns temas da teoria dos números, que são 
cruciais para o desenvolvimento de soluções computacionais com o uso da 
matemática em áreas como a Criptografia, robótica, automação, inteligência 
artificial, entre tantas outras. O aprendizado desses conteúdos é fundamental, e 
depende muito da prática, da exercitação, o que poderá ser feito com o apoio 
dos cadernos de exercícios e das aulas práticas. Boa aula! 
TEMA 1 – ARITMÉTICA MODULAR 
Seja um número n inteiro e positivo, que faz parte de um conjunto {0,...,n-
1}, o qual representamos como ℤn. Podemos considerar que dois inteiros desse 
conjunto, x e y, são os mesmos se x e y diferem por um múltiplo de n, o que 
escrevemos assim: 
x = y (mod n) 
E dizemos que x e y são congruentes módulo n. Quando o mod n está 
claramente definido pelo contexto, então pode ser omitido. Todo inteiro x é 
congruente para determinados y em ℤn. Quando somamos ou subtraímos 
múltiplos de n de um inteiro x para determinar y ∈ ℤn, então dizemos que 
estamos reduzindo x módulo n e y é o resto (ou residual). 
Podemos ter escolhido diferentes conjuntos para ℤn, por exemplo, 
podemos adicionar n para cada elemento, mas o nosso padrão será (0, ..., n – 
1}. Os elementos desta representação em particular são denominados restos (ou 
resíduos) menores. Exemplos: 
38 = 3 (mod 5), pois 38 = 7 x 5 + 3 
-3 = 11 (mod 14), pois -3 = (-1) x 14 +11 
 
 
3 
A aritmética com elementos de ℤn é a mais natural possível. Dados dois 
elementos x e y ∈ ℤn podemos realizar somas, subtrações e multiplicações e o 
resultado será congruente com um elemento de ℤn., como nos exemplos a 
seguir: 
6 + 7 = 1 (mod 12) 
3 x 20 = 10 (mod 50) 
12 – 14 = 16 (mod 18) 
Essas operações se comportam de maneira semelhante às operações 
corriqueiras com inteiros. Entretanto não há nenhuma noção de grandeza ou 
proporção. Por exemplo, 0 < 4 (mod 8) é algo que não faz sentido, uma vez que 
basta somar 4 aos dois lados da expressão e encontramos 4 < 0 (mod 8). Os 
inteiros regulares são vistos como se estivessem em uma linha numérica, na 
qual os números inteiros à esquerda são menores que inteiros à direita. Inteiros 
módulo n, no entanto, são vistos como se estivessem em um círculo: ao 
trabalhar com o módulo 12, pense nos números do mostrador de um relógio. 
A divisão, porém, é um caso à parte, posto que está fora dessa 
constatação. Se y divide x como inteiro, poderíamos supor que podemos usar a 
definição típica. Vejamos então: temos que 10 = 4 (mod 6). Se dividirmos ambos 
os lados da equação por 2, teremos uma equação incorreta: 5 = 2 (mod 6). 
Assim, temos que mudar o significado da divisão. Intuitivamente, a divisão deve 
"desfazer multiplicação", isto é, dividir x por y significa encontrar um número z, 
de tal modo que y vezes z resulta em x. O problema é que existem diferentes 
candidatos para z em ℤn para ambos - 5 e 2 - que resultam em módulo 4, quando 
são multiplicados por 2. 
Então qual resposta devemos escolher para “4/2”, 5 ou 2? Com os 
números reais, embora sempre haja duas raízes quadradas de um real positivo, 
ainda podemos definir o símbolo da raiz quadrada, porque estipulamos que ele 
se refere à raiz quadrada positiva. Porém sem uma noção de grandeza, não 
podemos afirmar "escolha a menor resposta". Existem maneiras de escolher 
uma resposta única, por exemplo, podemos escolher a menor resposta ao 
considerar o mínimo de resto como um inteiro, mas a divisão se comportará de 
maneira estranha. 
 
 
4 
Por isso, precisamos de unicidade, isto é, x dividido por y módulo n só é 
definido quando existe um z ∈ ℤn único, tal que x = yz. Podemos obter uma 
condição em y da seguinte maneira: Suponha z1y = z2y (mod n). Então, por 
definição, isso significa que, para alguns k, temos y (z1 − z2) = kn. Seja d o MDC 
- máximo divisor comum de n e y. Então n / d divide z1 − z2, uma vez que não 
pode dividir y, portanto, temos: 
z1y = z2y (mod n) 
se e somente se: 
z1y = z2 (mod n/d) 
Verificamos que um único z existe se e somente se é possível encontrar 
um w ∈ ℤn tal que yw = 1 (mod n). Se esse w existe, ele deve ser único: 
suponhamos que yw’ é também 1. Então multiplicando ambos os lados de yw = 
yw’ temos wyw = wyw’, o que implica que w = w’ uma vez que yw = 1. Quando 
isso ocorre, nós denominamos este único w o inverso de y, expresso por y-1. 
Mas o que podemos questionar é: como sabemos que y-1 existe? E, nesse 
caso, como podemos encontrá-lo? Uma vez que existam apenas n elementos 
em ℤn podemos multiplicar cada elemento por y e verificar se resulta em 1. 
Caso esse resultado não seja obtido, concluímos que y não tem um 
inverso. De certa forma, a aritmética modular é mais fácil do que a aritmética 
com inteiros, posto que existem apenas muitos elementos finitos. Então, para 
encontrar uma solução de um problema, podemos sempre tentar todas as 
possibilidades. Agora temos uma boa definição para divisão: x dividido por y é x 
multiplicado por y-1, se o inverso de y existe. Caso contrário a resposta é 
indefinida. 
Para evitar confusão com a divisão de números inteiros, é comum evitar 
o uso da barra “/” como símbolo de divisão na aritmética modular: para expressar 
a divisão de x por y escreve-se xy-1. Como exemplo, temos a seguinte equação: 
2 x 3 + 4(5-1) = 2 (mod 6) 
TEMA 2 – ALGORITMO DE EUCLIDES 
O algoritmo de Euclides é uma forma eficiente e simples para encontrar o 
MDC para dois inteiros diferentes de zero, sem exigir a fatoração. É um dos mais 
 
 
5 
antigos algoritmos conhecidos, e faz parte dos livros VII e X da obra Elementos 
do filósofo e matemático grego Euclides, escritos por volta de 300 a.C. Este 
algoritmo tem vasta aplicação nas mais diversas áreas, e é usado em grande 
parte de importantes aplicações, sendo um elemento-chave do método de 
criptografia de chave pública usado no comércio eletrônico, o algoritmo RSA. 
O ponto central desse algoritmo é a constatação de que um MDC – 
Máximo Divisor Comum pode ser calculado de forma recursiva. O resto da 
divisão na primeira entrada é usado no passo seguinte, até que o resto seja zero. 
Formulando essa definição temos: 
mdc (x, y) = mdc (y, r) 
Onde r é o resto da divisão de x por y. Como podemos ver, denotamos o 
máximo divisor comum de x e y como sendo mdc (x, y) ou, às vezes, somente 
como (x, y). E se mdc (x, y) = 1 dizemos que x e y são coprimos ou 
relativamente primos. Mas como encontramos o resultado de mdc (x, y)? A 
resposta óbvia é: relacionamos todos os divisores de x, y e identificamos o maior 
divisor que eles têm em comum. No entanto, isso requer que x, y sejam 
fatorados, e ainda não sabemos como fazer isso de forma eficiente e rápida. 
Porém, para refinar essa pergunta, podemos considerar que, dados três inteiros 
a, b, c, podemos definir c no formato 
c = ax + by 
para os inteiros x e y? Pode haver mais de uma solução? Podemos encontrar 
todas? Antes de responder isso, vamos responder a uma pergunta 
aparentemente não relacionada: Como encontramos o máximo divisor comum 
(mdc) de dois inteiros a, b? 
Curiosamente algumas observações simples levaram à forma superior do 
algoritmo de Euclides, ou algoritmo euclidiano. Primeiro, se d divide x e d divide 
y então d divide também a soma de x e y. De modo semelhante, divide também 
a diferença entre eles, (x – y), considerando que x é o maior dos dois números. 
E isso significa que diminuímos o tamanho do problema inicial. Agora só 
precisamoscalcular mdc (x, x – y), e o processo pode repetir-se até zerar o 
resto, e obter o resultado. 
Podemos, então, calcular o mdc (x, y) usando a divisão e o resto, como 
aprendemos no primário. Vamos ao exemplo: calcular o mdc (27, 33): 
1. Primeiro dividimos o maior número pelo menor: 33 = 1 x 27 + 6; 
 
 
6 
2. Então temos que mdc (27, 33) = mdc (27, 6); 
3. Repetimos o processo: 27 = 4 x 6 + 3; 
4. Então temos que mdc (27, 6) = mdc (6, 3); 
5. E, finalmente, 6 = 2 x 3 + 0 
6. Como 6 é um múltiplo de 3, então temos que mdc (6, 3) = 3, e por 
conseguinte, mdc (27, 6) = 3; 
Esse algoritmo não requer a fatoração dos números, e é bastante rápido. 
Obtemos uma redução brutal de etapas necessárias verificando que, se 
dividirmos x por y para encontrar x = yq + r, e r > y /2, então no próximo passo 
obtemos r’ ≤ y / 2. Desse modo, em um ambiente computacional, a cada dois 
passos os números diminuem em pelo menos um bit de tamanho! 
As equações que estudamos permitem calcular mais do que o mdc de 
dois números. Nós podemos usar essas equações para encontrar os inteiros m 
e n que façam correta a equação: 
3 = 33m + 27n 
Primeiro reorganizamos as equações para que os restos fiquem em 
evidência: 
6 = 33 – 1 x 27 
3 = 27 - 4 x 6 
A partir da última equação substituímos os valores com base na anterior, 
como segue: 
3 = 27 - 4 x (33 – 1 x 27)  (-4) x 33 + 5 x 27) 
E chegamos, então, a m =-4 e n=5. Se houvessem mais equações, 
repetiríamos o processo até usarmos todas elas para encontrar m e n. De um 
modo em geral, dados dois inteiros a e b, seja d = mdc (a, b). Então podemos 
encontrar inteiros m e n tais que 
d = ma + nb 
usando o algoritmo euclidiano estendido. Agora podemos responder à questão 
colocada lá no início, isto é, dado inteiros a, b, c encontrar todos os inteiros x, y 
tais que: 
c = ax + by 
 
 
7 
Seja d = mdc (a, b). Desde que ax + by seja múltiplo de d para quaisquer 
inteiros (x, y), existem soluções apenas quando d divide c. Então digamos que 
c = kd. Usando o algoritmo euclidiano estendido podemos encontrar m, n tal que 
d = ma + nb, e então teremos a solução x = km, y = kn. Supondo que x’ e y’ 
seja outra solução, então 
c=xa+yb = x′a+y′b 
Reorganizando essa equação, teremos: 
(x’ – x) a = (y – y’) b 
Uma vez que d é o mdc, então b/d não divide a. Porém deve dividir a 
expressão do lado direito, já que o b consta dela. Então (x’ – x) é um múltiplo de 
b/d, ou seja: 
(x’ – x) = tb / d 
para algum inteiro t. Resolvendo a expressão (y’ – y) dado que 
(y’ – y) = ta / d 
Logo, 
x’ = x + tb / d 
e 
 y’ = y – ta / d 
para um inteiro qualquer t. Se substituímos t por qualquer inteiro, x’ e y’ 
continuam satisfazer a equação 
c=x’a + y’b 
Deste modo, concluímos que existem muitas – na verdade, infinitas – 
soluções, que são dadas por 
x = km + tb / d 
e, 
y = kn + ta / d 
para todos os inteiros t. 
Posteriormente, com frequência desejaremos resolver 1 = xp + yq para 
inteiros coprimos p e q. Neste caso, as equações acima se tornam 
x = m + tq 
 
 
8 
e 
 y = n + tp 
TEMA 3 – LOGARITMOS DISCRETOS 
Vamos imaginar que tenhamos que calcular 35 módulo 7. Uma forma de 
fazer isso é calcularmos 35 = 243 e então calcular 243 mod 7 = 5. Um modo mais 
prático decorre de observarmos que 34 = (32)2. Já que 32 = 9, e 9 mod 7 = 2, e 
temos 34 mod 7 = 4 = 22 e, finalmente: 
35 mod 7 = (34 x 3) mod 7 = (4 x 3) mod 7 = 5 
Essa forma é a mais fácil, pois os valores usados são menores, e usa a 
potenciação ou elevação repetida, o que nos permite calcular ak mod n usando 
apenas multiplicações modulares tais como O (log k). Nós podemos usar essa 
mesma forma ao exponenciar números inteiros, mas as multiplicações não são 
multiplicações modulares, e cada multiplicação demora pelo menos o dobro do 
tempo da multiplicação anterior. 
Analisemos os módulos 7 de sucessivas potências de 3: 
31 mod 7 = 3 
32 mod 7 = 2 
33 mod 7 = 6 
34 mod 7 = 4 
35 mod 7 = 5 
36 mod 7 = 1 
Observe que o resultado do módulo de cada potência de 3 é exatamente 
o resultado do módulo 7 da potência anterior multiplicado por 3. E observamos 
que, após essa sequência, os resultados se repetem de forma cíclica: 
37 mod 7 = 3 
38 mod 7 = 2 
39 mod 7 = 6 
310 mod 7 = 4 
311 mod 7 = 5 
312 mod 7 = 1 
e assim sucessivamente. Apesar de observarmos isso, olhando rapidamente a 
sequência 3,2,6,4,5,1 não reflete nenhuma ordem aparente ou tampouco uma 
estrutura parece não ter ordem ou estrutura alguma. De qualquer modo, embora 
haja outras coincidências nessa sequência – como por exemplo: se somarmos 
os resultados à cada três elementos, o resultado será 7 – pouca coisa podemos 
 
 
9 
considerar a respeito dessa sequência, o que nos leva ao problema do 
logaritmo discreto. 
3.1 O problema do logaritmo discreto 
Seja p um número primo, e g, h dois elementos de ℤ𝐩𝐩∗ (ou seja, números 
inteiros menores que p). Suponhamos que saibamos que gx = h (mod p). Então, 
qual é o valor de x? 
Por exemplo, vamos avaliar uma ocorrência do problema do log discreto: 
calcular o valor de x de tal modo que 3x = 6 (mod 7). A resposta é: x = 3. Falando 
de forma específica, qualquer x = 3 (mod 6) vale como resposta. Vamos lembrar 
que, quando encontramos a inversão modular pela primeira vez, percebemos 
que poderíamos tentar cada elemento para encontrar um inverso. Porém isso é 
muito demorado para ser usado na prática. O mesmo vale para os logaritmos 
discretos: nós podemos tentar todas as potências possíveis até encontrá-las, 
mas isso é impraticável. 
O algoritmo de Euclides nos fornece uma maneira mais efetiva de 
computar inversos, porém não conhecemos nenhum algoritmo rápido para 
encontrar os logaritmos discretos. Os melhores algoritmos conhecidos para 
calcular logaritmos discretos são muito mais rápidos do que tentar todos os 
elementos, mas mesmo assim não são equivalentes ao tempo do cálculo 
polinomial. 
Esse conceito de logaritmos discretos é de fundamental importância, na 
atualidade, para os mecanismos de chave pública e assinatura digital. O 
entendimento desse conceito e de sua aplicação no contexto computacional 
passa pelos conhecimentos básicos da teoria dos números que estamos 
apresentando. Em função desse entendimento, dizemos que dois números 
são relativamente primos se não tiverem fatores primos em comum, isto é, se 
seu máximo divisor comum for 1. 
Veremos, a seguir, que a função de Euler, Φ (n), expressa o número de 
inteiros positivos menores que n que são relativamente primos com n. E devido 
a questões técnicas definimos que: 
Φ(1) = 1 
Vejamos os seguintes exemplos: 
 
 
10 
Φ (89) = 88 
O que significa que os inteiros de 1 a 88 são relativamente primos de 89, 
uma vez que 89 é primo. 
Φ (45) = 40 
Uma vez que 1,2,4,6,7,8,10,11,12,13,14,16,17,18,19,...,40 são os inteiros 
positivos menores que 45 que são relativamente primos de 45. As tabelas que 
expressam os valores desta função são vastas na bibliografia, e por meio delas 
podemos verificar que, se p é primo, então 
Φ (p) = p-1 
Também temos que, se 
p≠q 
São números primos, então 
Φ (pq) = Φ (p) Φ(q)=(p-1)(q-1) 
Essa expressão reflete o Teorema de Euler, assunto de nosso próximo 
tema! 
TEMA 4 – TEOREMAS DE EULER E FERMAT 
Como já dissemos, o problema do logaritmo discreto pode ser complexo, 
porém temos a nosso favor alguns pontos sobre a potência de uma unidade a 
∈ ℤ𝒏𝒏∗ . Primeiramente, ak = 1 para algum valor de k: uma vez que existem 
diversas unidades, em quantidade finita, é possível que devamos ter ax = ay para 
algum x < y eventualmente, e uma vez que existe um a − 1 podemos encontrar a 
x – y = 1. 
Consideremos a ∈ ℤ𝒏𝒏∗ . O menor inteiro positivo x para o qual ax = 1 (mod 
n) é chamado a ordem de a. A sequência a, a2, ... repete-se até atingir ax = 1. 
Como nesse caso ax + k = ak, e temos ak = 1 precisamente quando k é um múltiplo 
de x. Por exemplo: As potências de 3 (mod 7) são 3,2,6,4,5,1 então a ordem de 
3(mod 7) é 6. Os teoremas apresentados a seguir reduzem drasticamente o 
conjunto dos valores possíveis para a ordem de uma unidade. 
 
 
11 
4.1 Pequeno Teorema de Fermat 
O pequeno teorema de Fermat afirma que dado um número primo p então 
ap = a (mod p) para qualquer a ∈ ℤ𝒑𝒑 . Uma forma na qual este teorema é 
geralmente expresso é ap − 1 = 1 (mod p) desde que a não seja zero. Para provar 
esse teorema, primeiro mostramos uma identidade – por vezes denominada “o 
sonho de calouro”: para um dado número primo p temos: 
(x + y) p = xp + yp (mod p) 
Isto é imediato a partir da expansão binomial, porque p divide cada termo, 
exceto por dois termos, ou seja, 
(x + y)p = xp + yp + p (...) = xp + yp (mod p) 
Por indução temos: 
(x1 + ... + xn) p = 𝒙𝒙𝟏𝟏
𝒑𝒑+ ... + 𝒙𝒙𝒏𝒏
𝒑𝒑 
Assim, se declaramos a = 1 + ... + 1a = 1 + ... + 1 (ou seja, a números 1s), 
temos então que: 
ap = (1 + ... + 1) p = 1p + ... + 1p = 1 + ... + 1 = a.n 
Esse pequeno teorema de Fermat oferece outra maneira de computar 
inversos. Para a ∈ ℤ𝒑𝒑′∗ , a – 1 pode ser calculado como ap − 2, uma vez que temos 
a.ap − 2 = 1 pelo teorema. 
Então, em resumo, o pequeno teorema de Fermat afirma que se p é um 
número primo, então para qualquer inteiro a, o número ap - a é um inteiro múltiplo 
de p. Em notação aritmética modular escrevemos deste modo: 
ap ≡ a (mod p) 
Como exemplo e prova podemos demonstrar que, se a = 2 e p = 7, então 
27 = 128 e 128 - 2 = 126 = 7 × 18, portanto 126 é um múltiplo inteiro de 7. Se a 
não é divisível por p, o pequeno teorema de Fermat equivale à afirmação de que 
ap - - 1 é um inteiro múltiplo de p, ou seja: 
ap-1 ≡ 1 (mod p) 
 
 
12 
Para provar isso, vejamos: se a = 2 e p = 7, então 26 = 64 e 64 - 1 = 63 = 
7 × 9, sendo, portanto, um múltiplo de 7. 
4.2 Teorema de Euler 
O Teorema de Euler é, de certa forma, um modo genérico do pequeno teorema 
de Fermat, que vimos antes. O modo formal de expressar o teorema de Euler é 
o seguinte: se a ∈ ℤ𝒏𝒏∗ então aϕ (n) = 1 (mod n). Isso reduz o pequeno teorema 
de Fermat quando n é primo. 
Para comprovar, podemos considerar o seguinte: seja m = ϕ (n), e 
identificadas as unidades u1, ..., um. Consideremos, então, a sequência au1, ..., 
aum (ou seja, apenas multiplicamos cada unidade por a). Se aui = auj, então a 
multiplicação por a − 1 (que existe, uma vez que a é uma unidade) resulta em ui 
= uj, e, portanto, os membros da sequência são distintos. Além disso, sabemos 
que os produtos das unidades também devem ser unidades, e, portanto, au1, ..., 
aum deve ser u1,..., um em alguma ordem. Multiplicando todas as unidades juntas 
temos: 
au1 ... aum = u1 ... um 
Reorganizando os produtos: 
aϕ (n) = am = (u1 ... um) (u1 ... um) −1 = 1 
Da mesma forma, o Teorema de Euler também oferece uma maneira 
alternativa de calcular os inversos. Para todo a ∈ ℤ𝒏𝒏∗ , o valor de a − 1 pode ser 
calculado como aϕ (n) −1. É um modo bastante eficiente, já que podemos usar a 
repetição de quadrados, porém o algoritmo de Euclides é ainda mais rápido (qual 
seria o motivo?) E não requer que tenhamos que calcular ϕ (n). 
Estes teoremas não nos dizem a ordem de uma dada unidade a ∈ ℤ𝒏𝒏∗ , 
entretanto a diminuem significativamente: façamos x ser a ordem de a. Se 
sabemos que ay = 1 pelo algoritmo de Euclides, podemos encontrar m, n tal que 
d = mx + ny 
onde d = mdc (x, y). Então 
ad = amx + ny = (ax) m (ay) n = 1 
 
 
13 
assim, como d ≤ x, devemos ter d = x (já que x é o menor inteiro positivo para o 
qual ax = 1) e, consequentemente, x deve ser um divisor de y. Assim, pelo 
Teorema de Euler, a ordem de a divide ϕ (n). Podemos finalizar lembrando que 
esses teoremas são casos especiais do Teorema de Lagrange (da teoria dos 
grupos), ressaltando que tanto Fermat como Euler morreram muito antes da 
teoria do grupo ser desenvolvida. 
4.3 Teorema de Euler e o problema do logaritmo discreto 
Uma vez que já fomos apresentados ao Teorema de Euler, vamos retomar 
o problema do logaritmo discreto. Se t e n são números relativamente primos, 
então: 
tΦ(n) = 1 ( mod n) 
Vamos considerar a seguinte 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 
entendermos melhor esse conceito, vejamos o exemplo a seguir: 
71 = 7 ( mod 19) 
72 = 11 ( mod 19) 
73 = 1 ( mod 19) 
74 = 7 ( mod 19) 
75 = 11 ( mod 19) 
76 = 1 ( mod 19) 
77 = 7 ( mod 19) 
 
Observamos que o resultado expressa uma sequência periódica, cujo 
período é 3, ou seja, neste caso x = 3 é o gerador. Consideremos, agora, o primo 
n = 13 e a seguinte tabela: 
Tabela 1 - Inteiros positivos mod 13 diferentes de zero 
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 
 
 
14 
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 
Analisando essa tabela, podemos notar que determinados valores de t 
geram, por meio das potências, o conjunto dos valores inteiros positivos de mod 
13 diferentes de zero. Denominamos a cada um desses inteiros de raiz primitiva 
do mod 13. Nesse caso, esses números são 2,4,6,10,11. Notamos, também, 
que, se t é primitiva de n, então: 
t, t2,t3,...,tΦ(n) 
São relativamente primos de n. Em particular, se n = p, então: 
t, t2,t3,...,tp-1 
São relativamente primos de p. A Teoria dos Números nos revela que os 
inteiros que têm raízes primitivos são 2,4, e os da forma pk e 2pk, onde p é um 
número primo maior que 2 e k é um inteiro positivo. 
A questão do logaritmo discreto para números primos desperta um 
interesse especial no âmbito da criptografia. Consideremos um número p primo 
e t uma raiz primitiva de p. As potências de t de 1 até p - 1 apresentam os 
valores de 1 até p - 1 exatamente uma vez, tomados pelo módulo p. Por 
intermédio da aritmética modular, sabemos que dado um inteiro b, 
b= s mod p, para 0 ≤ s ≤ p -1 
Assim, seguimos considerando que, para um inteiro b e t uma raiz 
primitiva de p, existirá um expoente i com 
1 ≤ i ≤ p -1, tal que b = ti mod p 
Então nós podemos definir o número i como sendo o logaritmo discreto 
de b na base t mod p, o que denotamos por 
d logt,p b = i 
 
 
15 
Podemos apresentar outras notações para este conceito, e verificamos na 
Tabela 1 já apresentada, que também podemos escrever: 
d log11,13 25 = 6 
ou 
d log2,13 14 = 12 
4.4 Cálculo do logaritmo discreto 
O cálculo do logaritmo discreto consiste em solucionar o seguinte 
problema: "Dados três números primos, b, t e p, encontrar x de modo que b = 
tx mod p". A grande dificuldade para resolver essa equação para um número 
primo p muito grande, com muitos dígitos, mesmo com um algoritmo 
considerado rápido, é da ordem de: 
exp[(ln p)1/3(ln (ln p)2/3] 
Isso torna inviável o tratamento computacional para a busca de um 
resultado, mesmo fazendo uso de um ambiente computacional potente. É por 
isso que todo o sistema criptográfico na atualidade é baseado em um problema 
matemático de difícil solução computacional, em um tempo satisfatório. 
4.5 Multiplicação e Ordem 
Seja x a ordem de a ∈ ℤ𝒏𝒏∗ e y a ordem de b ∈ ℤ𝒏𝒏∗ . Então qual é a ordem 
do produto ab? Para responder a essa questão, suponhamos que (ab) k = 1. 
Elevando ambos os lados da equação à x temos então que 
bkx = 1kbkx = (ax) kbkx = (ab) kx = 1 
Como b tem ordem y, concluímos que y | kx. Agora suponhamos que x, y 
sejam coprimos. Então devemos ter y | k. De modo semelhante temos x | k, e, 
portanto, k deve ser um múltiplo de xy. Por outro lado, temos (ab) xy = 1 e, 
exatamente por isso, a ordem de ab é precisamente xy: Ou seja, “para os 
elementos com ordens de coprimos,a ordem de seu produto é igual ao 
produto de suas ordens”. 
Expondo de forma mais genérica, seja d = mdc (x, y). Então x | ky e y | 
kx implica que k deve ser um múltiplo de (x / d) (y / d). Se z é o mmc de x e y, 
 
 
16 
o qual podemos calcular por z = xy / d, então (ab) z = 1. Desse modo, tudo o que 
podemos dizer até esse momento é que a ordem de ab é um múltiplo de xy / d2 
e divide xy / d. 
4.6 O problema do RSA1 
Suponha que nos sejam dados os números inteiros positivos e, N e ae 
(mod N) para alguma unidade a. Como podemos recuperar a? Uma estratégia 
é: encontrar um inteiro d tal que ade = a (mod N). Pelo que vimos no Teorema 
de Euler, d irá satisfazer esta equação se de = kϕ (N) + 1 para algum k. Expondo 
isso de outra forma, nós podemos calcular: 
d = e − 1 (mod ϕ (N)) 
e então calcular (ae) d para recuperarmos o valor de a. Porém, até o momento, 
não sabemos como calcular ϕ (N) a partir de N sem fatorar N, e ainda não temos 
uma forma de fatorar grandes números primos com eficiência. A segurança e a 
confiabilidade do algoritmo RSA residem nessa dificuldade. 
TEMA 5 – TESTES DE FERMAT E MILLER-RABIN 
O uso de números primos grandes é essencial para alguns algoritmos de 
criptografia. Porém um dos complicadores do uso desses números é exatamente 
a identificação deles. Por definição, um número primo é aquele divisível apenas 
por 1 e por ele mesmo. Imaginemos um inteiro qualquer n: como podemos 
afirmar que n é primo? Vamos assumir que n seja ímpar, já que o único caso de 
número par e primo é o do número 2. A forma mais corriqueira de verificar se n 
é primo seria procurar os fatores de n, entretanto, como já sabemos, ainda não 
conhecemos nenhum algoritmo de fatoração eficiente para essa operação. 
5.1 O teste de Fermat 
Conhecemos como teste de Fermat ou teorema de Fermat o seguinte 
enunciado: se o número n é primo, então para qualquer a temos que an-1 = 1 
(mod n). Na prática é isso o que sugere o teste de Fermat para identificar um 
 
1 RSA é um sistema criptográfico de chave pública pioneiro, desenvolvido por Ron Rivest, Adi 
Shamir e Leonard Adleman (de cujos sobrenomes vem o acrônimo RSA) no qual a chave de 
criptografia é pública, e a chave de descriptografia é privada. A segurança do algoritmo é 
baseada na grande dificuldade de fatorar números primos de valor elevado. 
 
 
17 
número primo: escolhemos um número aleatório a tal que a ∈ {1, ..., n − 1} e 
verificamos se an-1 = 1 (mod n). Se não, então deve ser um número composto, 
isto é, não é primo. Entretanto podemos ainda obter essa igualdade mesmo 
quando n não é primo. Se considerarmos, por exemplo, que n = 561, isto é, 3 × 
11 × 17. Pelo teorema chinês do resto, temos que: 
ℤ561 = ℤ 3 × ℤ 11 × ℤ 17 
Desse modo podemos verificar que, para cada 
a ∈ ℤ𝟓𝟓𝟓𝟓𝟏𝟏∗ 
Correspondem alguns números 
(x, y, z) ∈ ℤ𝟑𝟑∗ x ℤ𝟏𝟏𝟏𝟏∗ x ℤ𝟏𝟏𝟏𝟏∗ 
Pelo teorema de Fermat temos que 
x2 = 1, y10 = 1 e z16 = 1 
Como tanto 2, como 10 e 16 são divisores de 560, isso significa que (x, y, 
z)560 = (1,1,1), ou, de outro modo, podemos afirmar que 
a560 = 1 para qualquer a ∈ ℤ𝟓𝟓𝟓𝟓𝟏𝟏∗ 
Ou seja, não importa o a que escolhermos, pois 561 sempre passará no 
teste de Fermat, apesar de ser composto, desde que a seja coprimo de n. Os 
números para os quais essa situação ocorre são denominados números 
Carmichael ou pseudoprimos, e há uma infinidade desses números. 
Se a não é coprimo de n então este teste de Fermat falha, mas então 
podemos facilmente obter um fator de n calculando o mdc (a, n). 
5.2 O teste de Miller-Rabin 
Um modo melhor para fazer esse cálculo é lembrar que n é primo se e 
somente se as soluções de x2 = 1 (mod n) são somente x = ± 1. Assim, se 
validarmos n pelo teste de Fermat, isto é, an−1 = 1, então também verificamos a 
(n − 1) / 2 = ± 1, uma vez que a (n − 1) / 2 é uma raiz quadrada de 1. Porém os números 
como o terceiro número de Carmichael (1729) invalidam mesmo este teste mais 
 
 
18 
avançado. Entretanto, e se nós o repetirmos? Ou seja, enquanto for possível, 
continuaremos reduzindo o expoente pela metade até alcançarmos um número 
qualquer além de 1. Se o resultado for qualquer outro número que não −1, então 
n deve ser composto, ou seja, não é primo. 
Expressando de maneira formal, seja 2s a maior potência de 2 que divide 
n − 1, isto é, n − 1 = 2sq para algum número ímpar q. Desse modo, cada membro 
da sequência 
𝑎𝑎𝑛𝑛−1 = 𝑎𝑎2𝑠𝑠𝑞𝑞, 𝑎𝑎2𝑠𝑠𝑞𝑞, ... 𝑎𝑎𝑞𝑞 
é uma raiz quadrada do membro anterior. Então, se n é primo, esta sequência 
começará com 1 e cada membro será 1, ou o primeiro membro da sequência 
diferente de 1 é -1. 
O teste de Miller-Rabin trata, então, de escolhermos um número a ∈ ℤ n. 
Se a sequência apresentada anteriormente não começa com 1, ou o primeiro 
membro da sequência que não é 1 também não é -1, então n não é primo. 
Acontece, porém, que, para qualquer número composto n, incluindo os já citados 
números de Carmichael, a probabilidade de n passar no teste de Miller-Rabin é 
de, no máximo, ¼, sendo que na média essa probabilidade é bem menor. 
Portanto, a probabilidade de n passar no teste após sucessivas execuções 
diminui exponencialmente. 
Se n não passar no teste de Miller-Rabin com uma sequência começando 
com 1, então temos uma raiz quadrada não trivial de 1 módulo n, e poderemos 
fatorar n de modo eficiente. Desse modo, os números de Carmichael serão 
sempre fáceis de fatorar. 
Quando o teste de Miller-Rabin é executado em números da forma pq onde p, q 
são grandes números primos grandes, o teste falha quase sempre, pois a 
sequência não começa com 1. Esse é o motivo pelo qual o algoritmo de 
criptografia RSA não pode ser quebrado dessa maneira. 
A implementação do teste de Miller-Rabin é feita, na prática, da seguinte 
forma: 
1. Dado n, encontramos s de modo que n − 1 = 2sq para algum q ímpar. 
2. Escolhemos um valor aleatório para a de tal modo que a ∈ {1, ..., n − 1} 
3. Se aq = 1, então n passa no teste, e finalizamos o teste. 
 
 
19 
4. Para toda iteração i = 0, ..., s − 1 verificamos se 𝑎𝑎2𝑖𝑖𝑞𝑞 = −1. Caso seja, n 
passa no teste, e finalizamos o teste. 
5. Caso contrário, n é um número composto, e, portanto, não é primo. 
Também é importante realizarmos alguns testes de divisão por pequenos 
números primos antes de executar o teste de Miller-Rabin. 
Essencialmente esses testes são testes de composição, uma vez que não 
provam que o número testado é primo, porém provam que este número é 
composto (ou seja, não é primo). Existem algoritmos determinísticos de tempo 
polinomial para verificar se o número é primo, tais como o AKS - Agrawal, Kayal 
e Saxena, embora estes, no momento, sejam impraticáveis do ponto de vista 
computacional. 
FINALIZANDO 
Os temas que estudamos nesta aula fazem parte da Teoria dos Números, 
um ramo da Matemática essencial para a modelagem de problemas – e das 
soluções desses problemas, especialmente em áreas como a Criptografia e a 
Criptologia, a robótica e a automação, e a inteligência artificial, entre tantas 
outras, como já dissemos no início. 
O domínio desse conteúdo é essencial para a pesquisa e o 
desenvolvimento de soluções computacionais embasadas na modelagem 
matemática, e mais além disso, para efetuar a comprovação da efetividade 
dessas soluções sem a necessidade de se construir programas ou sistemas, 
provando matematicamente sua viabilidade. 
Essa possibilidade é de grande valor, uma vez que representa grande 
racionalização no uso de recursos e do tempo, abre a perspectiva de discussão 
da solução em uma linguagem universal – a matemática – e reduz as 
especulações e o grau de incerteza inerente às atividades de projeto e 
desenvolvimento em geral. 
A contribuição dessa nossa aula é um incentivo a você, aluno(a), a 
caminhar na direção do estabelecimento de um modelo de trabalho em pesquisa 
e desenvolvimento tão escasso quanto caro, em nossa civilização,porém que já 
se comprovou, através dos séculos, ser capaz de diferenciar as nações e os 
povos que primaram por utilizarem-no e, assim, destacarem-se na história. 
 
 
20 
REFERÊNCIAS 
BONAFINI, F. C. Matemática e estatística. São Paulo: Pearson Education do 
Brasil, 2014. 
GERSTING, J. L. Fundamentos matemáticos para a ciência da computação: 
um tratamento moderno de matemática discreta. Rio de Janeiro: LTC, 2015. 
HUNTER, D. J. Fundamentos da matemática discreta. Rio de Janeiro: LTC, 
2011. 
LEITE, A. E.; CASTANHEIRA, N. P. Teoria dos Números e Teoria dos 
Conjuntos. Curitiba: InterSaberes, 2014. 
LYNN, B. Teoria dos Números – Notas. Stanford University. Disponível em: 
<https://crypto.stanford.edu/pbc/notes/numbertheory/>. Acesso em: 30 jul. 2019. 
MACEDO, L. R. D.; CASTANHEIRA, N. P.; ROCHA, A. Tópicos de Matemática 
Aplicada. Curitiba: InterSaberes, 2013. 
SHOUP, V. A Primer on Algebra and Number Theory for Computer 
Scientists. Courant Institute, New York University, 2002. Disponível em: 
<https://cs.nyu.edu/courses/fall02/G22.3033-010/notes.pdf>. Acesso em: 30 jun. 
2019. 
STEIN, C.; DRYSDALE, R. L.; BOGART, K. Matemática discreta para ciência 
da computação. São Paulo: Pearson Education do Brasil, 2013. 
VIEIRA, M. J. Introdução aos Fundamentos da Computação – Linguagens e 
Máquinas. São Paulo: Pioneira Thomson Learning, 2005. 
WALPOLE, R. E.; MYERS, R. H.; MYERS, S. L.; YE, K. Probabilidade & 
Estatística para engenharia e ciências. 8. Ed. São Paulo: Pearson Prentice 
Hall, 2009. 
	Conversa inicial
	TEMA 1 – ARITMÉTICA MODULAR
	TEMA 2 – ALGORITMO DE EUCLIDES
	TEMA 3 – LOGARITMOS DISCRETOS
	3.1 O problema do logaritmo discreto
	TEMA 4 – TEOREMAS DE EULER E FERMAT
	4.1 Pequeno Teorema de Fermat
	4.2 Teorema de Euler
	4.3 Teorema de Euler e o problema do logaritmo discreto
	4.4 Cálculo do logaritmo discreto
	4.5 Multiplicação e Ordem
	4.6 O problema do RSA0F
	TEMA 5 – TESTES DE FERMAT E MILLER-RABIN
	5.1 O teste de Fermat
	5.2 O teste de Miller-Rabin
	FINALIZANDO
	REFERÊNCIAS