AritméticaModular VF

Universidade Federal do ABC
Centro de Matemática, Computação e Cognição
Aritmética Modular e Criptografia
Jeovah Pereira de Alencar

Orientador: Prof. Dr. Antonio Cândido Faleiros
Dissertação apresentada junto ao Programa de

Mestrado Profissionalizante em Matemática da
Universidade Federal do ABC, para obtenção do
Tı́tulo de Mestre em Matemática.
Santo André - SP
Agosto de 2013.
Aritmética Modular e Criptografia
Este exemplar corresponde à redação

final da dissertação devidamente cor-
rigida e defendida por Jeovah Pereira
de Alencar e aprovada pela comissão
julgadora.
Santo André, 22 de agosto de 2013.
Prof. Dr. Antonio Cândido Faleiros

Orientador
Banca examinadora:
1. Prof. Dr. Antonio Cândido Faleiros - UFABC (Presidente)
2. Prof. Dr. Adail de Castro Cavalheiro - UnB (Membro Titular)
3. Prof. Dr. Daniel Miranda Machado - UFABC (Membro Titular)
Dissertação apresentada junto ao Programa

de Mestrado Profissional em Matemática da
UFABC, como requisito parcial para ob-
tenção do Tı́tulo de Mestre em Matemática.
Este exemplar foi revisado e alterado em relação à versão ori-
ginal, de acordo com as observações levantadas pela banca no dia
da defesa, sob responsabilidade única do autor e com a anuência de
seu orientador.
Santo André, 27 de agosto de 2013.
Assinatura do autor:
Assinatura do orientador:
Dedico este trabalho à minha mãe, que está sempre no meu coração e no
meu pensamento, e à minha famı́lia, em especial ao meu filho Pedro.
Agradecimentos
Agradeço primeiramente a Deus por me conduzir até aqui, ao Pro-

grama de Mestrado Profissional em Matemática (PROFMAT), à CAPES
pelo auxı́lio concedido, à UFABC e seus professores, ao meu orientador Prof.
Dr. Antonio Cândido Faleiros e aos colegas de turma do mestrado. A todos
minha sincera gratidão.
8
Resumo
Acreditando que a aritmética modular possa ser introduzida no ensino médio
e usando como centro de interesse a criptografia, discorremos sobre as cifras
de César, Vigenère e de Hill, mostrando a aritmética modular por detrás de
cada uma delas, até chegarmos à moderna criptografia de chave pública RSA
utilizada na Internet. O texto é uma introdução à aritmética modular, mos-
trando algumas de suas aplicações, como por exemplo, criptografia, cálculo
de dı́gitos de verificação e regras de divisibilidade.
Palavras-Chave
Aritmética Modular, Criptografia, Criptografia RSA
9
Abstract
We believe modular arithmetic can be introduced to high school students
and cryptography plays an important motivational role. We discourse about
the ciphers of Caesar, Vigenere and Hill, and the modular arithmetic behind
each one, until we reach the modern RSA public key encryption used on the
Internet. The text is an introduction to modular arithmetic, with some of
its applications, for example, cryptography, calculation of check digits and
divisibility rules.
Keywords
Modular Arithmetic, Cryptography, RSA public key encryption
10
Sumário
1 Aritmética Modular para o Ensino Médio 13

1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Propriedades e Operações . . . . . . . . . . . . . . . . . . . . 19
1.2.1 Propriedades da Congruência Módulo m . . . . . . . . 19
1.2.2 Adição e Multiplicação Modular . . . . . . . . . . . . . 20
1.2.3 Inversos Módulo m . . . . . . . . . . . . . . . . . . . . 22
1.2.4 Equações Módulo m . . . . . . . . . . . . . . . . . . . 24
1.2.5 Potenciação . . . . . . . . . . . . . . . . . . . . . . . . 25
1.3 Cálculo de potências xy mod m com auxı́lio da base 2 . . . . . 26
2 Criptografia e Aritmética Modular 31

2.1 Criptografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.1 A Cifra de César . . . . . . . . . . . . . . . . . . . . . 32
2.1.2 A Matemática da Cifra de César . . . . . . . . . . . . 33
2.1.3 A Cifra de Vigenère . . . . . . . . . . . . . . . . . . . . 35
2.1.4 A Matemática da Cifra de Vigenère . . . . . . . . . . . 38
2.1.5 Cifrário de Hill . . . . . . . . . . . . . . . . . . . . . . 42
2.2 Criptografia de Chave Pública . . . . . . . . . . . . . . . . . . 47
2.2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.2.2 O Método de Diffie-Hellman . . . . . . . . . . . . . . . 49
3 Criptografia RSA 53
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2 A matemática do RSA . . . . . . . . . . . . . . . . . . . . . . 54
3.3 Uma Função e dois Teoremas Importantes . . . . . . . . . . . 56
3.4 Como Funciona a Criptografia RSA . . . . . . . . . . . . . . . 60
3.4.1 Algoritmo Estendido de Euclides . . . . . . . . . . . . 61
3.5 Exemplificando o uso da RSA . . . . . . . . . . . . . . . . . . 63
11
12 SUMÁRIO
4 Aplicações da Aritmética Modular 71

4.1 Cálculo do dı́gito do CPF e do CNPJ . . . . . . . . . . . . . . 71
4.2 Cálculo do dı́gito do RG . . . . . . . . . . . . . . . . . . . . . 73
4.3 Cálculo do dı́gito ISBN-13 . . . . . . . . . . . . . . . . . . . . 74
4.4 Critérios de Divisibilidade . . . . . . . . . . . . . . . . . . . . 75
4.4.1 Divisibilidade por 3 . . . . . . . . . . . . . . . . . . . . 75
4.4.5 Divisibilidade por 11 . . . . . . . . . . . . . . . . . . . 78
4.4.6 Divisibilidade por 7, 11 e 13 . . . . . . . . . . . . . . . 79
4.4.7 Outros critérios de Divisibilidade . . . . . . . . . . . . 80
4.5 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . 81
Capı́tulo 1
Aritmética Modular para o

Ensino Médio
1.1 Introdução
O matemático suı́ço Leonhard Euler (1707-1783) foi quem introdu-
ziu, por volta de 1750, a aritmética modular (também chamada aritmética
do relógio). Em 1801, Carl Friedrich Gauss, matemático alemão, utilizou
e desenvolveu a aritmética modular em seu livro “Disquisitiones Arithmeti-
cae”. Durante muito tempo não houve aplicações importantes da aritmética
modular até que na segunda metade do século XX uma aplicação surpre-
endente dessa idéia veio resolver um problema que desafiava matemáticos e
criptógrafos, o problema da troca de chaves criptográficas.
Vamos utilizar uma ideia simples para ilustrar o conceito básico da
aritmética modular. Imagine um relógio comum de ponteiros registrando 3
horas. Se quisermos saber que hora ele estará marcando após se passarem
38 horas, verificamos que o resultado é 5 horas e não 41. A cada 12 horas
o ponteiro volta ao ponto de partida, portanto após 36 horas (3 voltas com-
pletas) o ponteiro estará novamente sobre as 3 horas, adicionando mais 2
horas chegamos ao resultado. A ideia permanece válida para um relógio com
um número qualquer de subdivisões. Um relógio com 7 subdivisões apenas,
numeradas sequencialmente no sentido horário, por exemplo. Se o ponteiro
está sobre o número 5 e o fazemos saltar 43 subdivisões, a adição comum
resultaria 48, mas não temos esse resultado no mostrador do relógio. Agora,
o ponteiro volta ao 5 a cada 7 saltos, ou seja, após 42 voltas completas, que
é o múltiplo de 7 mais próximo de 43, o ponteiro estará novamente sobre o
5, adicionando 1 chegamos ao resultado: 6.
13
14 CAPÍTULO 1. ARITMÉTICA MODULAR PARA O ENSINO MÉDIO
A aritmética modular normalmente é tratada no ensino superior.

Entretanto, devido à facilidade de compreensão do conceito, suas bases po-
dem ser introduzidas já no ensino médio. Evidentemente, com uma lin-
guagem matemática apropriada para esta etapa do ensino e sem que sejam
feitas todas as demonstrações dos teoremas e proposições. Aqueles cujas de-
monstrações não sejam essenciais à compreensão do conteúdo seriam apenas
enunciados e utilizados quando necessário. A aritmética modular está pre-
sente em métodos criptográficos como a cifra de César, a cifra de Vigenère e
mais recentemente na criptografia de chave pública RSA, da qual é a base.
O assunto está relacionado à segurança digital e ao cotidiano de quem utiliza
a internet, em especial os jovens, para se comunicar, se relacionar nas redes
sociais, fazer compras e transações bancárias. Isto apenas já constitui uma
excelente motivação para o seu estudo.
As transações comercias pela internet bem como a correspondência
dos usuários da rede são protegidas por criptografia baseada na aritmética
modular. Além desta importante aplicação há outras, como veremos mais
adiante. A ideia básica da aritmética modular é bem simples. Fixado um
inteiro m, todos os demais números inteiros a são substituı́dos pelo resto
de sua divisão euclidiana por m e representados por a mod m = b, b ∈
{0, 1, . . . , m − 1}. Desse modo, o conjunto Z dos números inteiros se trans-
forma no conjunto Zm = {0, 1, . . . , m − 1}, denominado conjunto dos inteiros
módulo m (cujos elementos são os restos possı́veis da divisão de um inteiro
a qualquer por m).
Assim como no conjunto dos números racionais temos as frações equi-
valentes, dizemos que dois inteiros que dão o mesmo resto quando divididos
por m são congruentes (equivalentes) módulo m. Por exemplo,
11 mod 7 = 4, assim como 25 mod 7 = 4
Portanto, 11 e 25 são congruentes módulo 7 e representamos 11 ≡ 25

mod 7. A congruência módulo m também pode ser verificada se fizermos a
diferença entre os dois inteiros e o resultado for um múltiplo de m. No caso
do exemplo, 25 − 11 = 14 = 2 · 7, o que também mostra que 11 e 25 são con-
gruentes módulo 7. A congruência módulo m é uma relação de equivalência
que subdivide o conjunto Z em m classes de equivalência, cada uma corres-
pondendo a um resto da divisão euclidiana por m.
Proposição 1. Dois inteiros p e q são congruentes módulo m, m ∈ Z,

m > 1 se, e somente se, p − q for divisı́vel por m e representamos
p ≡ q mod m.
1.1. INTRODUÇÃO 15
Demonstração. Sejam p = k1 m + r1 e q = k2 m + r2 , então r1 = p mod m e

r2 = q mod m.
(=⇒) Se p e q são congruentes módulo m, então
p ≡ q mod m =⇒ p mod m = q mod m =⇒ r1 = r2 =⇒
p−q = k1 m+r1 −k2 m−r2 = (k1 −k2 )m+(r1 −r2 ) =⇒ p−q = (k1 −k2 )m =⇒
m|p − q.
(⇐=) Se p − q é múltiplo de m, então
p − q = km =⇒ p = km + q =⇒ p mod m = (km + q) mod m =⇒
p mod m = km mod m + q mod m =⇒ p mod m = q mod m =⇒
p ≡ q mod m.
Exemplo 1. Determinar o valor de x = 139 mod 11.
Solução Basta efetuar a divisão euclidiana de 139 por 11, cujo resultado
é quociente 12 e resto 7. Portanto, x = 7.
Exemplo 2. Dentre os inteiros 111, 370, 341, 80 e 203 qual(is) é(são) con-
gruente(s) a 139 módulo 11?
Solução Procuramos x ≡ 139 mod 11, x ∈ {111, 370, 341, 80, 203}.
Pela proposição 1 acima, x é tal que 11|(x − 139). Verificamos que somente
x = 370 é solução.
370 − 139 = 231 = 21 · 11

Exemplo 3. Hoje é quarta- feira, 27 de fevereiro. Pedro tem 9 anos e fará

aniversário no dia 21 de junho. Em que dia da semana Pedro completará 10
anos?
Solução Se não temos um calendário à mão, mesmo assim podemos de-

terminar o dia da semana em que Pedro fará aniversário. Primeiro contamos
os dias até 21 de junho: 1 + 31 + 30 + 31 + 21 = 114 dias. Como iniciamos
a contagem a partir de uma quarta-feira, associamos 0 mod 7 a esse dia da
semana. Veja abaixo como fica:
quarta-feira −→ 0 mod 7=0
quinta-feira −→ 1 mod 7=1
sexta-feira −→ 2 mod 7=2
sábado −→ 3 mod 7=3
domingo −→ 4 mod 7=4
segunda-feira −→ 5 mod 7=5
terça-feira −→ 6 mod 7=6
Agora adicionamos 114 mod 7 ao dia de hoje (0 mod 7),
0 mod 7 + 114 mod 7 = 0 + 2 = 2 = 2 mod 7
Isto significa que o 114o dia a partir de hoje, dia do aniversário do
Pedro, cairá numa sexta-feira (2 mod 7 na tabela).
Exemplo 4. Determine o primeiro termo (a1 ) de uma P.A. de razão 7, sa-

bendo que 0 < a1 < r e um dos termos dessa P.A. é 21888. Qual a ordem do
termo dado?
Solução O termo geral de uma P.A. é an = a1 + (n − 1)r, onde a1 é o

primeiro termo e r é a razão.
Observe que
an mod r = [a1 + (n − 1)r] mod r = a1 mod r + [(n − 1)r] mod r =
a1 mod r =⇒
an mod r = a1 mod r =⇒ an ≡ a1 mod r (∀n, n ∈ N∗ )
Como a1 < r =⇒ a1 mod r = a1 =⇒ an mod r = a1 (∀n, n ∈ N∗ )

1.1. INTRODUÇÃO 17
Logo,
a1 = an mod r =⇒ a1 = 21888 mod 7 =⇒ a1 = 6.
Usando agora a fórmula do termo geral da P.A. temos,
an = a1 + (n − 1)r =⇒ 6 + (n − 1) · 7 = 21888 =⇒
21888−6
n= 7
+ 1 =⇒ n = 3127 =⇒ 21888 = a3127 .
Exemplo 5. Determine o 2954o algarismo da dı́zima perı́odica gerada pela

fração 11
7
.
Solução Efetuando a divisão do numerador 11 pelo denominador 7, obte-

mos a dı́zima 1, 571428 cujo perı́odo possui 6 algarismos. O primeiro alga-
rismo da dı́zima é 1 (unidades). Portanto, o que queremos é o 2953o algarismo
da parte decimal. Calculando 2953 mod 6 obtemos quociente 492 e resto 1,
o que significa 492 perı́odos e um algarismo, que no caso é o 5. Logo, o 2954o
algarismo desta dı́zima periódica é 5.
Exemplo 6. Qual é o 1234o termo da sequência periódica abaixo?
∪, ⊂, ∩, ⊃, ∨, <, ∧, >, ∪, ⊂, ∩, ⊃, ∨, <, . . .
Solução A sequência possui oito termos distintos repetindo-se na mesma

ordem, portanto basta calcularmos 1234 mod 8 = 2. Conforme a tabela
abaixo, o resultado corresponde ao segundo termo, ou seja, ⊂.
1o termo: ∪ −→ 1 mod 8=1

2o termo: ⊂ −→ 2 mod 8=2
3o termo: ∩ −→ 3 mod 8=3
4o termo: ⊃ −→ 4 mod 8=4
5o termo: ∨ −→ 5 mod 8=5
6o termo: < −→ 6 mod 8=6
7o termo: ∧ −→ 7 mod 8=7
8o termo: > −→ 8 mod 8=0
Exemplo 7. Determine o algarismo das unidades de 273100 .
Solução O algarismo das unidades de qualquer número é o resto da di-

visão desse número por 10. Sendo assim, devemos resolver 273100 mod 10.
273 ≡ 3 mod 10 =⇒ 273100 ≡ 3100 mod 10 = (32 )50 mod 10 =
950 mod 10.
Como 9 ≡ −1 mod 10, temos
950 mod 10 = (−1)50 mod 10 = 1.
Portanto o algarismo das unidades de 273100 é 1.
Exemplo 8. Calcule o mdc(858, 546).
Solução O método mais eficiente para calcular o máximo divisor comum

de dois inteiros é o algoritmo de Euclides, que consiste primeiramente em
dividir o maior pelo menor. Em seguida divide-se o divisor pelo resto e assim
sucessivamente até obter resto zero. O mdc será o último resto diferente de
zero obtido. Vejamos o processo do ponto de vista da aritmética modular.
858 mod 546 = 312

546 mod 312 = 234
312 mod 234 = 78
234 mod 78 = 0
Logo, o mdc(858, 546) = 78.
Observação: Como desafio, encontre o mdc(12119247318071, 673624408921)
usando o método descrito acima e a função MOD da planilha Excel. (solução:
151609)
1.2. PROPRIEDADES E OPERAÇÕES 19
1.2 Propriedades e Operações

1.2.1 Propriedades da Congruência Módulo m
O conjunto Zm = {1, 2, . . . , m − 1} dos inteiros módulo m, é fechado

para as operações de soma e multiplicação módulo m e valem as seguintes
propriedades.
Dados a, b e c inteiros, então:
1) a ≡ a mod m; (reflexiva)
2) a ≡ b mod m =⇒ b ≡ a mod m; (simétrica)
3) a ≡ b mod m e b ≡ c mod m =⇒ a ≡ c mod m; (transitiva)
4) Se a ≡ b mod m então
a ± c ≡ b ± c mod m;
a × c ≡ b × c mod m;
a ≡ b + cm mod m;
5) a + c ≡ b mod m =⇒ c ≡ b − a mod m;
Observação: As três primeiras propriedades fazem da congruência módulo

m uma relação de equivalência. Cada número inteiro corresponde a um dos
restos da divisão euclidiana por m. Isto reduz o conjunto infinito Z ao con-
junto finito Zm = {1, 2, . . . , m−1} onde cada elemento representa uma classe
de equivalência.
Além disso, quando a e m forem co-primos (mdc(a, m) = 1),
6) ac ≡ b mod m =⇒ c ≡ ba−1 mod m;
7) ac ≡ ab mod m =⇒ c ≡ b mod m. (lei do cancelamento).

O conjunto Zp , p primo, munido das operações de adição e mul-

tiplicação módulo p com as propriedades a seguir constitui uma estrutura
algébrica denominada corpo. Dados a, b, c e k inteiros, temos:
A1) adição associativa: a + (b + c) mod p = (a + b) + c mod p;
A2) adição comutativa: a + b mod p = b + a mod p;
A3) neutro aditivo: a + kp mod p = kp + a mod p = a mod p;
A4) inversos aditivos: a+(kp−a) mod p = (kp−a)+a mod p = 0 mod p;
M1) multiplicação associativa: a(bc) mod p = (ab)c mod p;
M2) multiplicação comutativa: ab mod p = ba mod p;
M3) neutro multiplicativo: a1 mod p = 1a mod p = a mod p;
M4) inversos multiplicativos: aa−1 mod p = a−1 a mod p = 1 mod p,

quando p 6 | a;
D) distributiva: a(b + c) mod p = ab mod p + ac mod p.
1.2.2 Adição e Multiplicação Modular
Efetuar adições e multiplicações módulo m consiste basicamente em

tomar os operandos módulo m, fazer as operações indicadas e reduzir o re-
sultado módulo m.
Proposição 2. Para todo a, b e m inteiros, m > 1, valem:
1) a ± b mod m = [(a mod m) ± (b mod m)] mod m;
2) ab mod m = [(a mod m)(b mod m)] mod m;

Demonstração. 1. Sejam a, b, e m inteiros, m > 1. Então,

a = mq + r =⇒ r = a mod m, 0 ≤ r < m
e b = mq 0 + r0 =⇒ r0 = b mod m, 0 ≤ r0 < m
e segue que
a ± b = m(q ± q 0 ) ± (r ± r0 ) =⇒
(a ± b) mod m = (r ± r0 ) mod m =⇒
(a ± b) mod m = [(a mod m) ± (b mod m)] mod m.

2. Agora,
ab = [(mq + r)(mq 0 + r0 )] = [m(mqq 0 + qr0 + q 0 r) + rr0 ] =⇒
ab mod m = rr0 mod m =⇒
ab mod m = [(a mod m)(b mod m)] mod m.
Por indução, pode-se provar que valem as igualdades:
(a1 +a2 +. . .+an ) mod m = (a1 mod m+a2 mod m+. . .+an mod m) mod m
(a1 a2 · · · an ) mod m = [(a1 mod m)(a2 mod m) · · · (an mod m)] mod m.
Exemplo 9. Calcule:
a) (202 + 813 + 4455 + 2390) mod 2
b) (43 · 365 · 1007) mod 3

Solução
a) (202 + 813 + 4455 + 2390) mod 2 =
(202 mod 2 + 813 mod 2 + 4455 mod 2 + 2390 mod 2) mod 2 =
(0 + 1 + 1 + 0) mod 2 = 2 mod 2 = 0
b) (43 · 365 · 1007) mod 3 =
[(43 mod 3) · (365 mod 3) · (1007 mod 3)] mod 3 =
(1 · 2 · 2) mod 3 = 4 mod 3 = 1
Exemplo 10. Resolva a expressão (23 · 8 + 13 · 6 − 25) mod 7.
Solução
[(23 mod 7) · (8 mod 7) + (13 mod 7) · (6 mod 7) − (25 mod 7)] mod 7 =
(2 · 1 + 6 · 6 − 4) mod 7 = (2 + 36 − 4) mod 7 = 34 mod 7 = 6
1.2.3 Inversos Módulo m
Dizemos que um inteiro a é o inverso módulo m de outro inteiro b e

vice-versa quando
ab ≡ 1 mod m.
O teorema seguinte estabelece a condição para que um inteiro qual-
quer k possua inverso módulo m.
Teorema 1. Dados k e m inteiros, m > 1. O inteiro k possui inverso módulo
m, se e somente se, k e m forem co-primos, ou seja, mdc(k, m) = 1.
Demonstração. (=⇒) Se k e m forem co-primos o mdc(k, m) = 1 e, como
consequência do algoritmo estendido de Euclides, existem inteiros a e b, tais
que
ak + bm = 1 =⇒ ak mod m + bm mod m = 1 =⇒
ak mod m = 1 (pois bm mod m = 0) =⇒ ak ≡ 1 mod m =⇒
a é o inverso de k módulo m e escrevemos a = k −1 mod m.
(⇐=) Se a for o inverso de k módulo m, ou seja, ak ≡ 1 mod m, então existe

−b inteiro, tal que
ak = −bm + 1 =⇒ ak + bm = 1 =⇒ mdc(k, m) = 1
Exemplo 11. Determine, se houver, o inverso de 7 módulo 12.
Solução
Como mdc(7, 12) = 1, isto significa que 7 tem inverso módulo 12. Então
existem inteiros a e b, tais que 7a + 12b = 1. Usando o algoritmo estendido
de Euclides, temos:
(1) 12 = 7 × 1 + 5
(2) 7=5×1+2
(3) 5=2×2+1
(4) 2=2×1+0
De (3): 5 − 2 × 2 = 1 (5)
De (2): 2 = 7 − 5, substituindo em (5): 5 − 2 × (7 − 5) = 1 =⇒
3 × 5 − 2 × 7 = 1 (6)
De (1): 5 = 12 − 7, substituindo em (6): 3 × (12 − 7) − 2 × 7 = 1 =⇒
3 × 12 − 5 × 7 = 1
Aplicando módulo, temos
(3 × 12) mod 12 + [(−5) × 7] mod 12 = 1 =⇒
[(−5) × 7] mod 12 = 1 =⇒ 7−1 mod 12 = −5 ≡ 7 mod 12
Portanto 7 é o seu próprio inverso módulo 12.

1.2.4 Equações Módulo m
É possı́vel resolver equações do tipo aX + b ≡ c mod m quando o

mdc(a, m) = 1, ou seja, quando a tem inverso módulo m.
aX + b ≡ c mod m =⇒ aX ≡ c − b mod m =⇒
X ≡ (c − b)a−1 mod m, fazendo (c − b)a−1 = d, temos X = d + km, k ∈ Z.
Exemplo 12. Resolva a equação modular 3X − 13 ≡ 4 mod 5.
Solução
Como mdc(3, 5) = 1, temos:
3X − 13 ≡ 4 mod 5 =⇒ 3X ≡ 17 mod 5 =⇒ 3X ≡ 2 mod 5 =⇒
X ≡ (2 · 3−1 ) mod 5 =⇒ X ≡ 4 mod 5, já que 3−1 mod 5 = 2
Portanto, X = 4 + 5k, k ∈ Z.
Se mdc(a, m) = d > 1, a equação aX ≡ b mod m terá solução

apenas se d dividir b, ou seja, se toda a equação puder ser dividida por d,
de modo que a0 X ≡ b0 mod m0 , onde a0 = a/d, b0 = b/d, m0 = m/d e
mdc(a0 , m0 ) = 1.
Exemplo 13. Resolva a equação 9X ≡ 6 mod 15.
Solução
Como o mdc(9, 15) = 3, que divide 6, simplificamos a equação e obtemos
9X ≡ 6 mod 15 =⇒ 3X ≡ 2 mod 5,
cujas soluções, conforme o exemplo anterior, são da forma X = 4 + 5k,

k ∈ Z.
1.2.5 Potenciação
A maneira mais eficiente para calcular potências módulo m consiste

em usar o expoente na base 2. Observe também que
ab mod m = (a mod m)b mod m.
Exemplo 14. Calcule 4311 mod 5.
Solução
4311 mod 5 = (43 mod 5)11 mod 5 = 311 mod 5
11 = 10112 = 8 + 2 + 1 =⇒ 311 mod 5 = 38+2+1 mod 5 =
(38 × 32 × 31 ) mod 5 = (38 mod 5 × 32 mod 5 × 31 mod 5) mod 5
31 mod 5 = 3 mod 5 = 3
32 mod 5 = 9 mod 5 = 4
34 mod 5 = (32 )2 mod 5 = (32 mod 5)2 mod 5 = 42 mod 5 =
16 mod 5 = 1
38 mod 5 = (34 )2 mod 5 = (34 mod 5)2 mod 5 = 12 mod 5 = 1
4311 mod 5 = (1 × 4 × 3) mod 5 = 12 mod 5 = 2.
Portanto, 4311 mod 5 = 2.

1.3 Cálculo de potências xy mod m com auxı́lio

da base 2
Para calcular potências módulo m de expoentes elevados existe um
método simples e eficiente utilizando a base 2. Vamos exemplificar calculando
117327 mod 143. Primeiro escreve-se o expoente 327 na base 2, dividindo-o
sucessivamente por 2 e tomando os restos.
327 = 163 × 2 + 1
327 = (81 × 2 + 1) × 2 + 1
327 = 81 × 22 + 1 × 2 + 1
327 = (40 × 2 + 1) × 22 + 1 × 2 + 1
327 = 40 × 23 + 1 × 22 + 1 × 2 + 1
327 = (20 × 2 + 0) × 23 + 1 × 22 + 1 × 2 + 1
327 = 20 × 24 + 0 × 23 + 1 × 22 + 1 × 2 + 1
327 = (10 × 2 + 0) × 24 + 0 × 23 + 1 × 22 + 1 × 2 + 1
327 = 10 × 25 + 0 × 24 + 0 × 23 + 1 × 22 + 1 × 2 + 1
327 = (5 × 2 + 0) × 25 + 0 × 24 + 0 × 23 + 1 × 22 + 1 × 2 + 1
327 = 5 × 26 + 0 × 25 + 0 × 24 + 0 × 23 + 1 × 22 + 1 × 2 + 1
327 = (2 × 2 + 1) × 26 + 0 × 25 + 0 × 24 + 0 × 23 + 1 × 22 + 1 × 2 + 1
327 = 2 × 27 + 1 × 26 + 0 × 25 + 0 × 24 + 0 × 23 + 1 × 22 + 1 × 2 + 1
327 = (1×2+0)×27 +1×26 +0×25 +0×24 +0×23 +1×22 +1×2+1
327 = 1×28 +0×27 +1×26 +0×25 +0×24 +0×23 +1×22 +1×2+1
=⇒ 32710 = 1010001112
1.3. CÁLCULO DE POTÊNCIAS X Y MOD M COM AUXÍLIO DA BASE 227
Então,
11732710 mod 143 = 1171010001112 mod 143 =

8 +0+26 +0+0+0+22 +2+1
1172 mod 143 =
(117256 · 11764 · 1174 · 1172 · 1171 ) mod 143 =
[(117256 mod 143) · (11764 mod 143) · (1174 mod 143) · (1172 mod 143) · (1171
mod 143)] mod 143 =⇒ (continua mais abaixo)
Algumas potências modulares 117x mod 143, sendo x uma potência

de 2, foram calculadas a seguir (somente aquelas correspondentes ao alga-
rismo 1 no expoente 1010001112 = 32710 serão usadas no cálculo de 117327
mod 143).
1171 mod 143 = 117
1172 mod 143 = 13689 mod 143 = 104
1174 mod 143 = (1172 )2 mod 143 = (1172 mod 143)2 mod 143 =
1042 mod 143 = 10816 mod 143 = 91
1178 mod 143 = (1174 )2 mod 143 = (1174 mod 143)2 mod 143 =
912 mod 143 = 8281 mod 143 = 130
11716 mod 143 = (1178 )2 mod 143 = (1178 mod 143)2 mod 143 =
1302 mod 143 = 16900 mod 143 = 26
11732 mod 143 = (11716 )2 mod 143 = (11716 mod 143)2 mod 143 =
262 mod 143 = 676 mod 143 = 104
11764 mod 143 = (11732 )2 mod 143 = (11732 mod 143)2 mod 143 =
1042 mod 143 = 10816 mod 143 = 91
117128 mod 143 = (11764 )2 mod 143 = (11764 mod 143)2 mod 143 =
912 mod 143 = 8281 mod 143 = 130
117256 mod 143 = (117128 )2 mod 143 = (117128 mod 143)2 mod 143 =
1302 mod 143 = 16900 mod 143 = 26
Finalizando o cálculo de 117327 mod 143, temos:
11732710 mod 143 = 1171010001112 mod 143 =
(117256 · 11764 · 1174 · 1172 · 1171 ) mod 143 =
[(117256 mod 143) · (11764 mod 143) · (1174 mod 143) · (1172 mod 143) · (1171
mod 143)] mod 143 =
(26 · 91 · 91 · 104 · 117) mod 143, que calculamos em etapas como segue:
(26 · 91) mod 143 = 2366 mod 143 = 78 mod 143
(78 · 91) mod 143 = 7098 mod 143 = 91 mod 143
(91 · 104) mod 143 = 9464 mod 143 = 26 mod 143
(26 · 117) mod 143 = 3042 mod 143 = 39 mod 143
Concluimos que 117327 mod 143 = 39. As contas podem ser feitas
numa calculadora comum, entretanto, calcular diretamente 117327 na calcula-
dora não é possı́vel porque o número é muito grande chegando a ”estourar”a
capacidade de armazenamento de um computador pessoal.
Pode-se implementar o algoritmo a seguir em linguagem de pro-
gramação para efetuar o cálculo da potência y = xk mod m, onde k está
escrito na base 2.
y := 1; A := x mod m; // atribuição dos valores iniciais de y e A
y := (y ∗ A) mod m; // y recebe o valor de (1 · x) mod m
A := (A ∗ A) mod m; // A recebe o valor de (x · x = x2 ) mod m
y := (y ∗ A) mod m; // y recebe o valor de (1 · x · x2 ) mod m
A := (A ∗ A) mod m; // A recebe o valor de (x2 · x2 = x4 ) mod m
y := (y ∗ A) mod m; // y recebe o valor de (1 · x · x2 · x4 ) mod m
...
1.3. CÁLCULO DE POTÊNCIAS X Y MOD M COM AUXÍLIO DA BASE 229
Os valores da variável A são calculados sempre, mas os valores de

y são calculados apenas quando o algarismo do número binário k for 1.
Começamos pelo primeiro algarismo à direita de k. Se for 1, calculamos
y, calculamos A, eliminamos este algarismo e passamos ao seguinte. Caso
contrário, se o primeiro dı́gito à direita de k for zero, calculamos A e elimina-
mos o zero, passando ao próximo algarismo. Repetimos isso até eliminarmos
todos os dı́gitos de k. Ao final do processo temos y = xk mod m. Num
programa, como o do exemplo abaixo, usamos um comando ’if’ para testar
os dı́gitos e um ’loop while’ para reduzir a quantidade de linhas de programa,
permitindo rodá-lo para qualquer tamanho do número binário k.
y = 1; A = x % m;
while (x ! = 0)
{
if (k & 1) // verifica se o bit menos significativo é 1
{
y = y ∗ A % m;
}
A = A ∗ A % m;
k = k >> 1; // elimina o bit menos significativo de k
}
Exemplo em linguagem C.
Como atividade em sala de aula, podemos propor aos alunos imple-

mentar o algoritmo numa planilha do Excel e calcular uma potência modular
de expoente grande como 117327 mod 143 usando essa planilha.
Abaixo a descrição da planilha:
B1 : x B2 : 117
C1 : k C2 : 327
D1 : m D2 : 143
B4 : A C4 : y
A5 : vazia A10 : 5
A6 : 1 A11 : 6
A7 : 2 A12 : 7
A8 : 3 A13 : 8
A9 : 4 A14 : 9
B5 : 0 C5 : 1
B6 :=MOD(B2; D2) C6 :=MOD(B6 ∗ C5; D2)
B7 :=MOD(B6 ∗ B6; D2) C7 :=MOD(B7 ∗ C6; D2)
B8 :=MOD(B7 ∗ B7; D2) C8 :=MOD(B8 ∗ C7; D2)
B9 :=MOD(B8 ∗ B8; D2) C9 : vazia
B10 :=MOD(B9 ∗ B9; D2) C10 : vazia
B11 :=MOD(B10 ∗ B10; D2) C11 : vazia
B12 :=MOD(B11 ∗ B11; D2) C12 :=MOD(B12 ∗ C8; D2)
B13 :=MOD(B12 ∗ B12; D2) C13 : vazia
B14 :=MOD(B13 ∗ B13; D2) C14 :=MOD(B14 ∗ C12; D2)
Planilha excel para cálculo de 117327 mod 143.

Capı́tulo 2
Criptografia e Aritmética
Modular
2.1 Criptografia
A necessidade de sigilo nas comunicações militares, diplomáticas e
comerciais levou à criação de códigos para mascarar mensagens de modo
que somente os legı́timos destinatários pudessem decifrá-las. Assim surgiu a
criptografia (do grego kryptos = secreto), a arte de codificar uma mensagem
segundo uma convenção pré-estabelecida entre o emissor e o receptor, impe-
dindo que qualquer outra pessoa que a intercepte consiga ler o seu conteúdo.
As técnicas criptográficas consistem na transposição e na substituição. A
transposição é o rearranjo das letras da mensagem original gerando um ana-
grama. O número de anagramas cresce rapidamente quanto maior o texto a
ser cifrado. Matematicamente, uma transposição nada mais é do que uma
das possı́veis permutações com repetição do conjunto das letras da mensa-
gem original. Para que seja eficiente, a transposição deve ser feita segundo
um sistema objetivo conhecido pelo receptor da mensagem, ou seja, o ana-
grama não pode ser gerado de forma aleatória, caso contrário o alto número
de anagramas possı́veis torna inviável a decifração. Um exemplo de cifra por
transposição consiste em escrever a mensagem original em blocos de n letras
e a seguir copiar as n colunas resultantes de cima para baixo, da esquerda
para a direita. Preliminarmente, excluı́mos os espaços entre as palavras e
excluı́mos também os sinais gráficos (cedilha, til, pontuação, etc.), se houver.
Além disso, os dı́grafos (rr, ss, oo, etc.) na mensagem são substituı́dos por
uma só letra. Tais medidas visam dificultar a quebra do código. Vamos cifrar
a frase “O matemático é um cego numa sala escura, procurando um gato que
não está lá”, atribuı́da a Charles Darwin (1809-1882), naturalista inglês (na
31
32 CAPÍTULO 2. CRIPTOGRAFIA E ARITMÉTICA MODULAR
verdade, fazendo um elogio aos matemáticos), com o método acima e usando

n=7.
o m a t e m a
t i c o e u m
c e g o n u m
a s a l a e s
c u r a p r o
c u r a n d o
u m g a t o q
u e n a o e s
t a l a a m a
A mensagem cifrada fica assim:
“otcaccuutmiesuumeaacgarrgnltoolaa
a a a e e n a p n t o a m u u e r d o e m a m m s o o q s a”,
que é um anagrama do texto original, obtido segundo a regra descrita an-

teriormente. Observe que completamos a última linha a ser cifrada com
caracteres nulos (a m a).
O destinatário, conhecendo a chave n= 7, divide o número de carac-
teres da mensagem cifrada por 7 (no caso, 63÷7 = 9) para obter o número de
caracteres que colocará em cada coluna para decifrar a mensagem. O ponto
fraco neste caso é que um espião pode obter a chave fatorando o número de
caracteres da mensagem.
A substituição, como o nome sugere, consiste em substituir cada
letra da mensagem original por outra segundo um sistema previamente acer-
tado, de modo que a substituição inversa forneça o texto original.
2.1.1 A Cifra de César

No cifrário de César, uma das cifras de substituição mais antigas,
cada letra da mensagem original é substituı́da pela terceira letra após ela na
ordem alfabética. Ou seja, trata-se de corresponder o alfabeto original com
uma translação do mesmo de três letras adiante.
2.1. CRIPTOGRAFIA 33
alfabeto original: a b c d e f g h i j ... x y z
substituição ... : d e f g h i j k l m ... a b c
A frase de Darwin codificada usando a cifra de César ficaria assim:

“r p d w h p d w l f r h x p f h j r q x p d v d o d h v f x u d s u r f x u d q
g r x p j d w r t x h q d r h v w d o d”.
2.1.2 A Matemática da Cifra de César

Associamos a cada letra do alfabeto um número inteiro não nega-
tivo da seguinte maneira: a = 0, b = 1, c = 2, d = 3 e assim por diante até
z = 25. Desse modo nos referimos a uma letra pelo seu número correspon-
dente e vice-versa. Pensando na cifra de César como uma função c que a
cada letra λ da mensagem original associa uma única letra c(λ) = λ + 3,
surge um problema quando desejamos cifrar as letras x, y ou z. Com essa
função obtemos c(x) = c(23) = 23 + 3 = 26, c(y) = c(24) = 24 + 3 = 27 e
c(z) = c(25) = 25 + 3 = 28 que não correspondem a nenhuma letra do alfa-
beto original (que vai até z=25). Como sabemos, x corresponde à letra a, y
à letra b e z à letra c. A solução é tomar o resto da divisão euclidiana de c(λ)
por 26. No caso da letra x, c(x) = 26 e o resto da divisão por 26 é 0, portanto
c(x) = 0 = a. Analogamente, c(y) = 1 = b e c(z) = 2 = c. Para decodificar a
cifra de César usamos a função inversa d[c(λ)] = c(λ) − 3 e novamente temos
problemas para decodifcar c(λ) = 0, c(λ) = 1 e c(λ) = 2 cujas decodificações
seriam inteiros negativos. Como vemos, as funções adequadas para cifrar e
decifrar usando a cifra de César são as funções modulares correspondentes
c(λ) = (λ + 3) mod 26 e d[c(λ)] = [c(λ) − 3] mod 26.
Podemos generalizar o procedimento utilizado na cifra de César. Fi-
xado um número natural k (denominado chave), 0 < k < 26, a cifragem
é feita substituindo cada letra por aquela k posições adiante no alfabeto.
Em termos de aritmética modular isto significa adicionar, módulo 26, k ao
número λ correspondente a letra a ser cifrada, ou seja
c(λ) = (λ + k) mod 26
A decifragem consiste em substitiuir cada letra do texto cifrado por

aquela obtida retrocedendo k posições no alfabeto. Em termos de aritmética
modular significa subtrair, módulo 26, k de c(λ), ou seja
d[c(λ)] = [c(λ) − k] mod 26 = (λ + k) − k mod 26 = λ

O ponto fraco da cifra de César está no pequeno número de chaves

possı́veis (25 apenas), o que permite a quebra do código por tentativas.
Vamos exemplificar cifrando ”legiões romanas” com a chave k = 11.
Após a supressão de espaços e acentos temos ”legioesromanas”. Substituindo
as letras por números temos 11-04-06-08-14-04-18-17-14-12-00-13-00-18.
c(11) = (11 + 11) mod 26 =⇒ c(11) = 22 mod 26 = 22
c(04) = (04 + 11) mod 26 =⇒ c(04) = 15 mod 26 = 15
c(06) = (06 + 11) mod 26 =⇒ c(06) = 17 mod 26 = 17
c(08) = (08 + 11) mod 26 =⇒ c(08) = 19 mod 26 = 19
c(14) = (14 + 11) mod 26 =⇒ c(14) = 25 mod 26 = 25
c(04) = (04 + 11) mod 26 =⇒ c(04) = 15 mod 26 = 15
c(18) = (18 + 11) mod 26 =⇒ c(18) = 29 ≡ 03 mod 26 = 03
c(17) = (17 + 11) mod 26 =⇒ c(17) = 28 ≡ 02 mod 26 = 02
c(14) = (14 + 11) mod 26 =⇒ c(14) = 25 mod 26 = 25
c(12) = (12 + 11) mod 26 =⇒ c(12) = 23 mod 26 = 23
c(00) = (00 + 11) mod 26 =⇒ c(00) = 11 mod 26 = 11
c(13) = (13 + 11) mod 26 =⇒ c(13) = 24 mod 26 = 24
c(00) = (00 + 11) mod 26 =⇒ c(00) = 11 mod 26 = 11
c(18) = (18 + 11) mod 26 =⇒ c(18) = 29 ≡ 03 mod 26 = 03
Obtemos assim 22-15-17-19-25-15-03-02-25-23-11-24-11-03 e a men-

sagem cifrada é ”w p r t z p d c z x l y l d”. Agora vamos decifrar a mensagem.
d(22) = (22 − 11) mod 26 =⇒ d(22) = 11 mod 26 = 11
d(15) = (15 − 11) mod 26 =⇒ d(15) = 04 mod 26 = 04

d(17) = (17 − 11) mod 26 =⇒ d(17) = 06 mod 26 = 06
d(19) = (19 − 11) mod 26 =⇒ d(19) = 08 mod 26 = 08
d(25) = (25 − 11) mod 26 =⇒ d(25) = 14 mod 26 = 14
d(15) = (15 − 11) mod 26 =⇒ d(15) = 04 mod 26 = 04
d(03) = (03 − 11) mod 26 =⇒ d(03) = −8 ≡ 18 mod 26 = 18
d(02) = (02 − 11) mod 26 =⇒ d(02) = −9 ≡ 17 mod 26 = 17
d(25) = (25 − 11) mod 26 =⇒ d(25) = 14 mod 26 = 14
d(23) = (23 − 11) mod 26 =⇒ d(23) = 12 mod 26 = 12
d(11) = (11 − 11) mod 26 =⇒ d(11) = 00 mod 26 = 00
d(24) = (24 − 11) mod 26 =⇒ d(24) = 13 mod 26 = 13
d(11) = (11 − 11) mod 26 =⇒ d(11) = 00 mod 26 = 00
d(03) = (03 − 11) mod 26 =⇒ d(03) = −8 ≡ 18 mod 26 = 18
Como esperado obtemos 11-04-06-08-14-04-18-17-14-12-00-13-00-18,

que corresponde à mensagem original ”legiões romanas”.
2.1.3 A Cifra de Vigenère

A cifra de César e suas variações são denominadas cifras de subs-
tituição monoalfabética, ou seja, cada letra é substituı́da sempre por um
mesmo sı́mbolo em toda a mensagem. Existe uma correspondência biunı́voca
entre o alfabeto original e o alfabeto de substituição. Para decifrar a mensa-
gem, basta substituir cada sı́mbolo pela letra correspondente do alfabeto ori-
ginal. Este tipo de cifra foi eficaz por muito tempo, mas com o surgimento da
técnica de análise de frequência, descoberta pelos árabes, tornou-se insegura.
A análise de frequência baseia-se no fato de que cada letra aparece com uma
determinada frequência em textos de um certo idioma. Assim, contando-se
os sı́mbolos na mensagem cifrada e sabendo-se o idioma do texto original,
basta comparar a frequência dos sı́mbolos com uma tabela de frequência pre-
viamente elaborada (a partir de um livro, por exemplo). A técnica é muito
eficaz quando se tem um texto relativamente longo ou muitos textos curtos,

mas pode não ser possı́vel aplicá-la a um único texto muito pequeno. Abaixo
mostramos a tabela de frequência do idioma português.
Português
A 14,63 E 12,57 I 6,18 M 4,74 Q 1,20 U 4,63 Y 0,01
B 1,04 F 1,02 J 0,40 N 5,05 R 6,53 V 1,67 Z 0,47
C 3,88 G 1,30 K 0,02 O 10,73 S 7,81 W 0,01 - -,-
D 4,99 H 1,28 L 2,78 P 2,52 T 4,74 X 0,21 - -,-
Tabela de frequência de letras do idioma português (em porcentagem).
Para escapar à análise de frequência, Blaise de Vigenère (1523-1596),

diplomata e criptógrafo francês, utilizou uma cifra polialfabética que leva
o seu nome. A cifra de Vigenère consiste numa tabela com 26 alfabetos
dispostos horizontalmente e, a partir do segundo, deslocados uma letra para
a direita em relação ao anterior. Ou seja, cada alfabeto começa por uma
letra diferente. O primeiro começa pela letra A, o segundo pela letra B, e
assim por diante.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A a b c d e f g h i j k l m n o p q r s t u v w x y z
B b c d e f g h i j k l m n o p q r s t u v w x y z a
C c d e f g h i j k l m n o p q r s t u v w x y z a b
D d e f g h i j k l m n o p q r s t u v w x y z a b c
E e f g h i j k l m n o p q r s t u v w x y z a b c d
F f g h i j k l m n o p q r s t u v w x y z a b c d e
G g h i j k l m n o p q r s t u v w x y z a b c d e f
H h i j k l m n o p q r s t u v w x y z a b c d e f g
I i j k l m n o p q r s t u v w x y z a b c d e f g h
J j k l m n o p q r s t u v w x y z a b c d e f g h i
K k l m n o p q r s t u v w x y z a b c d e f g h i j
L l m n o p q r s t u v w x y z a b c d e f g h i j k
M m n o p q r s t u v w x y z a b c d e f g h i j k l
N n o p q r s t u v w x y z a b c d e f g h i j k l m
O o p q r s t u v w x y z a b c d e f g h i j k l m n
P p q r s t u v w x y z a b c d e f g h i j k l m n o
Q q r s t u v w x y z a b c d e f g h i j k l m n o p
R r s t u v w x y z a b c d e f g h i j k l m n o p q
S s t u v w x y z a b c d e f g h i j k l m n o p q r
T t u v w x y z a b c d e f g h i j k l m n o p q r s
U u v w x y z a b c d e f g h i j k l m n o p q r s t
V v w x y z a b c d e f g h i j k l m n o p q r s t u
W w x y z a b c d e f g h i j k l m n o p q r s t u v
X x y z a b c d e f g h i j k l m n o p q r s t u v w
Y y z a b c d e f g h i j k l m n o p q r s t u v w x
Z z a b c d e f g h i j k l m n o p q r s t u v w x y
Alfabetos da cifra de Vigenère.
O método consiste em usar uma palavra ou frase como chave. Cada

letra da chave indica um alfabeto horizontal a ser usado na substituição
de uma letra do texto original. Vejamos um exemplo. Se queremos cifrar a
palavra ”tempestade” usando como chave a palavra RAIO procedemos assim:
buscamos a letra no cruzamento da coluna do T com a linha do R e achamos

que é k ;
buscamos a letra no cruzamento da coluna do E com a linha do A e achamos
que é e;
buscamos a letra no cruzamento da coluna do M com a linha do I e achamos
que é u;
buscamos a letra no cruzamento da coluna do P com a linha do O e achamos
que é d ;
buscamos a letra no cruzamento da coluna do E com a linha do R e achamos
que é v ;
buscamos a letra no cruzamento da coluna do S com a linha do A e achamos

que é s;
buscamos a letra no cruzamento da coluna do T com a linha do I e achamos
que é b;
buscamos a letra no cruzamento da coluna do A com a linha do O e achamos
que é o;
buscamos a letra no cruzamento da coluna do D com a linha do R e achamos
que é u;
buscamos a letra no cruzamento da coluna do E com a linha do A e achamos
que é e.
A mensagem cifrada é então ”k e u d v s b o u e”. A mensagem

agora não é vulnerável à análise de frequência já que uma mesma letra do
texto original é substituı́da por mais de uma no texto cifrado (t, por exemplo,
é cifrado como k e b e a letra e é cifrada como e e v ).
Para decifrar ”k e u d v s b o u e”, procuramos a letra k na linha R
e substituı́mos pela letra no topo da coluna, ou seja T ; localizamos a letra
e na linha A e substituı́mos pela letra no topo da coluna, E ; procuramos a
letra u na linha I e substituı́mos pela letra no topo da coluna, M ; buscamos
a letra d na linha O e substituı́mos pela primeira letra da coluna, ou seja P.
Repetindo o procedimento até a última letra do texto cifrado, obte-
mos o texto original ”tempestade”.
2.1.4 A Matemática da Cifra de Vigenère

Em termos de aritmética modular a cifra de Vigenère é semelhante
à cifra de César. Só que agora a chave é constituı́da de um conjunto de
naturais k = {k1 , k2 , . . . , km }, 0 ≤ ki < 26, i = 1, 2, 3, . . . , m. Uma mensagem
n1 n2 . . . np é criptografada segundo o procedimento:
C(n1 ) = (n1 + k1 ) mod 26;
C(n2 ) = (n2 + k2 ) mod 26;
...
C(ni−1 ) = (ni−1 + km ) mod 26;
C(ni ) = (ni + k1 ) mod 26;
C(ni+1 ) = (ni+1 + k2 ) mod 26;
...
C(np ) = (np + kj ) mod 26, para 1 ≤ j ≤ m;
Vamos exemplificar cifrando e decifrando a frase ’Os números gover-

nam o mundo.’ atribuı́da ao geômetra grego Pitágoras. Inicialmente fazemos
uma pré-codificação (para dificultar a quebra do código) onde os dı́grafos, se
existirem, são substituı́dos por uma letra apenas (”ss”por ”s”, por exemplo)
e também os acentos e os espaços entre as palavras são suprimidos. Como
resultado obtemos o bloco único: ’osnumerosgovernamomundo’. A cada le-
tra do alfabeto fazemos corresponder um número do seguinte modo: a = 0,
b = 1, c = 2, e assim por diante. Temos agora o bloco numérico (separamos
com hı́fen para facilitar o entendimento do exemplo),
14-18-13-20-12-04-17-14-18-06-14-21-04-17-13-00-12-14-12-20-13-03-14
Usaremos como chave para cifragem a palavra cateto, que conver-

tida em números é k = {02, 00, 19, 04, 19, 14}. Agora fazemos a codificação:
c(14) = (14 + 02) mod 26 = 16 mod 26 = 16

c(18) = (18 + 00) mod 26 = 18 mod 26 = 18
c(13) = (13 + 19) mod 26 = 32 mod 26 = 06
c(20) = (20 + 04) mod 26 = 24 mod 26 = 24
c(12) = (12 + 19) mod 26 = 31 mod 26 = 05
c(04) = (04 + 14) mod 26 = 18 mod 26 = 18
c(17) = (17 + 02) mod 26 = 19 mod 26 = 19

c(14) = (14 + 00) mod 26 = 14 mod 26 = 14
c(18) = (18 + 19) mod 26 = 37 mod 26 = 11
c(06) = (06 + 04) mod 26 = 10 mod 26 = 10
c(14) = (14 + 19) mod 26 = 33 mod 26 = 07
c(21) = (21 + 14) mod 26 = 35 mod 26 = 09
c(04) = (04 + 02) mod 26 = 06 mod 26 = 06
c(17) = (17 + 00) mod 26 = 17 mod 26 = 17
c(13) = (13 + 19) mod 26 = 32 mod 26 = 06
c(00) = (00 + 04) mod 26 = 04 mod 26 = 04
c(12) = (12 + 19) mod 26 = 31 mod 26 = 05
c(14) = (14 + 14) mod 26 = 28 mod 26 = 02
c(12) = (12 + 02) mod 26 = 14 mod 26 = 14
c(20) = (20 + 00) mod 26 = 20 mod 26 = 20
c(13) = (13 + 19) mod 26 = 32 mod 26 = 06
c(03) = (03 + 04) mod 26 = 07 mod 26 = 07
c(14) = (14 + 19) mod 26 = 33 mod 26 = 07
A sequência obtida,
16-18-06-24-05-18-19-14-11-10-07-09-06-17-06-04-05-02-14-20-06-07-07,
corresponde à mensagem encriptada ”q s g y f s t o l k h j g r g e f c o

u g h h”.
Deciframos com a mesma chave k = {02, 00, 19, 04, 19, 14}, obser-
vando que, se a = c(λ) − ki < 0, então d[c(λ)] = a mod 26 = (a + 26) mod
26.
d(16) = (16 − 02) mod 26 = 14 mod 26 =⇒ d(16) = 14

d(18) = (18 − 00) mod 26 = 18 mod 26 =⇒ d(18) = 18
d(06) = (06−19) mod 26 = −13 mod 26 ≡ (−13+26) mod 26 =⇒ d(06) = 13
d(24) = (24 − 04) mod 26 = 20 mod 26 =⇒ d(24) = 20

d(05) = (05−19) mod 26 = −14 mod 26 ≡ (−14+26) mod 26 =⇒ d(05) = 12
d(18) = (18 − 14) mod 26 = 04 mod 26 =⇒ d(18) = 04
d(19) = (19 − 02) mod 26 = 17 mod 26 =⇒ d(19) = 17
d(14) = (14 − 00) mod 26 = 14 mod 26 =⇒ d(14) = 14
d(11) = (11−19) mod 26 = −08 mod 26 ≡ (−8+26) mod 26 =⇒ d(11) = 18
d(10) = (10 − 04) mod 26 = 06 mod 26 =⇒ d(10) = 06
d(07) = (07−19) mod 26 = −12 mod 26 ≡ (−12+26) mod 26 =⇒ d(07) = 14
d(09) = (09−14) mod 26 = −05 mod 26 ≡ (−5+26) mod 26 =⇒ d(09) = 21
d(06) = (06 − 02) mod 26 = 04 mod 26 =⇒ d(06) = 04
d(17) = (17 − 00) mod 26 = 17 mod 26 =⇒ d(17) = 17
d(06) = (06−19) mod 26 = −13 mod 26 ≡ (−13+26) mod 26 =⇒ d(06) = 13
d(04) = (04 − 04) mod 26 = 00 mod 26 =⇒ d(04) = 00
d(05) = (05−19) mod 26 = −14 mod 26 ≡ (−14+26) mod 26 =⇒ d(05) = 12
d(02) = (02−14) mod 26 = −12 mod 26 ≡ (−12+26) mod 26 =⇒ d(02) = 14
d(14) = (14 − 02) mod 26 = 12 mod 26 =⇒ d(14) = 12
d(20) = (20 − 00) mod 26 = 20 mod 26 =⇒ d(20) = 20
d(06) = (06−19) mod 26 = −13 mod 26 ≡ (−13+26) mod 26 =⇒ d(06) = 13
d(07) = (07 − 04) mod 26 = 03 mod 26 =⇒ d(07) = 03
d(07) = (07−19) mod 26 = −12 mod 26 ≡ (−12+26) mod 26 =⇒ d(07) = 14
O resultado é o bloco original
14-18-13-20-12-04-17-14-18-06-14-21-04-17-13-00-12-14-12-20-13-03-14
cuja mensagem é a frase de Pitágoras ”Os números governam o mundo”.

2.1.5 Cifrário de Hill

Essa cifra foi proposta em 1920 pelo americano Lester S. Hill (1891-
1961) e utiliza o produto de matrizes. Vejamos como funciona. Primeira-
mente escolhe-se uma matriz quadrada K de ordem n com entradas kij tais
que, 0 ≤ kij < 26,  
k11 k12 . . . k1n
 k21 k22 . . . k2n 
K =  ..
 
.. . . .. 
 . . . . 
kn1 kn2 . . . knn
Para cifrar um texto original X, primeiro quebramos o texto em
blocos de n letras (x1 x2 x3 . . . xn ). Em seguida, obtemos o bloco cifrado
(y1 y2 y3 . . . yn ) efetuando o produto matricial abaixo, módulo 26.
   
y1   x1
 y2  k11 k12 . . . k1n 
  k21 k22 . . . k2n   x2 


 y3     x3 
= . .. . . . 
 ..   .. . ..   .. 
 
 .  .  . 
kn1 kn2 . . . knn
yn xn
Caso o número de caracteres de X não seja múltiplo de n, comple-

tamos o último bloco com letras ao acaso. Também costuma-se acrescentar
de 1 a n − 1 letras aleatoriamente no final da mensagem cifrada para difi-
cultar que se descubra o valor de n (se isso não fosse feito toda mensagem
cifrada teria um número de caracteres múltiplo de n, o que facilitaria a vida
do criptoanalista de plantão).
A mensagem original X é resgatada fazendo o produto da matriz
−1
K , inversa de K mod 26, por cada bloco cifrado (y1 y2 y3 . . . yn ), operando
módulo 26. Obviamente, a matriz K deve ser invertı́vel em Z26 , o que é
verdadeiro se o determinante de K possuir inverso em Z26 . Por exemplo, a
matriz

8 12
A=
3 9
cujo determinante é (det A) mod 26 = 36 mod 26 = 10 não é invertı́vel em

Z26 , pois 10 e 26 não são co-primos e, portanto, 10 não tem inverso módulo
26. Já a matriz

7 5
B=
3 8
cujo determinante (det B) mod 26 = 41 mod 26 = 15 é co-primo de 26,

possui inversa

−1 4 17
B =
5 23
A frase ”A terra é azul”dita pelo cosmonauta soviético Iuri A. Ga-

garin (1934-1968), quando avistou nosso planeta pela janela de sua cápsula
espacial, será usada como exemplo da cifra de Hill. Utilizaremos n = 2 e a
matriz

7 5
K=
3 8
como chave.
Na pré-codificação temos ’ateraeazul’ que corresponde a

00-19-04-17-00-04-00-25-20-11 utilizando a convenção estabelecida anterior-
mente para representação do alfabeto numericamente. Formamos então os
blocos:

00 04 00 00 20
X1 = X2 = X3 = X4 = X5 =
19 17 04 25 11
O próximo passo é a cifragem. Primeiro fazemos Yi0 = KXi , i ∈

{1, 2, 3, 4, 5}. Depois calculamos Yi = Yi0 mod 26.

7 5 00 95
Y10 = =
3 8 19 152

7 5 04 113
Y20 = =
3 8 17 148

7 5 00 20
Y30 = =
3 8 04 32

7 5 00 125
Y40 = =
3 8 25 200

7 5 20 195
Y50 = =
3 8 11 148
Y1 = Y10 mod 26
17
Y1 =
22
Y2 = Y20 mod 26
09
Y2 =
18
Y3 = Y30 mod 26
20
Y3 =
06
Y4 = Y40 mod 26
21
Y4 =
18
Y5 = Y50 mod 26
13
Y5 =
18
Então a mensagem cifrada é 17-22-09-18-20-06-21-12-13-18. Em le-

tras: ’r w j s u g v m n s’.

−1 4 17
Vamos agora decifrar com a matriz inversa K = . Pri-
5 23
meiramente, calculamos Xi0 = K −1 Yi . Depois Xi = Xi0 mod 26, com 00 ≤
Xi ≤ 25. Vejamos,

17 09 20 21 13
Y1 = Y2 = Y3 = Y4 = Y5 =
22 18 06 18 18

4 17 17 442
X10 = =
5 23 22 591

4 17 09 342
X20 = =
5 23 18 459

4 17 20 182
X30 = =
5 23 06 238

4 17 21 390
X40 = =
5 23 18 519

4 17 13 358
X50 = =
5 23 18 479
X1 = X10 mod 26
00
X1 =
19
X2 = X20 mod 26
04
X2 =
17
X3 = X30 mod 26
00
X3 =
04
X4 = X40 mod 26
00
X4 =
25
X5 = X50 mod 26
20
X5 =
11
O resultado 00-19-04-17-00-04-00-25-20-11, em letras ’ateraeazul’ é a men-

sagem original ”A terra é azul”.
2.2. CRIPTOGRAFIA DE CHAVE PÚBLICA 47
2.2 Criptografia de Chave Pública

2.2.1 Introdução
Ao final da segunda guerra mundial e durante o perı́odo da chamada
guerra fria, a criptografia consistia em métodos sofisticados de substituição
utilizando uma chave previamente acertada entre o emissor e o receptor, que
a utilizava para inverter o processo e decodificar a mensagem. Para que
fosse eficiente, era necessário que o número de chaves disponı́veis fosse muito
grande, de modo que mesmo conhecendo o processo de substituição não fosse
viável para um espião descobrir a chave por tentativas, mantendo seguro o
conteúdo do texto cifrado. O problema com esse procedimento é que emis-
sor e receptor precisavam combinar de antemão qual a chave a ser utilizada.
Além disso, para que houvesse máxima segurança, essa chave deveria ser
alterada com muita frequência, sendo ideal que fosse trocada a cada mensa-
gem. Com isso chegou-se a um beco sem saı́da, pois o problema da troca de
chaves de maneira segura parecia não ter solução. A frequência das trocas, a
quantidade de chaves a ser distribuı́da e as distâncias entre os destinatários
eram os obstáculos, além da insegurança causada pelo manuseio dessas cha-
ves por terceiros. Durante a segunda guerra mundial os alemães usaram a
máquina Enigma nos campos de batalha para codificar suas comunicações,
transmitindo via rádio a chave juntamente com a mensagem cifrada. Foi isso
que permitiu que os criptoanalistas poloneses, liderados por Marian Rejewski
(1905-1980) iniciassem a quebra do código da Enigma. A partir da análise
de muitas mensagens interceptadas e da comparação entre elas foi possı́vel
descobrir em que parte do texto cifrado se encontrava a chave o que deu inı́cio
à quebra do código. Quando a Polônia foi invadida pelas tropas alemãs, os
poloneses já haviam comunicado seus avanços em relação à Enigma aos fran-
ceses e ingleses, que dessa forma não tiveram de começar do zero. Em 1939,
os criptoanalistas ingleses instalaram em Bletchley Park, Buckinghamshire,
a Escola de Cifras e Códigos do Governo, onde trabalharam intensamente na
quebra do código da Enigma. Foi lá que o brilhante Alan Turing (1912-1954),
matemático e criptoanalista inglês, teve a idéia do que chamou ”máquina uni-
versal de Turing” precursora do conceito do computador moderno.
Na segunda metade do século XX, o desenvolvimento tecnológico,
com o advento do computador e das telecomunicações, acarretou um au-
mento no fluxo de informações sigilosas entre governos, empresas e pessoas
o que pressionou ainda mais a logı́stica da distribuição das chaves. A troca
de chaves por meios convencionais, assim como as mensagens, estava su-
jeita a interceptação. Nessa época, as chaves eram entregues diretamente
por bancos, governos e militares aos destinatários, utilizando mensageiros de
confiança. Era uma falha de segurança, pois as chaves podiam cair em mãos
indevidas e além disso, esse expediente consumia cada vez mais recursos. O
grande problema dos criptógrafos nessa época era a logı́stica da distribuição
de chaves, que infelizmente parecia ser insolucionável.
A crença geral era de que o problema da troca de chaves de ma-
neira segura não tivesse solução. Foi então que, em 1976, os pesquisadores
Whitfield Diffie e Martin Hellman publicaram um artigo onde descreveram
um método pelo qual emissor e receptor podem combinar uma chave utili-
zando um canal inseguro, que mesmo sujeito a interceptação não permite a
dedução da chave por um espião. O método de Diffie-Hellman mostrou que
o problema da distribuição de chaves podia ser superado e lançou as bases
da criptografia de chave pública, amplamente utilizada nas transações pela
internet.
Diffie e Hellman encontraram na aritmética modular a solução que
buscavam. Quando calculamos valores de uma função f (x) usando a aritmética
normal, esta função pode apresentar um comportamento previsı́vel (cres-
cente, decrescente, periódica, etc.). Agora, se calculamos os mesmos valores
para a função modular correspondente a f (x), ou seja, calculamos f (x) mod
m, m ∈ N, m > 1, observamos que, em geral, a função modular não apre-
senta regularidade. Isto significa que com a aritmética normal, conhecendo
f (x) podemos inferir x por tentativas ou usando métodos computacionais,
se necessário, baseados no comportamento da função. O mesmo não ocorre
com a maioria das chamadas funções modulares, onde o conhecimento de
f (x) não ajuda em nada na dedução de x. Um exemplo disso é a função ex-
ponencial y = ax . Na tabela 1 a seguir calculamos alguns valores da função
exponencial de base a = 3 e na tabela 2 fazemos o mesmo para esta função
módulo 7.
Aritmética Normal
x 1 2 3 4 5 6
x
f (x) = 3 3 9 27 81 243 729
Tabela 1
Aritmética Modular
x 1 2 3 4 5 6
x
f (x) = 3 mod 7 3 2 6 4 5 1
Tabela 2
Podemos observar na tabela 1 que a função é crescente, ou seja, os valo-

res de f (x) aumentam à medida que x aumenta. Não ocorre nada semelhante
no caso da função modular (tabela 2). Os valores de f (x) neste caso variam
aleatoriamente.
2.2.2 O Método de Diffie-Hellman
Considere o conjunto Zp \{0} dos inteiros módulo p menos o zero, sendo

p um número primo, que representaremos por Z∗p :
Z∗p = {1, . . . , p − 1}.
Este conjunto, com a operação de multiplicação usual constitui uma

estrutura algébrica denominada grupo, no caso o grupo multiplicativo dos
inteiros módulo p. Existem elementos g em Z∗p para os quais {g i mod
p : i = 1, . . . , p − 1} = Z∗p , ou seja, elementos que geram o conjunto. Tais ele-
mentos g são chamados geradores de Z∗p . Por exemplo, 3 ∈ Z∗7 é um gerador,
pois {3i mod 7 : i = 1, . . . , 6} = Z∗7 , como podemos ver abaixo:
36 = 729 ≡ 1 mod 7;
32 = 9 ≡ 2 mod 7;
31 = 3 mod 7;
34 = 81 ≡ 4 mod 7;
35 = 243 ≡ 5 mod 7;
33 = 27 ≡ 6 mod 7.
Pois bem, suponha que Alice e Bob queiram combinar uma chave
por telefone. Primeiro um liga para o outro e eles escolhem um número primo
p e um gerador g do grupo multiplicativo Z∗p . Depois cada um faz o seguinte:
1) Alice escolhe um número xA , 1 < xA < p − 1, e calcula yA = g xA

mod p. Depois ela informa o resultado yA para Bob, mantendo em segredo
o valor de xA .
2) Bob, por sua vez, faz o mesmo escolhendo um número xB , 1 <

xB < p − 1, e calculando yB = g xB mod p. Ele informa apenas o resultado
yB para Alice mantendo secreto o valor de xB .
3) Agora ambos calculam a chave:
Alice toma o valor de yB informado por Bob e faz
(yB )xA mod p = (g xB )xA mod p = g xB xA mod p = K
Bob por sua vez calcula
(yA )xB mod p = (g xA )xB mod p = g xA xB mod p = K
obtendo a mesma chave K.
Por exemplo, Bob liga para Alice e eles combinam usar o primo
p = 7 e o gerador g = 3. Então Alice pode escolher, por exemplo, xA = 2 e
Bob, xB = 3. Vejamos:
1) Alice calcula yA = 32 mod 7 = 2 =⇒ yA = 2.
2) Bob calcula yB = 33 mod 7 = 6 =⇒ yB = 6.
Eles voltam a se falar por telefone e trocam os valores de yA = 2 e yB = 6.
3) Agora Alice faz (yB )xA = 62 = 36 mod 7 = 1 e obtém a chave K = 1.
4) Bob por sua vez calcula (yA )xB = 23 = 8 mod 7 = 1, obtendo a

mesma chave K = 1.
Evidentemente, escolhemos o primo p muito grande, de modo que o

grupo Z∗ppossua muitos elementos x, tais que 1 < x < p − 1.
Vamos analisar agora o problema da escuta. Caso alguém inter-

cepte a ligação de Alice e Bob vai ter acesso ao primo p, ao gerador g, a yA e
a yB . Escolhendo p suficientemente grande, o número de possibilidades para
1 < x < p − 1 é também muito elevado. Além disso, é muito difı́cil calcular
a inversa da função exponencial módulo p (x = logg y mod p), pois como
sabemos a função exponencial módulo p não tem comportamento previsı́vel.
Desse modo, não é possı́vel para um espião determinar xA nem xB e, mesmo
utilizando um canal inseguro, o método permite a Alice e Bob acertar uma
chave criptográfica com segurança.
Capı́tulo 3
Criptografia RSA
3.1 Introdução
Em 1977 Ronald Rivest, Adi Shamir e Leonard Adleman apresen-
taram à comunidade cientı́fica o método que ficaria conhecido como cripto-
grafia RSA. A criptografia de chave pública RSA tornou-se a mais utilizada
na internet em transações comerciais e na codificação de mensagens que cir-
culam pela rede. O método se baseia em uma função exponencial modular
C(X) = X e mod n. Nesta função, X é o bloco a ser codificado (um número
inteiro, obtido após um processo de pré-codificação que consiste na subs-
tituição das letras da mensagem original por números, encadeados em um
único grande número que depois é quebrado em blocos cujo valor é menor do
que n). O par de números (n, e) é a chave pública do destinatário da mensa-
gem, n consiste no produto de dois números primos p e q muito grandes, da
ordem de 100 dı́gitos cada enquanto e é um expoente escolhido de maneira
que exista o seu inverso d mod (p − 1) · (q − 1). Obviamente, os números
primos p e q são de conhecimento exclusivo do usuário do RSA, que os uti-
liza para obter o expoente d com o qual decodifica as mensagens que recebe
segundo a fórmula D(C) = C d mod n. Uma vez obtido o expoente d, os
primos p e q não são mais necessários, podendo ser descartados. A segurança
do método consiste na dificuldade de fatorar o produto de números primos
muito grandes (da ordem de 100 dı́gitos decimais), mesmo tendo à disposição
recursos computacionais. Para se ter uma idéia, o tempo estimado para a
fatoração do produto de dois primos dessa magnitude supera, em muito, a
idade do universo e só poderia ser realizada num tempo aceitável por um
computador quântico, uma tecnologia que ainda está mais no plano teórico
do que no operacional.
53
54 CAPÍTULO 3. CRIPTOGRAFIA RSA
Uma ressalva deve ser feita, com relação à segurança, no que diz
respeito a mensagens falsas que podem ser enviadas para o usuário do RSA.
Como a chave pública (n, e) é acessı́vel a qualquer pessoa, as mensagens
recebidas devem ser verificadas quanto à origem. Isto é feito utilizando-se
uma assinatura digital. O remetente também deve possuir uma chave pública
(n0 , e0 ) e uma chave privada d0 , com a qual assina digitalmente a mensagem,
ou seja, o remetente cifra a assinatura digital com sua chave privada d0 , à
qual somente ele tem acesso, e o destinatário decifra a assinatura digital com
a chave pública (n0 , e0 ) do remetente. Procedendo assim, fica garantida a
procedência da mensagem.
3.2 A matemática do RSA

O primeiro passo para implementar o método criptográfico RSA é a
escolha dos primos p e q. Por questões de segurança, é preciso que esses pri-
mos sejam grandes, da ordem de 100 dı́gitos decimais. Isto é feito gerando-se
aleatoriamente números inteiros ı́mpares de 100 dı́gitos e testando sua pri-
malidade por meios computacionais. Felizmente, a densidade de números
primos entre os inteiros de 100 dı́gitos é bastante grande e os algoritmos para
teste de primalidade oferecem uma margem de erro muito pequena. Podemos
demonstrar a alta densidade de primos de 100 dı́gitos decimais a partir do
”Teorema dos Números Primos”que diz que, sendo π(n) o número de inteiros
menores do que n e primos relativos de n (dois inteiros são primos relativos
quando o máximo divisor comum entre eles é 1), então
n
π(n) ∼ , quando n −→ ∞
ln n
Se n é um inteiro com 100 dı́gitos então 1099 ≤ n < 10100 , o que

significa que o número de primos no intervalo acima é aproximadamente,
10100 1099
π(10100 ) − π(1099 ) = − ≈ 4 × 1097
ln 10100 ln 1099
Para se ter uma idéia da magnitude desse número vamos fazer cálculos.
A densidade do universo é equivalente a aproximadamente 5,9 prótons por
metro cúbico 1 enquanto o raio do universo conhecido é atualmente estimado
1
http://map.gsfc.nasa.gov/universe/uni matter.html 02/03/2013 23H29min.
3.2. A MATEMÁTICA DO RSA 55
em aproximadamente 14 bilhões de anos-luz 2 . A luz percorre 3 × 108 metros

a cada segundo, o que significa que o raio do universo, em metros, é
(14 × 109 ) × (60 × 60 × 24 × 365) × (3 × 108 ) ≈ 1, 3 × 1026
Considerando um universo esférico, o seu volume seria
4 3 4
πr = π(1, 3 × 1026 )3 ≈ 1079 m3
3 3
Pois bem, sendo a densidade do universo aproximadamente 6 prótons
por m3 terı́amos 6 × 1079 ≈ 1080 prótons no universo.
Comparando este resultado com o obtido para o número de primos
com 100 dı́gitos decimais, observamos que o número de primos é 1017 vezes
maior. Portanto existe uma quantidade enorme de primos de 100 dı́gitos
decimais disponı́veis. A densidade de primos no intervalo de 1099 a 10100 é
4 1
4 × 1097 ÷ (10100 − 1099 ) ≈ =
1000 250
Para obter primos dessa ordem gera-se aleatoriamente um inteiro

ı́mpar com 100 dı́gitos e testa-se a sua primalidade utilizando recursos com-
putacionais. O algoritmo mais utilizado para testar a primalidade é o Miller-
Rabin que retorna se o inteiro é ou não primo com probabilidade de erro de
1/4 se o resultado for positivo para número primo. O que se faz é testar várias
vezes o número e a cada vez que o algoritmo retorna que ele é primo a pro-
babilidade de erro diminui. Para n rodadas, a probabilidade de erro é (1/4)n .
De posse dos primos p e q, calculamos n = pq e o valor da função φ

de Euler para n, que no caso é φ(n) = (p − 1)(q − 1). Testamos até obter um
valor e, tal que o mdc [e, φ(n)] = 1. O par de números (n, e) constituirá a
chave pública necessária para encriptar as mensagens endereçadas ao usuário
do RSA. Em seguida, calculamos d = e−1 mod φ(n) que é a chave privada
necessária para decriptar as mensagens recebidas e que deve ser mantida em
sigilo, assim como os primos p e q. Quem quiser mandar uma mensagem
usará a chave pública (n, e) da seguinte maneira. Após uma pré-codificação
a mensagem é convertida em um único bloco numérico N = N1 N2 N3 . . . Nk ,
com Ni < n, para i = 1, 2, 3, . . . k (Ni deve ser menor do que n para que
o resultado da decodificação seja exatamente a mensagem original) ao qual
aplicamos
C(Ni ) = Nie mod n
2
http://map.gsfc.nasa.gov/universe/uni expansion.html 03/03/2013 00H09min.
A mensagem recebida C(N ) é então decodificada fazendo
D[C(Ni )] = C(Ni )d mod n = (Nie )d mod n = Ni mod n = Ni
Observação: A pré-codificação de N é feita utilizando-se a tabela AS-

CII (American Standard Code for Information Interchange). Esta tabela
é composta por 256 números binários de 8 dı́gitos cada e contém as letras
maiúsculas e minúsculas (na base 10, respectivamente de 65 até 90 e de 97 a
122), além dos caracteres alfabéticos acentuados, sinais de pontuação, etc.
decimal binário hexadecimal sı́mbolo

56 00111000 38 8
57 00111001 39 9
58 00111010 3A :
59 00111011 3B ;
60 00111100 3C <
61 00111101 3D =
62 00111110 3E >
63 00111111 3F ?
64 01000000 40 @
65 01000001 41 A
66 01000010 42 B
Uma parte da tabela ASCII.
3.3 Uma Função e dois Teoremas Importan-

tes
A quantidade de números inteiros menores e relativamente primos
de um inteiro a, a > 1, é dada por uma função chamada função fi de Eu-
ler, φ : N∗ −→ N, onde N∗ denota o conjunto dos naturais menos o zero
(N∗ = N \ {0}). Para a, b ∈ N∗ e mdc(a, b) = 1, a função φ é multiplica-
tiva, ou seja, φ(ab) = φ(a) · φ(b). Sendo p primo, φ(p) = p − 1. Assim, o
número de inteiros menores e relativamente primos de n = pq, p e q primos,
é φ(n) = (p − 1) · (q − 1).
3.3. UMA FUNÇÃO E DOIS TEOREMAS IMPORTANTES 57
Teorema 2. Sejam a, b ∈ N∗ e mdc(a, b) = 1. Então φ(ab) = φ(a) · φ(b).
Demonstração. Observe que mdc(c, ab) = 1, se, e somente se, mdc(c, a) = 1

e mdc(c, b) = 1. Portanto, dispondo os números de 1 a ab na tabela abaixo
com b linhas e a colunas devemos verificar quais são co-primos de a e de b.
1 2 3 ... a−1 a
a+1 a+2 a+3 ... a + (a − 1) 2a
2a + 1 2a + 2 2a + 3 ... 2a + (a − 1) 3a
.. .. .. .. ..
. . . . .
(b − 1)a + 1 (b − 1)a + 2 (b − 1)a + 3 ... (b − 1)a + (a − 1) ba
O elementos das colunas são da forma ka + j com 0 ≤ k ≤ b − 1 e

1 ≤ j ≤ a. Se j não for co-primo de a então todos os elementos da coluna j
também não são co-primos de a. Portanto os elementos co-primos de a estão
nas φ(a) colunas restantes.
Como mdc(a, b) = 1, os elementos das colunas j formam um sistema
completo de resı́duos módulo b,
ka + j ≡ k 0 a + j mod b ⇐⇒ ka ≡ k 0 a mod b ⇐⇒ k ≡ k 0 mod b
e portanto, φ(b) deles são co-primos de b. Logo, o número de elementos co-

primos de a e co-primos de b na tabela é φ(a) · φ(b).
Teorema 3 (Fermat). Sejam p um número primo, r e s côngruos módulo

(p − 1).
1. Se um número inteiro a não for divisı́vel por p, então
ap−1 ≡ 1 mod p
ar ≡ as mod p
2. Se r > 0 e s > 0 então, para todo a ∈ Z
ar ≡ as mod p.
Demonstração. 1. Considere o conjunto Z∗p = {1, 2, . . . , p − 1} dos números

x ∈ Zp que são primos com p. Como p não divide a, se x ∈ Z∗p , então ax mod
p ∈ Z∗p . Isto significa que a função f : Z∗p −→ Z∗p , tal que f (x) = ax mod p é
injetora e o conjunto imagem é um rearranjo de Z∗p . Portanto, são iguais os
produtos
f (1) × f (2) × . . . × f (p − 1) = 1 × 2 × . . . × (p − 1),
ou seja,
1a × 2a × . . . × (p − 1)a mod p = 1 × 2 × . . . × (p − 1) mod p
Multiplicando ambos os lados pelos inversos módulo p de 2 a p − 1, obtemos
ap−1 mod p = 1 =⇒ ap−1 ≡ 1 mod p.
Agora
r ≡ s mod (p − 1) =⇒ r = k(p − 1) + s
e
ar ≡ ak(p−1)+s ≡ (ap−1 )k · as ≡ 1k · as ≡ as mod p =⇒ ar ≡ as mod p.
2. Se p não divide a, já mostramos que ar ≡ as mod p. Se p divide a, as

potências de a módulo p de expoente negativo não existem (pois a ≡ 0 mod
p) e as potências de a módulo p de expoente positivo são congruentes a zero
módulo p, ou seja, são iguais. Isso prova que ar ≡ as mod p para qualquer a
inteiro.
Teorema 4 (Euler). Sejam n ≥ 2, n ∈ Z , r e s côngruos módulo φ(n).
1. Se a e n forem primos entre si,
aφ(n) ≡ 1 mod n
ar ≡ as mod n
2. Se n for produto de primos distintos, r > 0 e s > 0, então
ar ≡ as mod n, ∀a ∈ Z.
3.3. UMA FUNÇÃO E DOIS TEOREMAS IMPORTANTES 59
Demonstração. 1. A demonstração é análoga à do Teorema de Fermat.

Sendo Z∗n o conjunto dos elementos inversı́veis de Zn , a função f : Z∗n −→ Z∗n ,
tal que f (x) = ax mod n é injetora e o conjunto {ax mod n : x ∈ Z∗n } é igual
a Z∗n . Desse modo, são iguais os produtos
   
Y Y
 ax mod n =  x mod n
x ∈ Z∗n x ∈ Z∗n
ou seja,
   
Y Y
aφ(n)  x mod n =  x mod n
x ∈ Z∗n x ∈ Z∗n
Multiplicando ambos os lados da igualdade acima pelos inversos x−1 mod n

de cada x ∈ Z∗n , obtemos
aφ(n) mod n = 1 =⇒ aφ(n) ≡ 1 mod n
2. Se n = p1 p2 . . . pk , onde pi 6= pj , ∀ i, j com 1 ≤ i, j ≤ k
φ(n) = φ(p1 )φ(p2 ) . . . φ(pk ) = (p1 − 1)(p2 − 1) . . . (pk − 1)
Como r ≡ s mod φ(n), então r ≡ s mod (pi − 1), i = 1, 2, ..., k. Pelo

teorema de Fermat, r ≡ s mod (pi − 1) implica ar ≡ as mod pi , ou seja,
pi divide ar − as , para i = 1, 2, ..., k o que significa que n divide ar − as e
consequentemente ar ≡ as mod n.
A função de Euler, bem como o teorema de Fermat e o teorema
de Euler são muito importantes. O teorema de Fermat facilita o cálculo de
potências módulo n, n inteiro positivo, e o teorema de Euler (generalização
do teorema de Fermat) está no centro do método criptográfico RSA.
3.4 Como Funciona a Criptografia RSA

Neste ponto, podemos entender como tudo funciona:
1) Primeiro escolhemos dois primos p e q suficientemente grandes.
2) Depois fazemos n = pq e calculamos k = φ(n) = (p − 1)(q − 1).
3) Escolhemos ao acaso um inteiro e, 1 < e < k e verificamos

se mdc(e, k) = 1, o que significa que e tem inverso módulo k.
Caso contrário, escolhemos outro e até encontrar um que seja in-
vertı́vel módulo k.
4) Calculamos d = e−1 mod k. A chave secreta utilizada pelo

usuário do RSA para decifrar as mensagens que recebe é um in-
teiro positivo d, tal que ed ≡ 1 mod k, onde k = φ(n). Ou seja,
d é o inverso de e módulo k. Tomando e, tal que mdc(e, k) = 1,
existem d e b inteiros, tais que
de + bk = 1 =⇒ de mod k + bk mod k = 1 =⇒
de mod k = 1 =⇒ d = e−1 mod k.
Observação: Os inteiros d e b acima são determinados aplicando

o algoritmo estendido de Euclides a e e k e fazendo substituições
sucessivas nas igualdades até obter a equação de + bk = 1. Para
valores elevados de e e k, como ocorre na criptografia RSA, usa-
mos um programa para realizar o algoritmo estendido de Euclides.
Devido à velocidade de processamento e do algoritmo, o resultado
é obtido em segundos.
5) Divulgamos a chave pública (n, e) na internet e mantemos em

sigilo a chave privada d e também os primos p e q, que podem até
ser esquecidos.
Vejamos como utilizamos o RSA para cifrar e decifrar:
Para cifrar:
1) Transformamos a mensagem em blocos numéricos (menores

do que n, para que a decifragem retorne o bloco cifrado e não
3.4. COMO FUNCIONA A CRIPTOGRAFIA RSA 61
outro congruente a ele módulo n).
2) Ciframos um bloco M calculando c(M ) = M e mod n.
Para decifrar:
1) O destinatário, de posse da chave privada d, calcula para cada

bloco c(M ), d[c(M )] = [c(M )]d mod n e fazendo isso obtém a
mensagem original.
d[c(M )] = [c(M )]d mod n = (M e )d mod n = M ed mod n ≡
M s·φ(n)+1 mod n = [(M φ(n) )s · M 1 ] mod n ≡
(1s · M ) mod n = M mod n = M .
3.4.1 Algoritmo Estendido de Euclides
Lema 1 (Euclides). Sejam a, b, n ∈ N tais que a < na < b. Então mdc(a, b) =

mdc(a, b − na).
Demonstração. Seja d = mdc(a, b − na). Como d|a e d|(b − na), segue que
d|b = b − na + na. Portanto d é divisor comum de a e b. Seja c um divisor
comum de a e b, então c é divisor comum de a e b − na , logo, c|d o que prova
que d = mdc(a, b).
Algoritmo Estendido de Euclides
Dados a, b ∈ N, podemos supor a ≤ b. Então, se a = 1, ou a = b, ou

a|b, o mdc(a, b) = a. Supondo que 1 < a < b e a 6 | b, podemos escrever
b = aq1 + r1 , com r1 < a.
Se r1 |a, pelo lema de Euclides r1 = mdc(a, r1 ) = mdc(a, b − aq1 ) =

mdc(a, b). Caso contrário, fazemos a divisão de a por r1 , obtendo
a = r1 q2 + r2 , com r2 < r1 .
Novamente, se r2 |r1 , então
r2 = mdc(r1 , r2 ) = mdc(r1 , a − r1 q2 ) = mdc(r1 , a) = mdc(a, r1 ) =

mdc(a, b − aq1 ) = mdc(a, b).
Caso contrário, fazemos a divisão de r1 por r2 , obtendo
r1 = q3 r2 + r3 , com r3 < r2 .
Repetimos o processo até obter o mdc(a, b). Pela Propriedade da

Boa Ordem, a sequência dos naturais a > r1 > r2 > r3 > . . . possui mı́nimo,
ou seja, para algum n, temos que rn |rn−1 e o mdc(a, b) = rn . A partir das
equações obtidas no algoritmo estendido de Euclides pode-se obter inteiros
x e y, tais que
ax + by = mdc(a, b)
A existência de x e y que satisfazem a equação é garantida pelo
Teorema de Bézout, cuja demonstração pode ser encontrada na referência
bibliográfica [4].
Exemplo
Obter o inverso de 18, módulo 1247.
Solução
1247 = 69 × 18 + 5 (1)
18 = 3 × 5 + 3 (2)
5 = 1 × 3 + 2 (3)
3 = 1 × 2 + 1 (4)
2 = 2 × 1 + 0 =⇒ mdc(1247, 18) = 1
De (4): 3 − 2 = 1 (5)
De (3): 2 = 5 − 3, substituindo em (5): 3 − (5 − 3) = 1 =⇒

2 × 3 − 5 = 1 (6)
De (2): 3 = 18 − 3 × 5, substituindo em (6): 2 × (18 − 3 × 5) − 5 = 1 =⇒

2 × 18 − 7 × 5 = 1 (7)
De (1): 5 = 1247−69×18, substituindo em (7): 2×18−7×(1247−69×18) = 1
=⇒ (2 + 7 × 69) × 18 − 7 × 1247 = 485 × 18 − 7 × 1247 = 1

3.5. EXEMPLIFICANDO O USO DA RSA 63
Aplicando módulo, temos
(485 × 18) mod 1247 − (7 × 1247) mod 1247 = 1 =⇒ (485 × 18) mod 1247 = 1
=⇒ 18−1 mod 1247 = 485
Exemplo
Calcular d, tal que 19d = 1 mod 120 (observe que mdc(19, 120) = 1).
Solução
Aplicando o algoritmo estendido de Euclides obtemos as igualdades:
120 = 19 × 6 + 6 =⇒ 6 = 120 − 19 × 6 (1)
19 = 6 × 3 + 1 =⇒ 19 − 6 × 3 = 1 (2)
Substituindo (1) em (2),
19 − (120 − 19 × 6) × 3 = 1 =⇒ 19 × 19 − 120 × 3 = 1 (3)
Agora aplicamos módulo em (3) para achar o inverso de 19 mod 120.
(19 × 19) mod 120 − (120 × 3) mod 120 = 1 =⇒
(19 × 19) mod 120 = 1 =⇒ 19−1 mod 120 = 19.
Ou seja, 19 é seu próprio inverso módulo 120.
3.5 Exemplificando o uso da RSA

Como exemplo do uso da criptografia RSA, vamos codificar e de-
codificar a palavra ”enigma”. Para fins didáticos e para facilitar as contas
utilizaremos números primos bem pequenos. Tomando p = 11 e q = 13,
o valor de n será n = 11 · 13 = 143. Associamos a cada letra do alfabeto
um número inteiro a partir de 10 (a = 10, b = 11, c = 12 e assim por di-

ante). Neste caso, ficamos com ”enigma”= 142318162210, que dividiremos
em blocos. O tamanho de cada bloco a ser cifrado, assim como o tamanho
de cada bloco a ser decifrado é estabelecido previamente. Para garantir que
cada bloco a ser cifrado seja menor do que n, tomamos os blocos com um
algarismo decimal a menos do que n. No caso do exemplo, como n = 143 tem
três algarismos decimais, dividimos a mensagem em blocos com dois dı́gitos
apenas. Ficamos então com os blocos 14-23-18-16-22-10. Estes blocos depois
de cifrados podem ter de um a três algarismos, então convencionamos que os
blocos cifrados terão todos o tamanho de n, no caso, três algarismos. Aqueles
com dois ou um algarismo apenas serão completados com zeros à esquerda,
que serão desprezados quando for feita a decifração.
Para cifrar cada bloco X usamos a fórmula C(X) = X e mod 143.

Para isso, escolhemos o expoente e = 7 (co-primo de φ(n) = 10 · 12 = 120,
logo possui inverso módulo φ(n)). A chave pública é então (n, e) = (143, 7).
Primeiro, escrevemos o expoente e = 7 na base 2:
7 = 1112 = 22 + 21 + 20 = 4 + 2 + 1
Ciframos os dois primeiros blocos, os demais são cifrados de modo

análogo:
C(14) = 147 mod 143 = (144+2+1 ) mod 143 =
(144 × 142 × 14) mod 143 =
(144 mod 143 × 142 mod 143 × 14 mod 143) mod 143
Mas,
142 mod 143 = 196 mod 143 = 53
144 mod 143 = (142 )2 mod 143 = (142 mod 143)2 mod 143 =
532 mod 143 = 2809 mod 143 = 92

Então,
C(14) = (92 × 53 × 14) mod 143 =
[(92 × 53) mod 143 × 14] mod 143 =
[(4876 mod 143) × 14] mod 143 =
(14 × 14) mod 143 = 196 mod 143 = 53
C(14) = 53;
C(23) = 237 mod 143 = (234+2+1 ) mod 143 =
(234 × 232 × 23) mod 143 =
(234 mod 143 × 232 mod 143 × 23 mod 143) mod 143
Mas,
232 mod 143 = 529 mod 143 = 100
234 mod 143 = (232 )2 mod 143 = (232 mod 143)2 mod 143 =
1002 mod 143 = 10000 mod 143 = 133
Então,
C(23) = (133 × 100 × 23) mod 143 =
[(133 × 100) mod 143 × 23] mod 143 =
[(13300 mod 143) × 23] mod 143 =
(1 × 23) mod 143 = 23 mod 143 = 23
C(23) = 23.
O resultado, cifrando-se todos os blocos, é 53-23-138-3-22-10.

De acordo com a convenção estabelecida para o tamanho dos blocos,

acrescentamos zeros à esquerda aos blocos com menos de três algarismos de-
cimais e a mensagem transmitida é 053-023-138-003-022-010.
Vejamos agora como decifrar a mensagem. Primeiramente, calcu-

lamos d, tal que 7d = 1 mod k, k = φ(143), usando o algoritmo estendido de
Euclides.
e=7 k = φ(143) = 120
120 = 17 × 7 + 1 =⇒ −17 × 7 + 1 × 120 = 1 =⇒
(−17 × 7) mod 120 + (1 × 120) mod 120 = 1 =⇒
(−17 × 7) mod 120 = 1 =⇒ 7−1 mod 120 = −17 ≡ 103 =⇒
d = 103
A função modular que decodifica é, então, D(C) = C 103 mod 143.
Para decifrar, primeiro escrevemos o expoente d = 103 na base 2:
103 = 11001112 = 26 + 25 + 22 + 21 + 20 = 64 + 32 + 4 + 2 + 1
A mensagem recebida é quebrada em blocos com a mesma quanti-

dade de dı́gitos de n (três, no exemplo) e os zeros à esquerda nestes blocos
são desprezados. A seguir, deciframos os dois primeiros blocos de 053-023-
138-003-022-010, os demais são decifrados de maneira análoga:
D(53) = 53103 mod 143 = (5364+32+4+2+1 ) mod 143 =
(5364 × 5332 × 534 × 532 × 53) mod 143 =
[(5364 mod 143) × (5332 mod 143) × (534 mod 143) × (532 mod 143) ×
(53 mod 143)] mod 143
532 mod 143 = 2809 mod 143 = 92

534 mod 143 = (532 )2 mod 143 = (532 mod 143)2 mod 143 =
922 mod 143 = 8464 mod 143 = 27
538 mod 143 = (534 )2 mod 143 = (534 mod 143)2 mod 143 =
272 mod 143 = 729 mod 143 = 14
5316 mod 143 = (538 )2 mod 143 = (538 mod 143)2 mod 143 =
142 mod 143 = 196 mod 143 = 53
5332 mod 143 = (5316 )2 mod 143 = (5316 mod 143)2 mod 143 =
532 mod 143 = 2809 mod 143 = 92
5364 mod 143 = (5332 )2 mod 143 = (5332 mod 143)2 mod 143 =
922 mod 143 = 8464 mod 143 = 27
D(53) = (27 × 92 × 27 × 92 × 53) mod 143 =⇒
D(53) = [(27 × 92) mod 143 × (27 × 92)mod 143 × 53] mod 143 =⇒
D(53) = [(2484 mod 143) × (2484 mod 143) × 53] mod 143 =⇒
D(53) = (53 × 53 × 53) mod 143 =
D(53) = [(53 × 53) mod 143 × 53] mod 143 =⇒
D(53) = [(2809 mod 143) × 53] mod 143 =⇒
D(53) = (92 × 53) mod 143 =⇒
D(53) = 4876 mod 143 = 14
D(53) = 14;
D(23) = 23103 mod 143 = (2364+32+4+2+1 ) mod 143 =
(2364 × 2332 × 234 × 232 × 23) mod 143 =
[(2364 mod 143) × (2332 mod 143) × (234 mod 143) × (232 mod 143) ×
(23 mod 143)] mod 143
232 mod 143 = 529 mod 143 = 100
234 mod 143 = (232 )2 mod 143 = (232 mod 143)2 mod 143 =
1002 mod 143 = 10000 mod 143 = 133
238 mod 143 = (234 )2 mod 143 = (234 mod 143)2 mod 143 =
1332 mod 143 = 17689 mod 143 = 100
2316 mod 143 = (238 )2 mod 143 = (238 mod 143)2 mod 143 =
1002 mod 143 = 10000 mod 143 = 133
2332 mod 143 = (2316 )2 mod 143 = (2316 mod 143)2 mod 143 =
1332 mod 143 = 17689 mod 143 = 100
2364 mod 143 = (2332 )2 mod 143 = (2332 mod 143)2 mod 143 =
1002 mod 143 = 10000 mod 143 = 133
D(23) = (133 × 100 × 133 × 100 × 23) mod 143 =⇒
D(23) = [(133 × 100) mod 143 × (133 × 100) mod 143 × 23] mod 143 =⇒
D(23) = [(13300 mod 143) × (13300 mod 143) × 23] mod 143 =⇒
D(23) = (1 × 1 × 23) mod 143 = 23 mod 143 = 23
D(23) = 23.
Com a decifração dos blocos 053-023-138-003-022-010 obtemos 14-

23-18-16-22-10, que agora podemos converter novamente para texto desfa-
zendo o que foi feito na etapa de pré-codificação, ou seja, juntamos tudo
(142318162210), e substituimos cada dois algarismos a partir da esquerda
pela letra correspondente na seguinte convenção: a=10, b=11, c=12, . . . ,
z=35. O resultado final, como esperávamos, é a palavra ”enigma”.
Capı́tulo 4
Aplicações da Aritmética
Modular
Vamos supor que você deseja fazer um depósito em dinheiro no caixa

eletrônico do seu banco. Para isso é necessário que você informe os dados
da conta-corrente, isto é, o número da agência com dı́gito e o número da
conta-corrente com o dı́gito verificador. Pois bem, a função do dı́gito de
verificação é evitar erros. Se você trocar um número na conta-corrente ou na
agência o dı́gito respectivo não vai conferir e o caixa eletrônico não aceitará o
depósito. Isto fará com que você verifique novamente os dados e evitará que
o depósito entre na conta de outra pessoa causando transtornos para você e
para o banco.
Em muitos documentos (RG, CPF, CNPJ, Tı́tulo de Eleitor, etc.)
os dı́gitos de verificação estão presentes e quando preenchemos um formulário
eletrônico (um cadastro on-line por exemplo), esses dı́gitos são checados para
evitar possı́veis erros de digitação. O cálculo do dı́gito nestes casos é feito
utilizando a aritmética modular.
4.1 Cálculo do dı́gito do CPF e do CNPJ
Vamos calcular os dı́gitos verificadores de um CPF (Cadastro de

Pessoas Fı́sicas) hipotético 234.400.562−??.
Devemos, primeiramente, multiplicar cada algarismo da direita para
a esquerda respectivamente por 9, 8, 7, 6, 5, 4, 3, 2, 1 e 0.
71
72 CAPÍTULO 4. APLICAÇÕES DA ARITMÉTICA MODULAR
2 3 4 4 0 0 5 6 2
× × × × × × × × ×
1 2 3 4 5 6 7 8 9
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
2 6 12 16 0 0 35 48 18
Depois somamos os resultados e calculamos o total módulo 11 (se o
resultado for 10 consideramos 0 como dı́gito).
2 + 6 + 12 + 16 + 0 + 0 + 35 + 48 + 18 = 137 −→ 137 mod 11 = 5
O primeiro dı́gito é, portanto, igual a 5.
Para calcular o segundo dı́gito, incluı́mos o primeiro dı́gito junto

com os demais algarimos do CPF e repetimos o procedimento acima.
2 3 4 4 0 0 5 6 2 5
× × × × × × × × × ×
0 1 2 3 4 5 6 7 8 9
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
0 3 8 12 0 0 30 42 16 45
Depois somamos os resultados e calculamos o total módulo 11.
0 + 3 + 8 + 12 + 0 + 0 + 30 + 42 + 16 + 45 = 156 −→ 156 mod 11 = 2
O segundo dı́gito é 2 e o CPF completo com os dois dı́gitos veri-

ficadores é 234.400.562−52. Os dı́gitos de verificação calculados tomando-se
o resto da divisão por 11 são conhecidos como DV módulo 11.
Os dı́gitos do CNPJ (Cadastro Nacional de Pessoas Jurı́dicas) também

são calculados módulo 11. Vamos calcular os dı́gitos do CNPJ hipotético
22.345.293/0001−??.
Multiplicamos da direita para a esquerda cada algarismo respecti-
vamente por 9, 8, 7, 6, 5, 4, 3, 2, 9, 8, 7, 6 e 5. E procedemos de maneira
análoga ao que foi feito para o CPF.
2 2 3 4 5 2 9 3 0 0 0 1
× × × × × × × × × × × ×
6 7 8 9 2 3 4 5 6 7 8 9
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
12 14 24 36 10 6 36 15 0 0 0 9
4.2. CÁLCULO DO DÍGITO DO RG 73
12 + 14 + 24 + 36 + 10 + 6 + 36 + 15 + 0 + 0 + 0 + 9 = 162 −→ 162 mod 11 = 8
Agora incluı́mos o primeiro dı́gito calculado com os demais e re-

petimos o procedimento para encontrar o segundo dı́gito
2 2 3 4 5 2 9 3 0 0 0 1 8
× × × × × × × × × × × × ×
5 6 7 8 9 2 3 4 5 6 7 8 9
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
10 12 21 32 45 4 27 12 0 0 0 8 72
10 + 12 + 21 + 32 + 45 + 4 + 27 + 12 + 0 + 0 + 0 + 8 + 72 = 243 −→
243 mod 11 = 1
O CNPJ com DV é 22.345.293/0001−81.
4.2 Cálculo do dı́gito do RG

As carteiras de identidade emitidas no estado de São Paulo possuem
dı́gito verificador também módulo 11. Como exemplo, vamos calcular o DV
do RG 11.966.756−?.
Multiplicamos da direita para a esquerda cada algarismo respecti-

vamente por 2, 3, 4, 5, 6, 7, 8 e 9. A seguir, somamos os resultados e
calculamos o total módulo 11.
1 1 9 6 6 7 5 6
× × × × × × × ×
9 8 7 6 5 4 3 2
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
9 8 63 36 30 28 15 12
9 + 8 + 63 + 36 + 30 + 28 + 15 + 12 = 201 −→ 201 mod 11 = 3
O RG com dı́gito é 11.966.756−3.

No caso das contas-correntes e boletos de cobrança, os bancos

utilizam o módulo 11 ou o módulo 10 (com variações, como por exemplo
começar da esquerda para a direita ou utilizar X no lugar do dı́gito 0). Não
há um padrão e o algoritmo varia de banco para banco.
Exercı́cio 1. Calcule os dı́gitos verificadores do seu CPF utilizando os pro-

cedimentos descritos acima.
4.3 Cálculo do dı́gito ISBN-13

Outro importante dı́gito de verificação é o do ISBN-13 (International
Standard Book Number ), número padrão internacional de livros. Vejamos
como o dı́gito ISBN-13 é calculado tomando como exemplo o livro ”The Code
Book” do renomado autor Simon Singh. O código sem o dı́gito de verificação
é ISBN 978-85-01-05598-?(onde colocamos o sı́mbolo de interrogação no lugar
do dı́gito verificador).
9 7 8 8 5 0 1 0 5 5 9 8
× × × × × × × × × × × ×
1 3 1 3 1 3 1 3 1 3 1 3
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
9 21 8 24 5 0 1 0 5 15 9 24
9 + 21 + 8 + 24 + 5 + 0 + 1 + 0 + 5 + 15 + 9 + 24 = 121
Agora calculamos 121 mod 10 = 1. Por fim, o dı́gito verificador

do ISBN-13 é obtido subtraindo o resultado de 10. No caso, 10 − 1 = 9 é o
dı́gito. Portanto o ISBN-13 do livro de Singh é ISBN 978-85-01-05598-9, o
que é possı́vel confirmar olhando em um exemplar.
4.4. CRITÉRIOS DE DIVISIBILIDADE 75
4.4 Critérios de Divisibilidade

Usando artimética modular podemos deduzir os critérios de divisi-
bilidade. Vejamos como isto é feito.
4.4.1 Divisibilidade por 3

Sabemos que um número inteiro α é divisı́vel por 3 quando a soma
de seus algarimos for divisı́vel por 3. Por exemplo, 915 é divisı́vel por 3 por-
que a soma 9 + 1 + 5 de seus algarismos é 15, que é divisı́vel por 3. Vejamos
como chegar a essa conclusão usando a aritmética modular.
Seja α = an an−1 . . . a1 a0 (onde os ai são os algarimos do sistema

decimal de numeração), um número inteiro qualquer. Se α for divisı́vel por
3, então α satisfaz a equação α mod 3 = 0. Usando a expansão decimal de
α, temos
α mod 3 = 0 ⇐⇒ (an an−1 . . . a1 a0 ) mod 3 = 0 ⇐⇒
(an 10n + an−1 10n−1 + . . . + a1 10 + a0 ) mod 3 = 0 ⇐⇒
[an (999 . . . 9 + 1) + an−1 (99 . . . 9 + 1) + . . . + a1 (9 + 1) + a0 ]

mod 3 = 0 ⇐⇒
[(999 . . . 9an + 99 . . . 9an−1 + . . . + 9a1 ) + (an + an−1 + . . . + a1 + a0 )]

mod 3 = 0 ⇐⇒
[(999 . . . 9an + 99 . . . 9an−1 + . . . + 9a1 ) mod 3 + (an + an−1 + . . . +

a1 + a0 ) mod 3] mod 3 = 0 ⇐⇒
(0 + 0 + . . . + 0) + (an + an−1 + . . . + a1 + a0 ) mod 3 = 0 ⇐⇒
(an + an−1 + . . . + a1 + a0 ) mod 3 = 0
Portanto, α mod 3 = 0 ⇐⇒ (an +an−1 +. . .+a1 +a0 ) mod 3 = 0.


A divisibilidade de um número por 4 se verifica quando os dois
últimos algarimos desse número à direita (algarismo das dezenas e algarismo
das unidades) formam um número divisı́vel por 4. Por exemplo, 12928 é
divisı́vel por 4 porque 28 é divisı́vel por 4 (28 = 4 · 7). Assim como 1700
também o é, pois 00 é divisı́vel por 4.
Novamente, seja α = an an−1 . . . a1 a0 um número inteiro qualquer.

Vamos resolver α mod 4 = 0, usando a expansão decimal de α,
α mod 4 = 0 ⇐⇒ (an an−1 . . . a1 a0 ) mod 4 = 0 ⇐⇒
(an 10n + an−1 10n−1 + . . . + a1 10 + a0 ) mod 4 = 0 ⇐⇒
[(an 10n−2 +an−1 10n−3 +. . .+a2 )×100+a1 10+a0 ] mod 4 = 0 ⇐⇒
[(an 10n−2 + an−1 10n−3 + . . . + a2 ) × 100] mod 4 +

(a1 10 + a0 ) mod 4 = 0 ⇐⇒
(an 10n−2 + an−1 10n−3 + . . . + a2 ) mod 4×100 mod 4 +

(a1 10 + a0 ) mod 4= 0 ⇐⇒
Como 100 mod 4 = 0,
[(an 10n−2 + an−1 10n−3 + . . . + a2 ) mod 4]×0+

(a1 10 + a0 ) mod 4= 0 ⇐⇒
(a1 10 + a0 ) mod 4 = 0
Portanto
α mod 4 = 0 ⇐⇒ (a1 10 + a0 ) mod 4 = 0 ⇐⇒
(a1 a0 ) mod 4 = 0
Desse modo, justificamos o critério de divisibilidade por 4.


Procedemos de maneira semelhante aos casos anteriores para justi-
ficar o critério de divisibilidade por 5. Seja α = an an−1 . . . a1 a0 ,
α mod 5 = 0 ⇐⇒ (an an−1 . . . a1 a0 ) mod 5 = 0 ⇐⇒
(an 10n + an−1 10n−1 + . . . + a1 10 + a0 ) mod 5 = 0 ⇐⇒
[(an 10n−1 +an−1 10n−2 +. . .+a2 10+a1 )×10+a0 ] mod 5 = 0 ⇐⇒
[(an 10n−1 + an−1 10n−2 + . . . + a2 10 + a1 ) × 10] mod 5 +

a0 mod 5 = 0 ⇐⇒
(an 10n−1 + an−1 10n−2 + . . . + a2 10 + a1 ) mod 5 × 10 mod 5 +

a0 mod 5 = 0 ⇐⇒
Como 10 mod 5 = 0,
(an 10n−1 + an−1 10n−2 + . . . + a2 10 + a1 ) mod 5 × 0 +

a0 mod 5 = 0 ⇐⇒
a0 mod 5 = 0
Portanto,
α mod 5 = 0 ⇐⇒ a0 mod 5 = 0
Desse modo, temos
α mod 5 = 0 ⇐⇒ a0 mod 5 = 0 ⇐⇒ a0 = 5 ou a0 = 0
Justifica-se assim o critério de divisibilidade por 5.


Sabemos que um número é divisı́vel por 6 quando é par e divisı́vel
por 3. Esse é o critério de divisibilidade por 6. Mas podemos verificar a
divisibilidade por 6 de outra forma. Observe que
10 mod 6 = 4;
102 mod 6 = 100 mod 6 = 4;
103 mod 6 = (102 · 10) mod 6 = (100 mod 6) · (10 mod 6) =
4 · 4 mod 6 = 16 mod 6 = 4
Observamos que 10i ≡ 4 mod 6, para i ∈ N. Então
α = (an 10n + an−1 10n−1 + . . . + a1 10 + a0 ) mod 6 = 0 ⇐⇒
(4an + 4an−1 + . . . + 4a1 + a0 ) mod 6 = 0
Logo, α é divisı́vel por 6 se 4 · (an + an−1 + . . . + a1 ) + a0 também

for divisı́vel por 6.

Novamente, seja α = an an−1 . . . a1 a0 , então
α = an 10n + an−1 10n−1 + . . . + a1 10 + a0
Como 10 ≡ −1 mod 11 =⇒ 10k ≡ (−1)k mod 11, então
α = an 10n + an−1 10n−1 + . . . + a1 10 + a0 ≡
[an (−1)n + an−1 (−1)n−1 + . . . + a1 (−1) + a0 ] mod 11, ou seja,
α ≡ 0 mod 11 ⇐⇒
an (−1)n + an−1 (−1)n−1 + . . . + a1 (−1) + a0 ≡ 0 mod 11

Sendo assim, se n for de ordem par, por exemplo, α será divisı́vel

por onze se a soma a seguir for divisı́vel por 11
an − an−1 + an−2 + . . . + a2 − a1 + a0
Justificando a regra que diz que um número é divisı́vel por 11 se a

soma dos algarismos de ordem ı́mpar subtraı́da da soma dos algarismos de
ordem par for divisı́vel por 11.
4.4.6 Divisibilidade por 7, 11 e 13

Fatorando 1001, obtemos 1001 = 7 · 11 · 13. Isto significa que
1001 ≡ 0 mod [7, 11, 13] =⇒ 1000 ≡ −1 mod [7, 11, 13] =⇒
103 ≡ −1 mod [7, 11, 13];
106 = (103 )2 ≡ (−1)2 ≡ 1 mod [7, 11, 13];
109 = (103 )3 ≡ (−1)3 ≡ −1 mod [7, 11, 13];

..
.
Agora,
α = an an−1 . . . a2 a1 a0 =
an 10n + an−1 10n−1 + . . . + a2 102 + a1 10 + a0 =
a2 a1 a0 + a5 a4 a3 × 103 + a8 a7 a6 × 106 + . . . ≡
a2 a1 a0 − a5 a4 a3 + a8 a7 a6 + . . .
Então o número α = an an−1 . . . a2 a1 a0 será divisı́vel por 7, 11 e 13

se o resultado a seguir:
a2 a1 a0 − a5 a4 a3 + a8 a7 a6 + . . .
também for divisı́vel por 7, 11 e 13.
4.4.7 Outros critérios de Divisibilidade

Para outros critérios de divisibilidade procedemos de maneira análoga,
utilizando a expansão decimal de α. O critério de divisibilidade por 9 é ob-
tido de maneira semelhante ao que foi feito para o 3, ou seja,
α mod 9 = 0 ⇐⇒ (an + an−1 + . . . + a1 + a0 ) mod 9 = 0.
O critério de divisibilidade por 8 é semelhante ao que foi feito para

o 4, sendo que
α mod 8 = 0 ⇐⇒ (a2 102 + a1 10 + a0 ) mod 8 = 0 ⇐⇒
(a2 a1 a0 ) mod 8 = 0.
O critérios de divisibilidade por 2 e por 10 seguem o modelo da di-

visibilidade por 5, sendo que
α mod 2 = 0 ⇐⇒ a0 mod 2 = 0 e
α mod 10 = 0 ⇐⇒ a0 mod 10 = 0.
4.5. CONSIDERAÇÕES FINAIS 81
4.5 Considerações Finais

O objetivo do presente trabalho foi apresentar a aritmética modular
de uma forma que pudesse ser objeto de estudo no ensino médio da educação
básica, ou seja, relacionada a aplicações que pudessem despertar o interesse
dos alunos desse segmento. Para tanto nos valemos da criptografia, pela aura
de mistério em que está envolvida e pela sua importância em vários momen-
tos da história. A criptografia sempre esteve presente nas relações comercias
e diplomáticas entre os paı́ses, com destaque para os grandes conflitos mun-
diais (as grandes guerras e a guerra fria) onde a segurança das comunicações
foi de vital importância.
Ainda hoje esse ramo da matemática é largamente utilizado para ga-
rantir a privacidade das comunicações no mundo globalizado, especialmente
na internet com as chamadas cifras de chave pública.
Na abordagem do assunto, utilizamos exemplos de cifras de fácil
manipulação pelos alunos, como as cifras de César, de Vigenère e de Hill
(que envolve matrizes) procurando mostrar a matemática por detrás de cada
uma delas. Apresentamos também o método de Diffie-Hellman que revolu-
cionou a criptografia ao permitir a troca de chaves criptográficas com segu-
rança. A criptografia RSA, por ser de maior complexidade, pode constituir
um exercı́cio exemplar que o professor usará em sala de aula para ilustrar a
atualidade do tema e despertar o interesse pela pesquisa.
Na proposta para o ensino médio, quisemos mostrar exemplos de pro-
blemas envolvendo aritmética modular e cuja resolução está ao alcance dos
alunos. Não esgotamos as possibidades nos exemplos dados, havendo espaço
para a criação de inúmeros outros que certamente enriquecerão o conteúdo.
Exploramos também a relação da aritmética modular com as regras de di-
visibilidade e outras aplicações como o cálculo de dı́gitos de verificação de
documentos.
Atividades práticas como a cifragem e a decifragem de mensagens
entre grupos de alunos utilizando os métodos apresentados aqui, o cálculo do
dı́gito de verificação das cédulas de identidade dos alunos, a implementação
de algoritmo para cálculo de potências de expoente muito grande, usando os
recursos da sala de informática, entre outras, contribuiriam para aumentar a
participação e o interesse pelas aulas.
Referências Bibliográficas
[1] Antonio Cândido Faleiros: Criptografia, SBMAC, São Carlos (2011)
[2] Abramo Hefez: Elementos de Aritmética, SBM, Rio de Janeiro (2011)
[3] Abramo Hefez: Iniciação à Aritmética, OBMEP, Niterói (2009)
[4] César Polcino Milies Números, Uma Introdução à Matemática, Edusp,

São Paulo (2000)
[5] Ilydio P. Sá: Aritmética Modular e Algumas de suas Aplicações, in

http://magiadamatematica.com
[6] Simon Singh: O Livro dos Códigos, Record, São Paulo (2007)
[7] http://map.gsfc.nasa.gov/universe
83

AritméticaModular VF

Enviado por

Direitos autorais:

Formatos disponíveis

AritméticaModular VF

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

AritméticaModular VF

Enviado por

Direitos autorais:

Formatos disponíveis

Universidade Federal do ABC

Centro de Matemática, Computação e Cognição

Aritmética Modular e Criptografia

Jeovah Pereira de Alencar

Dissertação apresentada junto ao Programa de

Este exemplar corresponde à redação

Santo André, 22 de agosto de 2013.

Prof. Dr. Antonio Cândido Faleiros

1. Prof. Dr. Antonio Cândido Faleiros - UFABC (Presidente)

2. Prof. Dr. Adail de Castro Cavalheiro - UnB (Membro Titular)

3. Prof. Dr. Daniel Miranda Machado - UFABC (Membro Titular)

Dissertação apresentada junto ao Programa

Santo André, 27 de agosto de 2013.

Agradeço primeiramente a Deus por me conduzir até aqui, ao Pro-

1 Aritmética Modular para o Ensino Médio 13

2 Criptografia e Aritmética Modular 31

4 Aplicações da Aritmética Modular 71

Aritmética Modular para o

A aritmética modular normalmente é tratada no ensino superior.

11 mod 7 = 4, assim como 25 mod 7 = 4

Portanto, 11 e 25 são congruentes módulo 7 e representamos 11 ≡ 25

Proposição 1. Dois inteiros p e q são congruentes módulo m, m ∈ Z,

Demonstração. Sejam p = k1 m + r1 e q = k2 m + r2 , então r1 = p mod m e

(=⇒) Se p e q são congruentes módulo m, então

p ≡ q mod m =⇒ p mod m = q mod m =⇒ r1 = r2 =⇒

(⇐=) Se p − q é múltiplo de m, então

p − q = km =⇒ p = km + q =⇒ p mod m = (km + q) mod m =⇒

p mod m = km mod m + q mod m =⇒ p mod m = q mod m =⇒

Exemplo 1. Determinar o valor de x = 139 mod 11.

370 − 139 = 231 = 21 · 11

Exemplo 3. Hoje é quarta- feira, 27 de fevereiro. Pedro tem 9 anos e fará

Solução Se não temos um calendário à mão, mesmo assim podemos de-

Exemplo 4. Determine o primeiro termo (a1 ) de uma P.A. de razão 7, sa-

Solução O termo geral de uma P.A. é an = a1 + (n − 1)r, onde a1 é o

an mod r = [a1 + (n − 1)r] mod r = a1 mod r + [(n − 1)r] mod r =

an mod r = a1 mod r =⇒ an ≡ a1 mod r (∀n, n ∈ N∗ )

Como a1 < r =⇒ a1 mod r = a1 =⇒ an mod r = a1 (∀n, n ∈ N∗ )

a1 = an mod r =⇒ a1 = 21888 mod 7 =⇒ a1 = 6.

Usando agora a fórmula do termo geral da P.A. temos,

Exemplo 5. Determine o 2954o algarismo da dı́zima perı́odica gerada pela

Solução Efetuando a divisão do numerador 11 pelo denominador 7, obte-

Exemplo 6. Qual é o 1234o termo da sequência periódica abaixo?

∪, ⊂, ∩, ⊃, ∨, <, ∧, >, ∪, ⊂, ∩, ⊃, ∨, <, . . .

Solução A sequência possui oito termos distintos repetindo-se na mesma

1o termo: ∪ −→ 1 mod 8=1

Exemplo 7. Determine o algarismo das unidades de 273100 .

Solução O algarismo das unidades de qualquer número é o resto da di-

273 ≡ 3 mod 10 =⇒ 273100 ≡ 3100 mod 10 = (32 )50 mod 10 =

950 mod 10.

Como 9 ≡ −1 mod 10, temos

950 mod 10 = (−1)50 mod 10 = 1.

Portanto o algarismo das unidades de 273100 é 1.

Exemplo 8. Calcule o mdc(858, 546).

Solução O método mais eficiente para calcular o máximo divisor comum

858 mod 546 = 312

1.2 Propriedades e Operações

O conjunto Zm = {1, 2, . . . , m − 1} dos inteiros módulo m, é fechado

Dados a, b e c inteiros, então:

2) a ≡ b mod m =⇒ b ≡ a mod m; (simétrica)