Introdução à teoria dos números

8.1 Números primos 8.5 Logaritmos discretos

8.2 Teoremas de Fermat e Euler 8.6 Leitura e sites Web recomendados
8.3 Testando se o número é primo 8.7 Principais termos, questões para revisão e
problemas
8.4 O teorema chinês do resto

O diabo disse a Daniel Webster: “Dê-me uma tarefa que eu não possa executar; e eu lhe darei qual­
quer coisa no m undo que você pedir”’.
Daniel Webster: “Muito justo. Prove que\ para n maior que 2, a equação a" + b" = c" não possui
solução trivial no conjunto dos inteiros
Eles concordaram com um período de três dias para o trabalho, e o diabo desapareceu.
A o final dos três dias, o diabo se apresentou, desfigurado, mordendo seus lábios. Daniel Webster lhe
disse: “Bem, como você se saiu na minha tarefa? Conseguiu provar o teorema?”
“Não... não, eu não consegui provar”.
“Então eu posso ter o que quiser? Dinheiro? A presidência?”
“O quê? Oh, é claro... Mas, escute, se pudéssemos simplesmente provar os dois lemas a seguir...”
The mathematical Magpie, Clifton Fadiman

P O N T O S P R IN C IP A IS
♦ Um núm ero primo é um inteiro que só pode ser dividido sem resto por valores positivos e negativos de si mesmo
e por 1. Os núm eros primos desem penham um papel fundamental na Teoria dos Números e na criptografia.
♦ Dois teorem as que desem penham papéis im portantes na criptografia de chave pública são o teorem a de Fermat e
o teorem a de Euler.
♦ Um requisito im portante em diversos algoritmos criptográficos é a capacidade de escolher um núm ero primo
grande. Uma área de pesquisa contínua é o desenvolvimento de algoritmos eficientes para determ inar se um in­
teiro grande, escolhido aleatoriam ente, é um núm ero primo.
♦ Logaritmos discretos são fundam entais para diversos algoritmos de chave pública. Logaritmos discretos são
semelhantes aos logaritmos comuns, mas operam sobre a aritmética modular.

165
166 CRIPTOGRAFIA E SEGURANÇA DE REDES

Diversos conceitos da Teoria dos Números são essenciais no projeto dos algoritmos criptográficos de chave pública.
Este capítulo oferece uma visão geral dos conceitos mencionados em outros capítulos. O leitor familiarizado com
esses tópicos pode seguram ente ignorar este capítulo.
Assim como o Capítulo 4, este capítulo inclui diversos exemplos, cada um dos quais destacados em uma caixa
sombreada.

8.1 NÚMEROS PRIMOS1

Uma questão fundam ental da Teoria dos Números é o estudo dos números primos. Na realidade, livros inteiros foram
escritos sobre o assunto (por exemplo, [CRAN01], [RIBE96]). Nesta seção oferecemos uma visão geral relevante às
questões deste livro.
U m inteiro /; > 1 é um núm ero primo se e som ente se seus únicos divisores 2 * forem ± 1 e ± p. Os números primos
desem penham um papel im portante na Teoria dos Números e nas técnicas explicadas neste capítulo. A Tabela 8.1
mostra os primos menores que 2000. Observe o modo como os primos são distribuídos. Em particular, observe a quan­
tidade de primos em cada intervalo de cem números.
Q ualquer inteiro a > 1 pode ser fatorado de uma forma exclusiva como

a = p f p f ■■■p '!' ( 8. 1)

onde /?, < P 2 < ' ” < /;i sã ° núm eros primos e onde cada ai é um inteiro positivo. Isso é conhecido como teorem a fun­
dam ental da aritmética; uma prova poderá ser encontrada em qualquer texto sobre Teoria dos Números.

91 = 7 X 13
3600 = 2 4 X 32 X 52
11011 = 7 X l l 2 x 13

É útil, para o texto a seguir, expressar isso de outra maneira. Se P é o conjunto de todos os núm eros primos, então
qualquer inteiro positivo a pode ser escrito exclusivamente da seguinte forma:

a = Y l Pap onde cada aj 0

p el>

O lado direito é o produto sobre todos os números primos possíveis /;; para qualquer valor em particular de a, a maio­
ria dos expoentes ap será 0 .
O valor de qualquer inteiro positivo dado pode ser especificado simplesmente listando-se todos os expoentes
diferentes de zero na formulação a seguir.

O inteiro 1 2 é representado por {a2 = 2 , = 1}.

O inteiro 18 é representado por {a2 — 1 , tf3 = 2 }.
O inteiro 91 é representado por {tf7 = 1, tf13 = 1}.

A m ultiplicação de dois núm eros é equivalente à adição dos expoentes correspondentes. D ados
a = Y l P°P' b = IT
Pbp >defina k = ab. Sabemos que o inteiro k pode ser expresso como o produto de potências
pe? peP
de primos: k = Y Í P p- Segue-se que k = a + b para todo p g P.
pe?

1. Nesta seção, a m enos que observado de outra forma, lidam os apenas com inteiros não negativos. O uso de inteiros negativos não intro­
duziria diferenças essenciais.
2. Lcm bre-sc. conform e explicado no Capítulo 4, de que o inteiro a c considerado um divisor do inteiro b se não houver resto na divisão. De
m odo equivalente, dizem os que o divide b.
 .
r* c r c r C '. c r o> c r r* o
o o c r c r Tf « r. r - r - co Gv Gv Ov
o o C" o o O ' & o o o O ' s> o

c r r - r - c r r - Gv Gv
o — c r VO vO r* r -
cc cc 8 co oS co co co co co co §8

o c r c r r* c r o r - c r r - Gv
o r i c r Tf Tf i r • r r - co cc CC
r - P i r - r - r* r* r ' r - r* r*

_ r - o c r o r - r - c r Gv c r r - CV
r i r^ c r « r, O" Gv Gv
3 3 3 \ õ õ sO vO vO vO 3 3 3 vO O vO

CT c r o c r o> o c r r*
—• r i c r Tf i r *T é vO r - r - co O '
• r «A */T £ » r » r * r * r « r » r i r

c r r* gv c r O ' r* c r Gv c r r - Gv c r
S CN r i n c r c r « r « r « r r* CO o g
Tf T f Tf Tf Tf Tf T f T f Tf Tf '4 T f T f Tf
1 ' ~ ' T—- r ~~* ’ ‘ u'"* * ' * r ""1 * '

, , ,
c r o r* c r Gv
o £ ! Gv
£ c r 3 c r c r c r 3 3 P ; 3 c r
' 1
“

*—• c r r - c r o r - Gv Gv Gv c r Gv r -
O *—• — r i r i c r c r Tf • r r - r* cc co Gv Gv
r i r i r i r i <N CM o . r i r i r i r i r j r i r i r i
1 — •— •—• •—• •—•
1 — ■

c r r* c r O f— c r c r r* c r
o s r i r i « r, o co co Gv

. T—
c r o c r o Gv c r Gv r - c r r -
s r i c r c r c r • r o vO vO cc o o o
o o o o o o o 3 o o O O o o o o
' ■ ' *—< *— *—« *—• •—• •— j ' *

r - o o r* r— r* c r r - c r r -
o •— c r Tf Tf ir. vO r - r - cc Gv Gv
o o o S i o Gv o o Gv o Gv o O

o c r r - C ' o c r r - C ' c r r* c r r -
o r i r i n c r * r i r t r r -
cc Sõ co 8 co co co co oo oo 3 cc g §8 §8

o r - c r Gv c r r - Gv c r r* r»
o s r j c r c r Tf « r « r VO O r - co Gv
r - r - r - r - r - r - r - r - r - r - r -

r* c r r - gv c r r - c r Gv c r r - c r
o o c r Tf Tf • r i r vC r - r - CO Gv
vO VO O vO vO o 3 vO vO o vO vO o vO vo vO
Primos m eno res q u e 2000

CT Ov c r r - r - c r Gv r - c r o
o O r i r i Tf Tf * r vO vO r - r* X Gv Gv
in ir, «T »O u~, i r i r « r « r * r « r T

o o c r o c r Gv r - c r Gv Gv
o o c r c r c r • r r*
Tf Tf Tf 3 Tf Tf Tf 3 3 Tf 3 3 3 Tf 3 3 3

r - c r r - r - Gv c r Gv r - c r Gv c r Gv r -
o r —• T-^ *—* c r c r Tf « r • r vO r - r - cc cc o
c r c r c r c r c r c r 3 c r c r c r c r c r c r c r c r c r

c r r - o c r o r - c r Gv r - c r c r
— r i r i r i c r c r Tf « r • r vO vO r - r - co cc Gv
r i r i n CM r i r '. CM r i r i r i r i r i r i r i r i r i

c r r - O c r r* r* Gv Gv c r r - c r Gv c r r-' Gv
o o o O 1—* r i c r c r c r Tf i r i r VC >o r* co C ' C ' C ' C '
Tabela 8.1

c r r - Gv c r Gv r* c r r - c r G** c r Gv c r GV
CM c r r , r r i r i c r c r Tf Tf Tf « r « r o o r - r - cc 00 Gv
168 c r ip t o g r a f ia e s e g u r a n ç a d e r e d e s

k = 12 X 18 = (22 X 3) X (2 x 32) = 216

k 2 = 2 + 1 = 3; *3 = 1 + 2 = 3
216 = 2 3 X 33 = 8 X 27

Isso significa, em termos dos fatores primos de tf e b, dizer que a divide fr? Q ualquer inteiro na forma p" pode
ser dividido apenas por um inteiro que seja de potência m enor ou igual ao mesmo núm ero prim o,p ’ com j < n. Assim,
podemos dizer o seguinte:

D ado a = Y L p ‘p' b = T Í P ^’- Se a\b, então a» ^ bp para to d o p .

pe. P pe P

a = 1 2 ;/> = 36; 12136

12 = 22 X 3; 36 = 2 2 X 32
í ?2 ~ 2 = /?2
a3 = 1 < 2 =
Assim, a desigualdade ap — bp é satisfeita para todos os números primos.

É fácil determ inar o máximo divisor comum3 de dois inteiros positivos se expressarmos cada inteiro como o pro­
duto dos primos.

300 = 2 2 X 3 ' X 52
18 = 2 ‘ X 32
m d c (1 8 ,300) = 21 x 31 X 5o = 6

O seguinte relacionam ento sem pre é verdadeiro:

Se k = mdc(tf, b) en tão k p = m in (a,,, bp) para to d o p

Não é fácil determ inar os fatores primos de um núm ero grande, de modo que o relacionam ento anterior não leva
diretam ente a um m étodo prático de calcular o máximo divisor comum.

8.2 TEOREMAS DE FERMAT E EULER

Dois teorem as que desem penham papéis im portantes na criptografia de chave pública são o teorem a de Ferm ât e o
teorem a de Euler.

T eorem a de F e rm â t45
O teorem a de Fermât afirma o seguinte: Se p é primo e a é um inteiro positivo não divisível por p, então

ap 1 = l( m o d p ) 82
( . )

Prova: Considere o conjunto de inteiros positivos m enores que p: { 1 ,2 ,... ,p - 1} e multiplique cada elem ento por
a, módulo p, para obter o conjunto X = [a mod p, 2a mod p , . . . (p - 1)a mod p). Nenhum dos elem entos de X é igual
a zero porque p não divide a. Além do mais, dois inteiros em X não são iguais. Para verificar isso, considere que ja =
ka( mod p) onde l < ; < & < p - l . Como a é relativam ente primo* de p, podemos eliminar a dos dois lados da
equação [ver Equação (4.3)] resultando em: j = k( mod p). Essa última igualdade é impossível, porque j e k são ambos

3. Lcm bre-se, conform e o C apítulo 4 ,d c que o máximo divisor com um dos inteiros a c />, expresso com o m dc(«,/)),c um inteiro c que divide
a e b sem resto e que qualquer divisor de a e b é um divisor de c.
4. Este ás vezes é conhecido com o pequeno teorem a de Ferm at.
5. Lembre-se, conform e o C apítulo 4. de que dois núm eros são relativam ente prim os se não tiverem fatores prim os em com um , ou seja, seu
único divisor com um c 1. Isso equivale a dizer que dois núm eros são rclativam cntc primos se seu máximo divisor comum for 1.
 CAPÍTULO 8 • INTRODUÇÃO À TEORIA DOS NÚMEROS 169

inteiros positivos menores que /;. Portanto, sabem os que os (p - 1) elem entos de X são todos inteiros positivos, sem
que dois elem entos sejam iguais. Podemos concluir que X consiste no conjunto de inteiros ( 1 , 2 , . . . , / ? - 1) em algu­
ma ordem . Multiplicar os núm eros nos dois conjuntos e apanhar o resultado mod p gera

« x 2« x . . . x (p - 1) = [(1 x 2 x . . . x (/? - l)](m o d /? )

ap- ' ( p - 1)! = {p - l) ! ( m o d p )

Podemos cancelar o term o (p - I)! porque ele é relativam ente primo de p [ver Equação (4.3)]. Isso gera a E qua­
ção (8.2).

Uma forma alternativa do teorem a de Fermat também é útil: Se p é primo e « é um inteiro positivo, então

ar = a (m o á p ) (8.3)

Observe que a primeira forma do teorem a [Equação (8.2)] requer que « seja relativam ente prim o de /?, mas esta últi­
ma forma não.

p = 5, « = 3 ap = 35 = 243 s 3 (m od 5) = «(m od p )
p = 5, « = 10 ar = IO'' = 100000 = 1 0 (m o d 5 ) = 0 (m o d 5 ) = « (m o d /?)

F unção to cien te de Euler

A ntes de apresentar o teorem a de Euler, precisamos apresentar uma quantidade im portante na Teoria dos Números,
chamada de função tociente de Euler, escrita como <£(«), definida como o núm ero de inteiros positivos m enores que
n c relativam entc primos de //. Por convenção, <£(1) = 1

D eterm ine 0(37) e <£(35).

Como 37 é primo, todos os inteiros positivos de 1 até 36 são relativam ente primos de 37. Assim, <£(37) = 36.
Para determ inar <£(35), listamos todos os inteiros positivos menores que 35 que são relativam ente primos
dele:

1 ,2 ,3 ,4 ,6 ,8 ,9 ,1 1 ,1 2 ,1 3 ,1 6 ,1 7 ,1 8 ,
19,22,23,24,26,27,29,31,32,33,34.

Existem 24 núm eros na lista, de modo que <£(35) = 24.

A Tabela 8.2 lista os 30 primeiros valores de <£(«)• O valor <£(1) não tem significado, mas é definido para que
tenha o valor 1.
D everá ficar claro que, para um núm ero primo /?,

= P ~ 1

Agora, suponha que tenham os dois núm eros primos p e q , com p ± q. Então, podemos m ostrar que, para n = p q ,

<M>0 = <Kp (i ) = H p ) x 4>{<l) = (p ~ 1) x (</ - l)

170 C R IP T O G R A F IA e seg u ra n ça de redes

Tabela 8.2 A lg u n s valores da fun ção tociente de Euler 4 > (n )

n 0 (n ) n 0 (» )

1 1 21 12
2 1 22 10
3 2 23 22
4 2 24 8
5 4 25 20
6 2 26 12
7 6 27 18
8 4 28 12
9 6 29 28
10 4 30 8

Para verificar que <£(//) = <t>(p) x <p(q), considere que o conjunto de inteiros positivos m enores que n c o conjunto
{1, (pq - 1)). Os inteiros nesse conjunto que não são relativam ente primos de n são o conjunto {/;, 2 / ; , ( q - 1)/;)
e o conjunto {q, 2 q , . . . , ( p - l)r/). Por conseguinte,

</•>(«) = (P<l - 1) - [(<7 - 1) + (P ~ 1)]

= p q - (p + q ) + 1
= (p - 1) X (<7 - 1)
= 4>{p) x 0(<7)

T eorem a de Euler
O teorem a de Euler afirma que, para cada a e n que sejam relativam ente primos:

a<f>{n) = i(n io d /? ) (8.4)

a = 3; n = 10; 0 (1 0 ) = 4 = 34 = 81 = l(m o d 10) = l(m o d n)

a = 2; n = 11; 0 (1 1 ) = 10 a ^ n) = 2 10 = 1024 = l(m o d 11) = l(m o d n )

Prova: A Equação (8.4) é verdadeira se n for primo, pois nesse caso </>(«) = (n - 1) e o teorem a de Ferm at prevalece.
Porém, ela também prevalece para qualquer inteiro n. Lembre-se de que <!>(<n) é o núm ero de inteiros positivos
menores que n que são relativam ente primos de n. Considere o conjunto desses inteiros, rotulados da seguinte forma:

R {'^ 1 » x 2> • • *» b(n) }

O u seja, cada elem ento de R é um inteiro positivo exclusivo, m enor que n com mdc(xifn) = 1. Agora, multiplique
cada elem ento por a, módulo n :

S = {( ax i m od n ), (ax2 m od At),. . . , m od n ) }

O conjunto 5 é uma perm utação de R, pela seguinte linha de raciocínio:

í. Como a é relativam ente primo de n e .v, é relativam ente primo de a í , axt também deverá ser relativam ente
primo de n. Assim, todos os membros de S são inteiros menores que n e relativam ente primos de n.
2. Existem duplicatas em S. Consulte a Equação (4.3). Sc ax, mod n = axj mod /z, então jc, = Xj.
 CAPÍTULO 8 • INTRODUÇÃO ATEORIA DOS NÚMEROS 171

Portanto,
Mn) Mn)
Q (ax, m od n) i/=t1
/=!
Mn) Mn)
ni = i « i IT,
1=1
(m od n)

'Mn) Mn)
a Mn) X it n - , (m od n)
i '= i i—1
a Mn) 1 (m od n)

Essa é a mesma linha de raciocínio aplicada à prova do teorem a de Fermat. Como acontece com o teorem a de Fermat,
uma forma alternativa do teorem a também é útil:

(7<«")+l . «(m od n) (8.5)

Novamente, de modo sem elhante ao caso do teorem a de Fermat, a primeira forma do teorem a de Euler [Equação
(8.4)| requer que a seja relativam ente primo de //, mas essa forma não.

8.3 TESTANDO SE O NÚMERO É PRIMO

Para muitos algoritmos criptográficos, é necessário selecionar um ou mais números primos muito grandes aleatoria­
mente. Assim, encaramos a tarefa de determ inar se certo núm ero grande é primo. Não existe um meio simples e efi­
ciente de realizar essa tarefa.
Nesta seção, apresentamos um algoritmo atraente e bastante utilizado. Você pode ficar surpreso ao descobrir que
esse algoritmo gera um núm ero que não é necessariamente primo. Porém, o algoritmo pode gerar um núm ero que
quase certam ente é primo. Isso será explicado nesta seção. Também fazemos referência a um algoritmo determinístico
para encontrar primos. A seção termina com uma explicação a respeito da distribuição dos primos.

Algoritmo de Miller-Rabin6
O algoritmo devido a Millcr e Rabin [MILL75, RAI3I80] norm alm ente é usado para testar se um núm ero grande é
primo. A ntes de explicar o algoritmo, precisamos de alguma base. Primeiro, qualquer inteiro positivo ímpar n > 3
pode ser expresso da seguinte forma:

n - 1 = 2kq com k > 0, q odd

Para verificar isso, observe que (n - 1) é um inteiro par. Depois, divida (n - 1) por 2 até que o resultado seja um
núm ero ím par q, para gerar um total de k divisões. Se n for expresso como um número binário, então o resultado será
alcançado deslocando-se o núm ero para a direita até que o dígito mais à direita seja 1, gerando um total de k deslo­
camentos. Agora desenvolveremos duas propriedades dos núm eros primos, das quais precisaremos.
D u a s p r o p r i e d a d e s d o s n ú m e r o s p r i m o s A primeira propriedade é expressa da seguinte maneira: se p é
prim o e a é um inteiro positivo m enor que p, então a2 mod p = 1 se e som ente se a mod p = 1 ou a mod p = —1 mod
p = p - 1. Pelas regras da aritmética modular, (a mod /;) (tf mod /;) = a2 mod /;. Assim, se a mod /; = 1 ou o mod
p = - 1, então a2 mod p = 1. Reciprocam ente, se a2 mod p = 1, então (a mod p ) 2 = 1, que é verdadeiro som ente para
a mod p = 1 ou a mod p = —1.
A segunda propriedade é expressa da seguinte maneira: Considere que p seja um núm ero primo maior que 2.
Podemos, então, escrever p - 1 = 2kq, com k > 0, q ímpar. Considere que a seja qualquer inteiro no intervalo 1 < a
< p - 1. Então, uma das duas condições a seguir é verdadeira:
1. aq é congruente a 1 módulo p. Ou seja, aq mod p = 1 ou, de forma equivalente, aq = l(m od p).
2. Um dos números aq, a2q, a4qt . . . , tf2* lq é congruente a - 1 módulo p. O u seja, existe algum núm ero j no inter­
valo (1 < / < / : ) tal que a21 q mod /; = - 1 mod p = p — 1, ou, de forma equivalente, cr q = - l( m o d p).

Prova: O teorema de Fermat [Equação (8.2)) afirma que an 1 = l(m od //) se n for primo. Temos que p - 1 = 2kq.
A ssim ,sabem os que ar ~l mod p = o2 q mod p = 1. Assim, se examinarmos a seqüência de números

6 .Também conhecido na literatura como algoritm o de R abin-M illcr.ou teste de Rabin-M iller, ou teste de Miller-Rabin.
172 CRIPTOGRAFIA E SEGURANÇA DE REDES

aq m od p , a 2q m od a 4q m od cr 'q m od /;, a 2 q mod p ( 8. 6)

saberem os que o último núm ero na lista tem o valor 1. Além disso, cada núm ero na lista é o quadrado do núm ero an­
terior. Portanto, uma das seguintes possibilidades precisa ser verdadeira:
1. O prim eiro núm ero na lista, e, portanto, lodos os números subseqüentes na lista, é igual a 1.
2. Algum núm ero na lista não é igual a 1, mas seu quadrado mod p é igual a 1. Em virtude da primeira pro­
priedade dos números primos, definida acima, sabemos que o único núm ero que satisfaz essa condição é
p - 1. Assim, nesse caso, a lista contém um elem ento igual a p — 1.
Isso completa a prova.

D e t a l h e s d o a l g o r i t m o Essas considerações levam à conclusão de que, se n é primo, então ou o primeiro ele­

m ento da lista de resíduos, ou restos, (aq, a2q, ..., a2 q, a2 q) módulo n é igual a 1, ou algum elem ento na lista é igual
a (// - 1); caso contrário, n é composto, ou seja, não é primo. Por outro lado, se a condição for atendida, isso não ne­
cessariamente significa que n é primo. Por exemplo, se n = 2047 = 23 x 89, então n - 1 = 2 X 1023. Calculando, 2 1023
mod 2047 = I, de modo que 2047 atende a condição, mas não é primo.
Podemos usar a propriedade anterior para criar um teste que verifica se o núm ero é primo. O procedim ento
TESTE usa um candidato inteiro n como entrada e retorna o resultado c o m p o s to se n definitivamente não for
primo, e o resultado i n c o n c l u s i v o se n pode ou não ser primo.

TEST (n )
1. E ncontre in teiro s k , q, com k > 0, q ím par, de modo q u e (n - 1 = 2 kq) ;
2. S elecio n e um i n t e i r o aleató rio a, 1 < a < n - 1;
3 . S e aq m o d n = 1 e n t ã o r e t u r n (" i n c o n c l u s i v o " ) ;
4. para j = 0 a té k - 1 faça
5. se a ' (,’ m o d n = n —1 então retu rn ( " in con clu sivo" ) ;
6. r e t u r n ( "c o m p o sto ");

Vamos aplicar o teste ao núm ero primo n = 29. Temos (n - 1) = 28 = 22(7) = 2kq. Primeiro, vamos testar
a = 10. Calculamos 107 mod 29 = 17, que não é 1 nem 28, de m odo que continuamos o teste. O próximo cál­
culo descobre que (107)2 mod 29 = 28, e o teste retorna i n c o n c l u s i v o , ou seja, 29 pode ser primo. Vamos
testar novam ente com a = 2. Temos os seguintes cálculos: 27 mod 29 = 12; 2 14 mod 29 = 28; e o leste nova­
mente retorna i n c o n c l u s i v o . Se realizarmos o teste para todos os inteiros a no intervalo de 1 a 28, obtere­
mos o mesmo resultado inconclusivo, que é compatível com n sendo um núm ero primo.
Agora, vamos testar com o núm ero composto n = 13 x 17 = 221. Então, (n - 1) = 220 = 22(55) = 2kq.
Vamos testar a = 5. Então, temos 555 mod 221 = 112, que não é 1 nem 220; (555)2 mod 221 = 168. Como
usamos todos os valores de j (ou seja,;' = 0 e j = 1) na linha 4 do algoritmo TESTE, o teste retorna com­
p o s t o , indicando que 221 é definitivamente um núm ero composto. Mas suponha que tivéssemos sele­
cionado a = 21. Então, teríamos 2155 mod 221 = 200; (2155)2 mod 221 = 220; e o teste retornaria i n c o n ­
c l u s i v o , indicando que 221 pode ser primo. De fato, dos 218 inteiros de 2 até 219, quatro desses retornarão
um resultado inconclusivo, a saber, 21,47,174 e 200.

U s o r e p e t i d o d o a l g o r i t m o d e M i l l e r - R a b i n Com o podem os usar o algoritmo de Miller-Rabin para

determ inar com um alto grau de confiança se um inteiro é ou não prim o? Pode ser m ostrado [KNUT98] que, dado
um núm ero ím par n que não é primo e um inteiro escolhido aleatoriam ente, a com 1 < a < n — 1, a probabilidade de
que TESTE retorne i n c o n c l u s i v o (ou seja, que deixe de detectar que // não é primo) é m enor que 1/4. Assim, se t
diferentes valores de a forem escolhidos, a probabilidade de que todos eles passem no TESTE (retornem neste tipo
i n c o n c l u s i v o ) para n é m enor que (1/4)'. Por exemplo, para t = 10, a probabilidade de que um núm ero não-primo
passe em todos os dez testes é menor que 10~6. Assim, para um valor suficientemente grande de /, podem os confiar
que n é primo se o teste de Miller sem pre retornar i n c o n c l u s i v o .
Isso nos dá uma base para determ inar se um inteiro ímpar n é primo com um razoável grau de confiança. O pro­
cedimento é o seguinte: chame repetidam ente TESTE(«) usando valores escolhidos aleatoriam ente para a. Se, em qual­
quer ponto, TESTE retornar c o m p o sto , então n será determ inado como sendo não-primo. Se o TESTE continuar a
retornar i n c o n c l u s i v o por t testes, para um valor suficientemente grande de (, consideramos que n é primo.
 CAPÍTULO 8 • INTRODUÇÃO À TEORIA DOS NÚMEROS 173

U m a lg o ritm o d eterm in ístico para n ú m eros p rim os

A ntes de 2002 não havia um m étodo conhecido para provar com eficiência se números muito grandes são primos.
Todos os algoritmos em uso, incluindo o mais popular (M iller-Rabin), produziam um resultado probabilístico. Em
2002, Agrawal, Kayal e Saxena [AGRA02] desenvolveram um algoritmo determ inístico relativam ente simples, que
determ ina com eficiência se determ inado núm ero grande é primo. O algoritmo, conhecido como algoritmo AKS, não
parece ser tão eficiente quanto o algoritmo de Miller-Rabin. A té agora ele não suplantou essa técnica probabilística
mais antiga [BORN03].

D istrib u ição de n ú m eros p rim os

Vale a pena observar quantos números provavelmente serão rejeitados antes que um núm ero primo seja encontrado
usando o teste de Miller-Rabin, ou qualquer outro teste de números primos. Um resultado da Teoria dos Números,
conhecido como teorem a do núm ero primo, afirma que os primos próximos de n são espaçados em média a cada (ln
//) inteiros. Assim, na média, seria preciso testar algo na ordem de ln(//) inteiros antes que um núm ero primo fosse
encontrado. Como todos os inteiros pares podem ser im ediatam ente rejeitados, o valor correto é 0,5 ln(/z). Por exem­
plo, se um primo na ordem de grandeza de 22()t) fosse procurado, então seriam necessárias cerca de 0,5 ln(22(K>) = 69
tentativas para encontrar um primo. Porém, esse valor é apenas uma média. Em alguns lugares ao longo da linha de
números, os primos são mais próximos, e em outros lugares existem lacunas maiores.

Os dois inteiros ímpares consecutivos 1.000.000.000.061 e 1.000.000.000.063 são ambos primos. Por outro
lado, 1001! + 2,1001! + 3 ,..., 1001! + 1000,1001! + 1001 é uma seqüência de 1000 inteiros compostos
consecutivos.

8.4 O TEOREMA CHINÊS DO RESTO

Um dos mais úteis resultados da teoria dos números é o teorem a chinês do resto (CRT — Chinese Rem aindcr
llieorem ).7 Basicamente, o TCR diz que é possível reconstruir inteiros em um certo intervalo a partir de seus resí­
duos módulo um conjunto de pares de módulos relalivamente primos.

Os 10 inteiros em Z l0, que são os inteiros de 0 a 9, podem ser reconstruídos a partir de seus dois resíduos
módulo 2 e 5 (os fatores relativam ente primos de 10). Digamos que os resíduos conhecidos de um dígito
decimal x sejam r2 — 0 e r5 = 3, ou seja, .v mod 2 = 0 e x mod 5 = 3. Portanto, x é um inteiro par em Z ]0
cujo resto, na divisão por 5, é 3. A única solução é x = 8.

O TCR pode ser declarado de várias maneiras. A presentam os aqui uma formulação que é mais útil do ponto de
vista deste texto. Uma formulação alternativa é explorada no Problema 8.17. Considere

M = n « ,
i=l
onde o m i são pares de números relativam ente primos, ou seja, mdc(/?/,, mj) = 1 para 1 ^ i , j < /c, e / ^ j. Podemos
representar qualquer inteiro A em Z M por uma tupla de k cujos elem entos estão em Z lW., usando a seguinte corres­
pondência:

Á ^ ( a h a2....... ak) (8.7)

onde A e Z w,a, € Z x1r e at = A mod para 1 < / < k. O TCR faz duas asserções.
1. O m apeam ento da Equação (8.7) é uma correspondência biunívoca (chamada de bijeção) entre Z M e o pro­
duto cartesiano Z iW/ X Z,v/, X ... x Z ^ k. O u seja, para cada inteiro A tal que 0 < A < À7, existe uma tupla
de k elem entos exclusiva (a ,ya2, ..., ak) com 0 ^ a-f < m , que o representa, e para cada tupla de k elementos (fl,,
n2y...yOk) existe um inteiro exclusivo A em Z A/.

7. O TC R tem esse nom e porque acredita-se que tenha sido descoberto pelo m atem ático chinês Sun-Tsu, por volta do ano 100 DC.
174 CRIPTOGRAFIA E SEGURANÇA DE REDES

2. As operações realizadas sobre os elem entos de Z M podem ser equivalentem ente realizadas sobre as tuplas de
k correspondentes, realizando-se a operação independentem ente, cm cada posição de coordenada no sistema
apropriado.

Vamos dem onstrar a primeira asserção. A transform ação de A para (aifa2, a k) obviam ente é exclusiva; ou seja,
cada é calculado exclusivamente como a, = A mod m O cálculo de A a partir de (ci\,a2y —♦ok) pode ser feito da
seguinte forma. Considere Mj = Mlmi para 1 < / < / : . Observe que = w , X m 2 X ... x niiA x m i+l x ... x tnk, de
modo que = 0(mod mj) para todo j =£ /. Então, considere

Cj = Mi X { M J Xm od nij) p ara 1 < / < & ( 8 .8 )

Pela definição de M h ele é relativamente primo de m i e, portanto, possui inverso multiplicativo exclusivo mod m r
Assim, a Equação (8 .8 ) é bem definida e produz um valor exclusivo cv Podemos agora calcular:

(8.9)

Para m ostrar que o valor de A produzido pela Equação (8.9) está correto, temos de m ostrar que at = A mod m h
para 1 < / < / : . Observe que cf = Mj = 0(mod m,) se j ^ / e que c, = 1(mod m,). Segue-se que a,- = A mod m r
A segunda asserção do TCR, referente a operações aritméticas, vem das regras da aritm ética modular. Ou seja,
a segunda asserção pode ser declarada da seguinte forma: Se

A <— > ( a h a2, . . . , a k)

B <— > ( 6 1 , 6 2 , . . . , 6 *)
en tão

(A + B) mod M *— > ((«] + b {) m od m b ___ , (ak + bk) m od m k)

(A - B) m od M *— * ( ( í7 j - /;|) m od m h ___ , (ak - bk) m od m k)
(A X B) m od M <— > ((«1 X 6 ,) m od m b — , (ak X bk) m od m k)
Um dos recursos úteis do teorem a chinês do resto é que ele oferece um modo de m anipular números (poten­
cialmente muito grandes) mod M em termos de tuplas de números menores. Isso pode ser útil quando M tem 150 dígi­
tos ou mais. Porém, observe que é preciso saber de antem ão a fatoração de M.

Para representar 973 mod 1813 como um par de núm eros mod 37 e 49, defina 8
ni\ = 37
m 2 = 49
M = 1813
A = 973
Também temos M ] = 49 e M2 = 37. Usando o algoritmo euclidiano estendido, calculamos M j" 1 = 34 mod m,
e M 2 1 = 4 mod m 2. (Observe que só precisamos calcular cada M, e cada M ,- 1 uma vez.) A panhando resíduos
módulo 37 e 49, nossa representação de 973 é (11,42), pois 973 mod 37 = 11 e 973 mod 49 = 42.
Agora, suponha que queiram os som ar 678 a 973. O que fazemos com (11, 42)? Primeiro, calculamos
(678) <-» (678 mod 37,678 mod 49) = (12,41). Depois, somamos as tuplas para cada elem ento e reduzimos
(11 + 12 mod 37,42 + 41 mod 49) = (23,34). Para verificar se isso tem o efeito correto, calculamos

(2 3 ,3 4 ) <— » m od M
= [(23) (49) (34) + (34) (37) (4)] m od 1813
= 43350 m od 1813
= 1651

8. Este exemplo foi fornecido pelo professor Ken Calvert, da G eorgia Tech.
 CAPÍTULO 8 • INTRODUÇÃO À TEORIA DOS NÚMEROS 175

e verificamos se é igual a (973 + 678) mod 1813 = 1651. Lembre-se de que, na derivação acima, M \ 1 é o
inverso multiplicativo de M x módulo /w,, e M 2 1 é o inverso multiplicativo de M 2 módulo m 2.
Suponha que queiramos multiplicar 1651 (mod 1813) por 73. Multiplicamos (23,34) por 73 e reduzimos
para obter (23 x 73 mod 37,34 X 73 mod 49) = (14,32). Pode ser facilmente verificado que

(1 4 ,3 2 ) <— > [(14) (49) (34) + (32) (37) (4)] m od 1813

= 865
= 1651 X 73 m od 1813

8.5 LOGARITMOS DISCRETOS

Logaritmos discretos são fundam entais para diversos algoritmos de chave pública, incluindo a troca de chave Diffie-
Hellm an e o algoritmo de assinatura digital (DSA). Esta seção oferece uma rápida visão geral dos logaritmos discre­
tos. Para o leitor interessado, mais detalhes desse assunto podem ser encontrados em [ORE67] e [LEVE90].

As p otên cias de u m inteiro, m ó d u lo n

Lembre-se, pelo teorem a de Euler [Equação (8.4)], de que, para cada a e n que são relativam ente primos:

„<«"> = i( m o d /j)

onde <£(/t), a função tociente de Euler, é o núm ero de inteiros positivos m enores que n e relativam ente primos de n.
Agora, considere a expressão mais geral:

am = l(m o d n ) ( 8. 10)

Se a e n são relativamente primos, então existe pelo menos um inteiro m que satisfaz a Equação (8.10), a saber, m = <£(//).
O expoente menos positivo m para o qual a Equação (8.10) c verdadeira, pode ser expresso de várias maneiras:

• a ordem de o (mod n)
• o expoente ao qual a pertence a (mod n)
• a extensão do período gerado por a

Para ver esse último ponto, considere as potências de 7, módulo 19:

71 ■ 7 (m o d 19)
72 = 4 9 = 2 x 19 + 11 * ll( m o d 19)
73 = 343 = 18 x 19 + 1 s l(m o d 19)
74 = 2401 = 126 X 19 + 7 = 7(m od 19)
7 5 = 16807 = 884 X 19 + 11 s ll( m o d 19)

N ão há sentido em continuar, pois a seqüência é repetitiva. Isso pode ser provado observando-se que
7 3 = l(m o d 19) e, portanto, 73+y = 7 3 7y s 7;(m od 19), e por isso duas potências quaisquer de 7 cujos ex­
poentes diferem em 3 (ou um m últiplo de 3) são congruentes entre si (m od 19). Em outras palavras, a se­
quência é periódica, e a extensão do período é o m enor expoente positivo m tal que 7m = l(m o d 19).

A Tabela 8.3 mostra todas as potências de tf, módulo 19, para todo positivo a < 19. A extensão da seqüência para
cada valor de base ê indicada pelo sombreado. Observe o seguinte:

1. Todas as seqüências terminam em 1. Isso é coerente com o raciocínio dos parágrafos anteriores.
2. A extensão de uma seqüência divide <£(19) = 18, ou seja, um núm ero inteiro de seqüências ocorre em cada
linha da tabela.
176 C R IP T O G R A F IA e seg u ra n ça de redes

3. Algumas das seqüências têm extensão 18. Nesse caso, diz-se que o inteiro de base a gera (por potências) o con­
junto de inteiros diferentes de zero módulo 19. Cada um desses inteiros é chamado de raiz primitiva do módulo 19.
Geralm ente, podemos dizer que o expoente mais alto possível ao qual um núm ero pode pertencer (mod n) é
</>(//)• Se um núm ero for dessa ordem , ele é considerado uma raiz primitiva de n. A importância dessa noção é que, se
a for uma raiz primitiva de n , então suas potências

a, o 2, . . . ,

são distintas (mod n) e são todas relativam ente primas de n. Em particular, para um núm ero primo p, sc a é uma raiz
primitiva de p, então

a, a 2, ..., a p~1

são distintos (mod p). Para o núm ero primo 19, suas raízes primitivas são 2,3, 10,13,14 e 15.
Nem todos os inteiros possuem raízes primitivas. De fato, os únicos inteiros com raízes primitivas são aqueles no
form ato 2 ,4 ,p “ e 2p " onde p é qualquer primo ímpar e a é um inteiro positivo. A prova não é simples, mas pode ser
encontrada em muitos livros sobre a Teoria dos Números, incluindo [ORE76].

L ogaritm os para aritm ética m odular

Com números reais positivos comuns, a função de logaritmo é o inverso da exponenciação. Existe uma função sem el­
hante para a aritm ética modular.
Vamos rever rapidam ente as propriedades dos logaritmos comuns. O logaritmo de um núm ero é definido como
sendo a potência à qual alguma base positiva (exceto 1 ) precisa ser elevada para igualar o número, ou seja, para a base
x e para um valor y:
y = x '°s«(y)

As propriedades dos logaritmos incluem as seguintes:

log.v(l) 0
log,(-v) 1
lO g-rí^) lOfeOO + log.v(z) (8 .11)
l0 g .t(/) r X logt (y) (8.12)

Tabela 8.3 Potências de inteiros, módulo 19

1
a a a3 a4 a5 a6 a7 «s a9 a 10 a" a 12 a 13 a 14 a15 a lft a 17 a 18
1 i 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1
3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13 1
4 16 7 9 17 11 6 5 1 4 16 7 9 17 11 6 5 1
5 6 11 17 9 7 16 4 1 5 6 11 17 9 7 16 4 1
6 17 7 4 5 11 9 16 1 6 17 7 4 5 11 9 16 1
7 11 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1
8 7 18 11 12 1 8 7 18 11 12 1 8 7 18 11 12 1
9 5 7 6 16 11 4 17 1 9 5 7 6 16 11 4 17 1
10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2 1
11 7 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1
12 11 18 7 8 1 12 1) 18 7 8 1 12 11 18 7 8 1
13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3 1
14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15 1
15 16 12 9 2 11 13 5 18 4 3 7 10 17 8 6 14 1
16 9 11 5 4 7 17 6 1 16 9 11 5 4 7 17 6 1
17 4 11 16 6 7 5 9 1 17 4 11 16 6 7 5 9 1
18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1
 CAPÍTULO 8 • INTRODUÇÃO A TEORIA DOS NÚMEROS 177

Considere uma raiz primitiva a para algum núm ero primo p (o argum ento pode ser desenvolvido para não-pri­
mos tam bém). Então, sabem os que as potências de a partir de 1 até (p - I) produzem cada inteiro de 1 até (p - 1)
exatam ente uma vez. Também sabemos que qualquer inteiro b satisfaz

b = r(m o d p ) para algum r , onde 0 s r < (p - 1)

pela definição da aritmética modular. Segue-se que, para qualquer inteiro b e uma raiz primitiva a de núm ero p rim o/;,
podemos encontrar um expoente exclusivo / tal que

b = tf'(m od p ) o nde 0 < / < ( / ; — 1)

Esse expoente / é conhecido como o logaritmo discreto do núm ero b para a base «(mod /;). Indicamos esse valor
como dlog,,,//)).9
Observe o seguinte:

d l o g ^ l ) = 0, pois a° m od p = l m od p = 1 (8.13)
dlo ga,p(a) = l,p o is a ] m od p = a (8.14)

Aqui está um exemplo usando um m ódulo não-primo, n = 9. Aqui, </>(w) = 6, e a = 2 é uma raiz primitiva.
Calculamos as diversas potências de a e encontram os

2o = 1 2 4 = 7 (m od 9)
21= 2 2 5 = 5 (m o d 9)
22 = 4 2 6 = l(m o d 9)
23 = 8

Isso nos dá a seguinte tabela de núm eros com determ inados logaritmos discretos (mod 9) para a raiz a = 2:

Logaritmo 0 1 2 3 4 5
N úm ero 1 2 4 8 7 5

Para facilitar a obtenção dos logaritmos discretos de determ inado número, rearrum am os a tabela:

Núm ero 1 2 4 5 7 8
Logaritmo 0 1 2 5 4 3

Agora, considere
x = rtdlo&-Av) m od p y = í7d,08tí m od p
x y = tfd,0& Ãv>*) m od p
Usando as regras da multiplicação modular,

x y m od p = [{x m od p ) (y m od /?)] m od p

fldlog^,(xy) m otj p _ Í qíllo&.p(.v) mocJ p^j ^logd.pír) mocl m od p

= m0(j p

Mas agora considere o teorem a de Euler, que afirma que, para cada a e n que são relativam ente primos:

= i( m o d /i)

9. M uitos textos se referem ao logaritm o discreto com o o índice. G eralm ente, não existe uma notação convencionada para esse conceito,
m uito m onos um nom e convencionado.
178 CRIPTOGRAFIA E SEGURANÇA DE REDES

Qualquer inteiro positivo z pode ser expresso na forma z = q + k ^ n ), com 0 ^ q < <t>(n). Portanto, pelo teorema de Euler,

cr = tf'7(mod n) se z — (j m od (j>{n)
Aplicando isso à igualdade anterior, temos

dlog,v (*y) = [ d lo g ^ t* ) + dlog„;,(y)] (m od 4>{p))

e generalizando,

dlog(,.p ( /) = [r X d l o g , ( m o d </>(/?))

Isso dem onstra a analogia entre logaritmos verdadeiros e logaritmos discretos.

Lembre-se de que os logaritmos discretos exclusivos mod m em alguma base a só existem se a for uma raiz pri­
mitiva de m.
A Tabela 8.4, que é derivada diretam ente da Tabela 8.3, mostra os conjuntos de logaritmos discretos que podem
ser definidos para o módulo 19.

Cálculo de logaritmos discretos

Considere a equação
y = gx m od p
D ados £, x e /?, é muito simples calcular y. No pior dos casos, temos de realizar a' multiplicações repetidas, e existem
algoritmos para se conseguir m aior eficiência (ver Capítulo 9).
Porém, dados y, g e p, em geral, é muito difícil calcular a- (considere o logaritmo discreto). A dificuldade parece
estar na mesma ordem de grandeza daquela da fatoração de números primos, exigida para o RSA. No mom ento em
que este livro foi escrito, o algoritmo mais rápido conhecido para realizar logaritmos discretos módulo um núm ero
primo estava na ordem de [BETH91):
e((\np)v3{\n(\np))2*)
que não é viável para grandes números primos.

Tabela 8.4 Tabelas de logaritm os discretos, m ódulo 19

(a) Logaritmos discretos com a base 2, módulo 19

a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
18 1 13 2 16 14 6 3 8 17 12 15 5 7 11 4 10 9

(b) Logaritmos discretos com a base 3, módulo 19

a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
log.u y(fl) 18 7 1 14 4 8 6 3 2 11 12 15 17 13 5 10 16 9

(c) Logaritm os discretos com a base 10, m ódulo 19

a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
lo g io .iy (« ) 18 17 5 16 2 4 12 15 10 1 6 3 13 11 7 14 8 9

(d) Lo ’aritiiK s discr elos coini a base 13, módulo 19

a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
togaw í«) 18 11 17 4 14 10 12 15 16 7 6 3 1 5 13 8 2 9

(e) Logaritmos discretos com a base 14, módulo 19

a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
log 14.1<;(«) 18 13 7 8 10 2 6 3 14 5 12 15 11 1 17 16 4 9

(f) Logaritmos discretos com a base 15, módulo 19

a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
lo g is .iy (fl) 18 5 11 10 8 16 12 15 4 13 6 3 7 17 1 2 14 9
 CAPÍTULO 8 • INTRODUÇÃO À TEORIA DOS NÚMEROS 179

8.6 LEITURA E SITES WEB RECOMENDADOS

Existem muitos textos básicos a respeito de Teoria de Números, que oferecem muito mais detalhes do que a maioria
dos leitores deste livro deseja. Um a rápida introdução elem entar, em bora útil, é [ORE67]. Para o leitor interessado
em uma abordagem mais profunda, dois livros-texto excelentes sobre o assunto são [KUMA98] e [ROSE05].
[LEVE90] também é um abordagem fácil c detalhada. Todos esses livros incluem problem as com soluções, aum en­
tando seu valor como auto-estudo.
Para os leitores que desejam realm ente despender tempo, talvez a m elhor maneira dc obter um conhecimento
sólido dos fundam entos da Teoria dos Núm eros seja trabalhar com [BURN97], que consiste unicam ente em uma série
de exercícios com soluções que acompanham o aluno passo a passo pelos conceitos da Teoria dos Números; fazer
todos os exercícios é equivalente a concluir um curso de formação sobre Teoria dos Números.

BURN97 Burn, R. A pathway to number theory. Cambridge: Cambridge University Press, 1997.
KUMA98 Kumanduri. R. e Romero, C. Number theory with computer applications. Upper Saddle River: Prentice Hall,
1998.
LEVE90 Leveque, W. Elementary theory o f numbers. New York: Dover, 1990.
ORE67 Ore, O. Invitation to number theory. Washington: The Mathematical Association of America, 1967.
ROSE05 Rosen, K. Elementary number theory and its applications. Reading: Addison-Wesley, 2000.

■s^Site Web reco m en d ad o :

• T he Prime Pages: Pesquisa, registros e recursos para números primos.

8.7 PRINCIPAIS TERMOS, PERGUNTAS DE REVISÃO E PROBLEMAS

P rin cip ais te rm o s
função tociente de Eulcr número primo teorema chines do resto
índice ordem teorema de Eulcr
logaritmo discreto raiz primitiva teorema de Fermat
número composto

P erguntas de revisão
8.1 O que é um núm ero primo? um núm ero é primo. Como esse algoritmo pode
8.2 Q ual é o significado da expressão a divide b? ser usado para testar se o núm ero é primo?
8.3 O que é a função tociente de Euler? 8.5 O que é uma raiz primitiva de um núm ero?
8.4 O teste de Miller-Rabin pode determ inar se um 8.6 Qual é a diferença entre um índice e um logaritmo
núm ero não é primo, mas não pode determ inar se discreto?

P roblem as
8.1 A finalidade deste problema é determ inar quantos a. Considere P = Pr[mdc(a, b) = lj. M ostre que
núm eros primos existem. Suponha que haja um Pr[mdc(a, b) = d] = Pld1. Dica: Considere a quan­
total de n números primos, e os listemos em ordem:
tidade igualdade mdc
P\ = 2 < p 2 = 3 < ps = 5 < • • • < pn.
a. Defina X = 1 + p xp 2 Qu seja, X é igual a um b. A soma do resultado da parte (a) sobre to­
mais o produto de todos os primos. Podemos dos os valores possíveis dc d ê 1. Qu seja:
encontrar o núm ero primo p /n que divide X'l
2)Pr[gcd(ci, b) = d] = l.Use essa igualdade para
h. O que você pode dizer sobre m l </£1
c. Deduza que o núm ero total de primos não pode determ inar o valor de P. Dica: Use a igualdade
ser finito.
cl. M ostre que /;,í+1 < 1 + pij)2 .
8.2 A finalidade deste problema é dem onstrar que a 8.3 Por que mdc(/?, n + 1) = 1 para dois inteiros con­
probabilidade de que dois núm eros aleatórios secutivos n e n + 1?
sejam relativam ente primos é de cerca de 0,6. 8.4 Usando o teorema de Fermat, encontre 3201 mod 11.
180 CRIPTOGRAFIA E SEGURANÇA DE REDES

8.5 Use o Teorema de Fermat para encontrar um número fazer isso com números não primos até um valor
a entre 0 e 72 com a congruente a 9794 módulo 73. muito grande. Isso confundiu os matemáticos chi­
8.6 Use o Teorema de Fermat para encontrar um nú­ neses, que pensaram que, se a condição fosse ver­
mero .v entre 0 e 28 com a*85 congruente a 6 módulo dadeira, então n seria primo,
29. (Você não precisara usar qualquer pesquisa por cl. Infelizmente, os antigos chineses nunca experimen­
força bruta.) taram n = 341, que não é primo (341 = 11 X 31) e
8.7 Use o Teorem a de E uler para en co n trar um ainda 341 divide 2M< - 2 sem resto. Demonstre que
núm ero a entre 0 e 9 tal que a seja congruente a 2341 = 2(mod 341) (invalidando a condição somente
71000 módulo 10. (Observe que isso é o mesmo que se). Dica: não é necessário calcular 2341;em vez disso,
o último dígito da expansão decimal de 7llM,(>). use as congruências.
8.8 Use o Teorema de E uler para encontrar um nú­ 8.15 Mostre que, se n é um inteiro composto ímpar, então
mero .v entre 0 e 28 com x8:>congruente a 6 módulo 0 teste de Miller-Rabin retornará i n c o n c l u s i v o
35. (Você não precisará usar qualquer pesquisa por para a = 1 e a = (n - 1).
força bruta.) 8.16 Se n é composto e passa no teste de Miller-Rabin
8.9 Observe, na Tabela 8.2, que </>(/*) é par para n > 2. Isso para a base r/, então n é cham ado de pseudoprimo
é verdade para todo n > 2. Forneça um argumento forte na base a. Mostre que 2047 é um pseudoprimo
conciso para explicar por que Isso acontece. na base 2.
8.10 Prove o seguinte: Se p é primo, então = 8.17 Uma formulação comum do teorem a chinês do
pi _ p i-i Djca: qUC núm eros têm um fator em resto (TCR) é a seguinte: Considere que m ,,..., m k
comum com p'? sejam inteiros relativam ente primos par a par, para
1 < iyj < kyC i r j. Defina A7 como sendo o produ­
8.11 Podemos m ostrar (consulte qualquer livro sobre a
to de todos os m/s. Considere que a,, ..., ak sejam
Teoria de Números) que, se mdc(m, //) = 1, então
inteiros. Então, o conjunto de congruências:
cp(rnn) = (f)(m)</>(/?). U sando essa propriedade e a
propriedade desenvolvida no problema anterior, e ,v = <?i(mod m x)
a propriedade de que 4>(p) = p - 1 para p primo, é x = r/2(mod m 2)
simples determ inar o valor de <f>(n) para qualquer
n. Determ ine o seguinte: .v = **(mod m k)
a. </>(41) b. </>(27)
c. 0(231) cl. *(440) tem uma solução exclusiva módulo M. Mostre que
8.12 Também pode ser m ostrado que, para qualquer o teorem a declarado dessa forma é verdadeiro.
inteiro positivo a, é(a ) é dado por: 8.18 O exemplo usado por Sun-Tsu para ilustrar o TCR foi

<H<i) =n[prv.
=
í i
~>)] x = 2(mod 3); .v = 3(mod 5); .v = 2(mod 7)

onde a é dado pela E quação (8.1), a saber: Resolva x.

a = p‘l lP22 . • •pí';. D em onstre esse resultado. 8.19 Seis professores iniciam cursos na segunda-feira,
terça-feira, quarta-feira, quinta-feira, sexta-feira e
8.13 Considere a função: f(/i) = núm ero de elem entos
no conjunto (r/:0 < a < n e mdc(a, n) = 1). O que é sábado, respectivamente, e anunciam suas intenções
ministrar palestras em intervalos de 2, 3, 4 ,1 , 6 e 5
essa função?
dias, respectivamente. As diretrizes da universidade
8.14 Em bora os antigos matemáticos chineses tivessem proíbem palestras aos domingos (de modo que uma
feito um bom trabalho apresentando seu teorem a palestra no domingo deverá ser omitida). Quando
do resto, eles nem sem pre acertavam. Eles tinham todos os seis professores serão obrigados pela
um teste de números primos. O teste dizia que n é primeira vez a omitir uma palestra? Dica: use o TCR.
primo se e som ente se n dividir (2" - 2).
8.20 Encontre todas as raízes primitivas de 25.
a. Dê um exemplo que satisfaça a condição usando
um primo ímpar. 8.21 D ado 2 como uma raiz primitiva de 29, construa
I). A condição é obviam ente verdadeira para n = 2. uma tabela de logaritmos discretos e use-a para
Prove que a condição é verdadeira se n for um solucionar as seguintes congruências:
primo ím par (provando a condição se), a. 17a:2 = 10(mod 29)
c. Dê um exemplo de um n ímpar que não seja I). x 2 - 4.v - 16 = 0(mod 29)
primo e que não satisfaça a condição. Você pode c. x 1 = 17(mod 29)

P roblem as de p ro g ram ação

8.22 Escreva um program a de com putador que imple­ pelo usuário. O programa deverá permitir que o usuário
mente a exponenciação rápida (quadrados suces­ faça duas escolhas: (1) especifique uma possível teste­
sivos) módulo n. munha a para testar o uso do procedimento Witness, ou
8.23 Escreva um programa de computador que implemente (2) especifique um número s de testemunhas aleatórias
o algoritmo de Miller-Rabin para um n especificado para o teste de Miller-Rabin verificar.