Teoria dos Números e o RSA

Prévia do material em texto

Universidade Estadual de Campinas
Instituto de Matemática, Estat́ıstica e Computação Cient́ıfica
Departamento de Matemática Aplicada
Dissertação de Mestrado
TEORIA DOS NÚMEROS E O RSA
por
Bianca Amoras de Souza
Mestrado em Matemática Aplicada
Orientador: Prof. Dr. José Pĺınio de O. Santos
Este trabalho contou com o apoio financeiro do CNPq.
TEORIA DOS NÚMEROS E O RSA
Este exemplar corresponde à redação
final da dissertação intitulada
“Teoria dos Números e o RSA”
devidamente corrigida e defendida por
Bianca Amoras de Souza e aprovada
pela comissão julgadora.
Campinas, 15 de agosto de 2004.
Prof. Dr. José Pĺınio de O. Santos
Orientador
Banca Examinadora:
1. Prof. Dr. José Pĺınio de Oliveira Santos
2. Prof. Dr. Emerson Alexandre de Oliveira Lima
3. Profa. Dra. Sueli Rodrigues Costa
Dissertação apresentada ao Instituto de
Matemática, Estat́ıstica e Computação Ci-
ent́ıfica, UNICAMP, como requisito par-
cial para otenção do t́ıtulo de MESTRE
em Matemática Aplicada.
ii
Campinas, 15 de julho de 2004.
Autor: Bianca Amoras de Souza
T́ıtulo: Teoria dos Números e o RSA
Departamento: Matemática Aplicada
Grau: Mestre em Matemática Aplicada
Defesa: 06 de agosto de 2004
Assinatura da Autora
iii
Ao Sashenka.
iv
Sumário
Abstract vii
Resumo viii
Agradecimentos ix
Tabelas de Śımbolos xi
Introdução 1
1 Criptografia Computacional 4
1.1 Sistemas Criptográficos . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Funções Unidirecionais . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Criptossistemas Simétricos e Assimétricos . . . . . . . . . . . . . . . 8
2 O Sistema de Chave Pública RSA 10
2.1 Geração das Chaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Codificação e Decodificação . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Assinatura Digital . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Segurança do RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
v
3 Testes de Primalidade 18
3.1 Distribuição de Primos . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Teste de Solovay-Strassen . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Teste de Miller-Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Teste de Agrawal-Kayal-Saxena . . . . . . . . . . . . . . . . . . . . . 33
3.4.1 Teoria dos Números . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.2 Corpos finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4.3 O algoritmo AKS . . . . . . . . . . . . . . . . . . . . . . . . . 43
4 Fatoração de Inteiros 53
4.1 Um Método Simples . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2 Método de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 ρ-Método de Pollard . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.4 ρ− 1-Método de Pollard . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5 Crivo Quadrático . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Conclusão 60
vi
Abstract
Number Theory has been subject of study since the ancient years. In the two
last decades, this field of Mathematics has gained much interest due to its use in
cryptography. The public-key cryptosystems have their security based on number
theoretic problems which are computationally hard to solve.
The RSA base its security on the difficulty in factoring numbers that are products
of two big primes. In this work, we describe the RSA. As we are interested also in the
generation of prime numbers and factorization of integers, we present some methods
for primality testing and integer factorization.
vii
Resumo
A Teoria dos Números tem sido objeto de estudo desde a antiguidade. Nas últimas
duas décadas, este campo da Matemática tem ganho maior interesse devido à sua
utilização em criptografia. Os criptossistemas de chave pública têm sua segurança
baseada em problemas da Teoria dos Números que são computacionalmente dif́ıceis
de resolver.
O RSA baseia sua segurança na dificuldade de fatorar números que são produtos de
dois primos grandes. Neste trabalho, descreveremos o RSA. Como estamos também
interessados na geração de números primos e na fatoração de inteiros, apresentaremos
alguns testes de primalidade e métodos de fatoração.
viii
Agradecimentos
Agradeço a Deus, por tudo.
Aos meus pais, Rosana e Francisco, sem os quais não estaria onde estou hoje. Em
particular à minha mãe, quem esteve sempre ao meu lado.
Ao Alexander Sosnovski (Sashenka) por seu amor, companheirismo e apoio.
Ao Agnaldo Dantas Sobrinho, meu padrasto querido.
Ao meu orientador, Prof. Pĺınio O. dos Santos, pela paciência, pela compreensão
e por sua orientação neste trabalho.
Aos meus amigos de todas as horas. Em especial, Ignêz G. Amaral e Luciane
Bombach.
Aos colegas do Departamento de Matemática Aplicada do IMECC por toda ajuda
e companhia durante o curso. Em particular, agradeço aos colegas Eduardo Bovo,
Igor Freire e Jair Cunha.
Agradeço à Luziane por me ajudar a solucionar alguns problemas com relação ao
LATEX.
Aos professores dos Departamentos de Matemática e Matemática Aplicada por
incentivarem meu gosto pelos estudos.
ix
Aos professores da banca examinadora, pelas sugestões e correções.
Ao Alonso Sepúlveda Castellanos por me ajudar com a figura que representa um
sistema criptográfico contida nesta dissertação.
x
Tabelas de Śımbolos
bxc Maior inteiro menor do que ou igual a x
lg x Número de bits de x
f(x) = O(g(x)) Existência de uma constante positiva c e um inteiro n0
tais que f(x) ≤ cg(x) para x ≥ n0
log x Logaritmo natural de x
logb x Logaritmo de x na base b
φ(x) Número de inteiros menores do que ou iguais a x que são
relativamente primos com x
mdc(x, y) Máximo divisor comum dos inteiros x e y
mmc(x, y) Mı́nimo múltiplo comum dos inteiros x e y
π(x) Números de primos menores do que ou iguais a x(
a
n
)
Śımbolo de Jacobi
E(n) Conjunto de bases de Euler para os quais n é um candidato
a primo
|C| Cardinalidade do conjunto C
Zn Grupo aditivo de inteiros módulo n
Z∗n Grupo multiplicativo de inteiros módulo n
ordna Ordem de a módulo n
S(n) Conjunto de bases para os quais n é um candidato
forte a primo
(A : B) Índice do subgrupo B em A, A um grupo
xi
(
m
n
)
Coeficiente binomial de m e n
P (n) Maior primo divisor de n
π′(x) Cardinalidade de {p ; p é primo , p ≤ x e P (p− 1) > x2/3}
Zn[x] Anel de polinômios em Zn
p(x) mod (q(x), n) Resto da divisão do polinômio p(x) pelo polinômio
q(x) em Zn[x]
F Anel de polinômios em Zn[x] de grau ≤ grau(h(x))
onde a adição e a multiplicação são módulo h(x),
h(x) um polinômio irredut́ıvel
og Ordem de g(x) em F
xii
Introdução
A palavra criptografia tem origem no grego, onde cryptos significa oculto, se-
creto, escondido e grapho significa escrita, grafia. A criptografia é, então, o estudo
de métodos para transformar uma mensagem originalmente compreenśıvel em algo
incompreenśıvel para todos, exceto para o destinatário leǵıtimo da mensagem que a
tornará leǵıvel novamente, podendo interpretar seu conteúdo.
O processo de transformar uma mensagem leǵıvel em uma equivalente mas ileǵıvel
é chamado de codificação. E o que um usuário leǵıtimo do código usa para tornar
compreenśıvel uma mensagem codificada é denominado decodificação.
Em geral, para decodificar uma mensagem é necessário o conhecimento de uma
chave secreta dispońıvel ao usuário leǵıtimo do código. É posśıvel que pessoas não au-
torizadas tenham acesso à mensagem codificada e consigam determinar seu conteúdo
ou mesmo a chave de decodificação, “quebrando” o código. A este processo chama-
mos de deciframento.
A criptoanálise (cryptos+analysis= decomposição) busca determinar a chave de
decodificação ou decifrar a mensagem sem o conhecimento da chave.
Ao estudo ou ciência quereúne a criptografia e a criptoanálise chamamos de
criptologia.
1
O uso da criptografia já se fazia presente no sistema eǵıpcio de escrita hierogĺıfica,
há aproximadamente quatro mil anos. Júlio César usava um cifrário para comunicar
seus planos de batalha aos generais de seu exército. Tal cifra consistia em transladar as
letras do alfabeto três casas adiante. Existem outros códigos primitivos semelhantes
a este como, por exemplo, o cifrário de Vigenère [18, §4 On the Origin of the Species]
e o cifrário de Hill [18, §13 Secrecy for Sale].
A partir do advento dos computadores, os métodos de codificação baseados em
substituição alfabética tornaram-se inviáveis. Na verdade, o primeiro computador foi
criado para decifrar as mensagens secretas estabelecidas pelo exército alemão durante
a Segunda Guerra Mundial. As mensagens alemães eram codificadas através de uma
máquina chamada Enigma. Um projeto denominado ULTRA foi desenvolvido na
época em Bletchley Park, Inglaterra, para tentar decifrar o código alemão. Um dos
responsáveis por este projeto era Alan Turing, o idealizador da máquina de Turing.
Como conseqüência deste projeto o primeiro computador foi constrúıdo, o Colossus.
Até então, o uso da criptografia estava associada a interesses poĺıticos e militares.
Com a crescente utilização de redes de computadores, a necessidade de se manter
informações sigilosas também cresceu. A criptografia segue, então, uma nova direção,
deixando de servir a interesses puramente militares ou poĺıticos e passa a servir a
cidadãos comuns. Um exemplo disso, é a enorme quantidade de transações bancárias
ou comerciais feitas através da internet nos dias de hoje.
Particularmente, estaremos interessados na criptografia computacional, onde a
segurança de informações em redes de computadores, em bancos de dados, em caixas
automáticos, etc. é a principal preocupação. Mais especificamente, faremos uma
relação entre a criptografia RSA e a Teoria dos Números. Atualmente, o RSA é um
2
dos métodos criptográficos mais usados em aplicações comerciais.
Inicialmente, descreveremos o RSA. Como para codificar uma mensagem usando
o RSA é preciso obter dois primos grandes, exporemos alguns algoritmos para testar
a primalidade de números. Outro aspecto importante em relação ao RSA é a intrata-
bilidade de se fatorar o produto de dois primos grandes, também serão apresentados
alguns algoritmos de fatoração.
Como em nosso estudo analisaremos a complexidade de alguns algoritmos impor-
tantes direta ou indiretamente para a criptografia RSA, faremos as análises em termos
do tamanho da entrada.
Definição 0.0.1. Seja n um inteiro positivo. Definimos
lg n =
{
1, se n = 0
1 + blog2 nc, se n 6= 0 .
Assim, lg n conta o número de bits na representação binária de um inteiro n.
3
Caṕıtulo 1
Criptografia Computacional
O uso de rede de computadores, cada vez em maior número de aplicações, depende
diretamente da confiabilidade que tais redes oferecem. É necessário proteger as men-
sagens e dados que trafegam nestes meios de comunicação de maneira que somente
pessoas ou processos autorizados possam utilizá-los. É a criptografia que cuida de
fornecer segurança e proteção à transmissão dessas informações e cujos objetivos são:
• Sigilo de informação que é a garantia de que somente pessoas autorizadas te-
nham acesso às informações. O acesso a saldos bancários em caixas automáticos
é um exemplo disso, onde somente as pessoas autorizadas, mediante cartão e
senha pessoal, têm acesso a esse tipo de dados.
• Integridade de informação que garante que a mesma não sofra nenhum tipo de
alteração, intencional ou não, de seu conteúdo, ou seja, que a informação se
encontre inalterada. Um exemplo desse tipo de aplicação é o banco de dados de
uma universidade que contém os históricos escolares dos alunos. A criptografia
dificulta a fraude nas notas dos alunos.
4
• Autenticação de informação serve para identificar pessoas ou processos com
quem se está estabelecendo comunicação. Como exemplo, a assinatura digital
é um análogo computacional à assinatura em um documento tradicional.
• Não repúdio que evita que uma das partes envolvida na comunicação negue
o envio ou o recebimento de uma informação. Um exemplo disso seria uma
empresa que autoriza uma entidade a comprar uma propriedade e depois nega
que autorizou tal negociação.
1.1 Sistemas Criptográficos
Um sistema criptográfico é um conjunto de processos criptográficos que fornece
segurança de informações. Um sistema criptográfico consiste de :
• Um conjunto finito A que chamamos de alfabeto de entrada. O alfabeto de
entrada pode ser o alfabeto latino, o alfabeto binário ou qualquer alfabeto de
alguma ĺıngua. Em se tratando de criptografia computacional, geralmente o
alfabeto binário será usado como alfabeto de entrada. Convém observar que
qualquer tipo de alfabeto pode ser representado como uma cadeia de strings do
alfabeto binário.
• Um conjunto M formado por cadeias finitas de elementos de A. Chamamos a
este conjunto de espaço de mensagens. Cada elemento deM corresponde a um
texto simples, não cifrado.
• Um conjunto C também formado por cadeias finitas de elementos de A. Este é
o chamado espaço de mensagens codificadas e cada elemento de C corresponde
5
a um texto cifrado.
• K um conjunto finito de elementos chamados de chaves que são ferramentas
necessárias para manter oculta uma informação.
• E espaço de funções e :M→ C onde cada função codifica os elementos de M.
E é o espaço de funções de codificação.
• D espaço de funções d : C →M onde cada função decodifica os elementos de C.
Cada elemento k1 ∈ K determina uma única bijeção de M em C que denotamos
por ek1 . Assim, temos que existe k2 ∈ K que determina uma função de decodificação
dk2 que é inversa à ek1 .
Quando se projeta um sistema criptográfico deve-se estar atento ao fato de que
o sistema deve permanecer seguro mesmo quando os algoritmos de codificação e de
decodificação são de conhecimento público.
Com esse objetivo usam-se pares de chaves, uma para codificação e outra para
decodificação, devendo haver uma grande número de pares de chaves.
A figura a seguir esboça um sistema criptográfico t́ıpico onde duas funções são
utilizadas:
Exemplo 1.1.1. Um sistema criptográfico simples é o cifrário de César que já menci-
onado anteriormente. Consiste em substituir uma letra por outra, três casas adiante.
Os conjuntosM e C constituem ambos de textos formados pelas 26 letras do alfabeto
latino. Pode-se variar o valor de casas que devemos transladar cada letra e tal valor
consiste na chave de codificação. Obviamente esses valores estão no intervalo [0, 25].
A chave de decodificação é a mesma que a de decodificação. As funções de codificação
6
Figura 1.1: Sistema Criptográfico
e decodificação são as translações “avançada” e “retroativa”, respectivamente, em três
casas no alfabeto.
1.2 Funções Unidirecionais
As funções de codificação e de decodificação usadas em criptossistemas são exem-
plos t́ıpicos de funções unidirecionais. A seguir definiremos funções unidirecionais.
Definição 1.2.1. Uma função unidirecional f é uma função computacionalmente
viável (em tempo, espaço e dinheiro) de se calcular f(x) dado x e computacionalmente
inviável determinar x tal que f(x) = y dado y.
A unidirecionalidade de uma função pode ser uma caracteŕıstica intŕınseca da
própria função ou depender do estado da arte do avanço tecnológico e cient́ıfico como
veremos no exemplo a seguir.
7
Exemplo 1.2.1. A multiplicação de dois primos grandes (pelo menos 100 d́ıgitos)
é facilmente calculada com a tecnologia atual, mas dado o produto de dois primos
(pelo menos 200 d́ıgitos decimais) obter a fatoraçãodo produto não é viável com a
tecnologia atual. A segurança do criptossistema RSA (próximo caṕıtulo) é baseado
na incapacidade de fatorar um número grande rapidamente.
Exemplo 1.2.2. Outro exemplo de função unidirecional é a exponenciação módulo
um número, isto é, f(x) = ax (mod n), dados a, x e n, com x ≥ 0 e n > 0.
Esta é uma função viável de se calcular cujo tempo de execução é O(lg x lg2 n)
[7, Cap.5]. Agora, dados a, n e ax (mod n), calcular x é inviável. Ainda não
existe um algoritmo para este problema cuja execução seja em tempo polinomial.
Existem dois tipos de funções unidirecionais que podem ser com segredo ou sem
segredo. Uma função unidirecional é com segredo quando existe uma informação
(o segredo) que possibilita a computação de sua inversa e sem segredo caso contrário.
No caso da função fatoração de primos, no exemplo acima, a função é sem segredo.
1.3 Criptossistemas Simétricos e Assimétricos
Quando a chave de decodificação e a chave de codificação são as mesmas em
um dado criptossistema ou quando a função de decodificação é uma função com-
putacionalmente viável da chave de codificação , precisamos manter a chave em
sigilo, sendo conhecida apenas pelos usuários leǵıtimos. Neste caso, o sistema é dito
simétrico ou de chave secreta. O cifrário de César é um exemplo de criptossistema
simétrico.
8
O sistema simétrico mais conhecido é o DES - Data Encryption Standard adotado
pelo governo americano em 1977 como padrão de codificação para uso em seus órgãos
governamentais não relacionados à segurança nacional. Por não ser objeto de nosso
estudo não descreveremos o DES neste trabalho. A descrição de seu funcionamento
pode ser obtida nas referências [23] e [24].
Nos criptossistemas assimétricos ou de chave pública, a chave de codificação é
publicada, ou seja, acesśıvel à todos. O conhecimento da chave de codificação não
compromete a segurança do sistema. O processo de codificação também é público e
somente a chave de decodificação é mantida em segredo pelo destinatário leǵıtimo da
mensagem.
A idéia de um sistema de chave pública foi inicialmente introduzido por Diffie e
Hellman em 1976. O RSA é um sistema criptográfico assimétrico e foi o primeiro
criptossistema de chave pública criado. A partir disso, surgiram muitos outros crip-
tossistemas de chave pública. O RSA será descrito no próximo caṕıtulo.
Nos sistemas de chave pública, cada usuário possui um par de chaves, sendo que
uma é a chave de codificação, colocada à disposição daqueles que desejam enviar uma
mensagem para o proprietário da chave. Suponhamos que um usuário A deseje enviar
uma mensagem m para um outro usuário B. Então o usuário A consulta a lista de
chaves públicas e obtém a chave de codificação PB de B. A aplica PB à mensagem
m e obtém o texto codificado PB(m) e envia para B. Após receber PB(m), B aplica
a chave secreta SB e obtém m = SB(PB(m)). Assim, todos os usuários que enviam
mensagens codificadas a B usam a mesma chave pública PB, entretanto, somente B
tem acesso à chave secreta SB.
9
Caṕıtulo 2
O Sistema de Chave Pública RSA
O criptossistema de chave pública RSA foi desenvolvido por R. L. Rivest, A.
Shamir e L. Adleman em 1978. As iniciais dos autores deram origem ao nome do
código.
O RSA tem base na facilidade de computar o produto de dois primos grandes
(pelos menos da ordem 10100 cada) e na dificuldade de fatorar esse produto.
Antes de descrevermos o RSA, estabeleceremos alguns resultados de Teoria dos
Números que serão usados para explicar como o código funciona.
Definição 2.0.1. A função φ de Euler de um inteiro positivo m, denotada por φ(m),
é definida como o número de inteiros positivos menores do que ou iguais a m que são
relativamente primos com m.
Observamos que quando p é primo, φ(p) = p− 1.
Definição 2.0.2. Um conjunto {r1, r2, . . . , rφ(m)} é um sistema reduzido de reśıduos
módulo m se cada um de seus elementos é relativamente primo com m e ri 6≡ rj
(mod m) quando i 6= j.
10
Teorema 2.0.1 (Euler). Se m ∈ Z, m > 0 e a ∈ Z é tal que a ∈ Z∗m, então
aφ(m) ≡ 1 (mod m).
Prova. Seja {r1, r2, . . . , rφ(m)} um sistema reduzido de reśıduos módulo m. Como
mdc(a, m) = 1, então {ar1, ar2, . . . , arφ(m)} também é um sistema reduzido de reśıduos
módulo m (a demonstração deste resultado pode ser encontrada em [32, Teorema
2.12]). Isto implica que cada ari é congruente a exatamente um dos rj’s,
1 ≤ j ≤ φ(m). Logo o produto dos ari’s deve ser congruente ao produto dos rj’s
módulo m, ou seja,
ar1 · ar2 · · · arφ(m) ≡ r1 · r2 · · · rφ(m) (mod m).
Então
aφ(m)r1 · r2 · · · rφ(m) ≡ r1 · r2 · · · rφ(m) (mod m). (2.0.1)
Pelas caracteŕısticas de sistema reduzido de reśıduos módulo m, então o produto
Π
φ(m)
j=1 rj é relativamente primo com m. Podemos, então, cancelar Π
φ(m)
j=1 rj em ambos
os lados da congruência (2.0.1), obtendo
aφ(m) ≡ 1 (mod m).
�
11
Teorema 2.0.2. Sejam a, b, m ∈ Z com m > 1 e a ∈ Z∗m. Então a congruência
ax ≡ b (mod m) possui solução única módulo m.
Prova. Este resultado é uma conseqüência do Teorema 2.8 apresentado em [32].
�
2.1 Geração das Chaves
Nesse criptossistema, cada usuário possui uma chave de codificação e outra de
decodificação. Para gerar o par de chaves cada usuário realiza o seguinte pré-cálculo:
• Seleciona-se dois primos grandes p e q (veremos mais adiante que tais primos
devem obedecer alguns requisitos para manter a segurança do método).
• Calcula-se o produto n = pq e φ(n) = (p− 1)(q − 1).
• Gera-se um inteiro e, 1 < e < φ(n) tal que mdc(e, φ(n)) = 1 (também temos
que tal expoente deve obedecer certos critérios de segurança [24, §8.2.2 Security
of RSA]).
• Determina-se d, 0 ≤ d < φ(n) tal que ed ≡ 1 mod φ(n), ou seja, d é o inverso
multiplicativo de e módulo φ(n).
A geração dos primos p e q será discutida no caṕıtulo seguinte sobre primalidade.
Obtidos tais primos, facilmente se calcula n e φ(n). Usando-se um gerador pseudo-
aleatório podemos obter e e determinamos o mdc(e, φ(n)) através do algoritmo de
Euclides cuja a complexidade é O(lg2(φ(n))) [7, Cap.4]. A solução d da congruência
12
ed ≡ 1 mod φ(n) também pode ser obtida através do algoritmo estendido de Euclides
[13, Seção 31.4].
Feitos os cálculos acima, o usuário publica P = (e, n) como chave de codificação
e mantém em segredo S = (d, n) (na verdade, somente d é mantido em segredo) que
é a chave de decodificação.
Observamos que d determinado acima existe e é único, conforme o Teorema 2.0.2.
2.2 Codificação e Decodificação
Agora veremos como as chaves P e S geradas acima são aplicadas para codificar
e decodificar mensagens. Inicialmente, a mensagem é convertida em uma seqüência
de números binários. Essa seqüência gerada é quebrada em blocos de bits que repre-
sentam inteiros m no intervalo [0, n). Então cada bloco m é codificado.
A codificação associada a chave P = (e, n) é feita através da função
P (m) = me (mod n)
e a decodificação de uma cifra c := P (m) em relação a chave S = (d, n) é dada por
S(c) = cd (mod n).
Dessa forma, o RSA é um criptossistema cujo alfabeto de entrada é o alfabeto
binário, o espaço de posśıveis mensagens e o espaço de mensagens codificadas é o
conjunto Zn.
As exponenciações modulares podem ser efetuadas rapidamente como citamos
no Exemplo 1.2.2. Além disso, temos que calcular a inversa da função exponencial
módulo n é computacionalmente intratável.
13
Chega o momento de se verificar se o método acima realmente funciona, ou seja, se
decodificando um bloco codificado obtemos o bloco da mensagem original. O próximo
teorema responde a esta questão.
Teorema 2.2.1. A decodificação do RSA funciona.
Prova. Seja c = P (m) = me (mod n) a codificação de um bloco m. Como
ed ≡ 1 mod φ(n), existe t talque ed = 1 + tφ(n). Se mdc(m, p) = 1, usando o
Teorema 2.0.1 temos que mp−1 ≡ 1 (mod p). Então (mp−1)t(q−1) =
= mt(p−1)(q−1) ≡ 1 (mod p) ⇒ m1+t(p−1)(q−1) = med ≡ m (mod p). Agora, se
mdc(m, p) = p, então a última congruência é válida novamente pois cada lado é
congruente a 0 módulo p. Assim, temos med ≡ m (mod p) em todos os casos.
De forma análoga, med ≡ m (mod q). Como p e q são primos distintos, então
med ≡ m (mod n). Dáı, cd = (me)d ≡ m (mod p).
�
2.3 Assinatura Digital
Uma caracteŕıstica importante do sistema RSA é que S(P (m)) = P (S(m)), isto
é, S e P comutam. De fato,
S(m) ≡ md mod n ⇒ P (S(m)) ≡ (md)e mod n ⇒
P (S(m)) ≡ med mod n ⇒ P (S(m)) ≡ m mod n,
e conforme a demonstração do Teorema 2.2.1 temos S(P (m)) ≡ m mod n.
14
Os sistemas em que a codificação e a decodificação comutam são ditos sistemas
comutativos e admitem uma assinatura digital natural.
Assim, no sistema RSA é posśıvel “decodificar” uma mensagem e depois
“codificar” o resultado. Suponhamos que um usuário A deseje enviar uma mensagem
assinada a um usuário B. Para isso, basta que A envie o texto SA(m). Somente A
tem a chave secreta SA usada para computar SA(m). B aplica a chave pública de A
a SA(m) para obter o texto original m = PA(SA(m)). Qualquer usuário com o uso de
PA pode verificar que A é realmente o remetente da mensagem, pois somente A tem
acesso a chave SA.
2.4 Segurança do RSA
Veremos que a segurança do RSA depende em grande parte da dificuldade em
fatorar números grandes. Analisaremos as posśıveis maneiras de obter a mensagem
original codificada pelo RSA.
Fatorar n implica decodificar uma mensagem no RSA, pois encontrando os fatores
de n, é posśıvel calcular φ(n). Como ed = 1 (mod φ(n)), então a solução d dessa
congruência pode ser obtida facilmente através do Algoritmo Estendido de Euclides.
Agora, analisaremos algumas posśıveis maneiras de obter a mensagem original
codificada pelo RSA conhecendo-se somente a chave pública.
Suponhamos que seja posśıvel determinar de alguma forma φ(n) usando o par
(e, n) sem ter que fatorar n. Logo, n e φ(n) são conhecidos. Sabendo que existem p
e q tais que n = pq e φ(n) = (p− 1)(q − 1) temos que
φ(n) = (p− 1)(q − 1) = pq − (p + q) + 1 = n− (p + q).
15
Assim, conhecemos p + q = n− φ(n) + 1. Também temos que
(p + q)2 − 4n = (p2 + 2pq + q2)− 2pq = p2 − 2pq + q2 = (p− q)2.
A partir disso, o valor de p− q =
√
(p + q)2 − 4n também é conhecido. De posse dos
valores de p+ q e p− q, obtemos os valores de p e q, isto é, achamos a fatoração de n.
Se de alguma maneira podermos determinar d somente com o conhecimento de n
e e, então encontramos a fatoração de n. De fato, como ed− 1 = tφ(n), isto significa
que encontramos um múltiplo de φ(n). É posśıvel fatorar n a partir de qualquer
múltiplo de φ(n). Miller [25] mostrou que considerando-se a Hipótese Estendida de
Riemman, isto pode ser feito de maneira eficiente.
Outra maneira de se conseguir m seria inverter a função de codificação, isto é,
encontrar a raiz e-ésima módulo n. Até agora não se conseguiu provar que inverter
a função de codificação, dado o par (e, n) e a codificação de c := me (mod n), é
equivalente a fatorar n. Porém sabemos que este problema é computacionalmente
inviável, conforme exemplo 1.2.2.
Até o momento, não se conhece uma maneira eficiente de fatorar um número
grande. Assim, o RSA tem se mostrado seguro com a tecnologia atual.
Para manter tal segurança deve-se tomar alguns cuidados para com relação a
escolha dos parâmetros p e q:
• os números p e q não podem ser próximos um do outro, caso contrário estarão
próximos da
√
n o que torna posśıvel fatorar n através da fatoração de Fermat
que será apresentado no último caṕıtulo.
16
• Os números p − 1 e q − 1 devem ter fatores primos grandes. Com alguns
algoritmos de fatoração conhecidos, fica fácil fatorar n se p − 1 e q − 1 tem
fatores pequenos, como é o caso do algoritmo ρ− 1 de Pollard.
• O mdc(p− 1, q − 1) deve ser pequeno [10, Cap.4]
17
Caṕıtulo 3
Testes de Primalidade
Desde a antiguidade até os tempos atuais, os números primos têm atráıdo a
atenção de muitos estudiosos. Em tempos remotos, Erastóstenes (240 a.C aproxi-
madamente) desenvolveu uma maneira de determinar se um dado inteiro positivo n
é primo. Para isto basta tentar dividir n por todos os inteiros menores do que ou
iguais a
√
n (em [32] o Teorema 1.15 garante que se n não é primo, então n tem um
fator primo menor do que ou igual a
√
n). Assim se n não for diviśıvel por nenhum
dos números, então n é primo. Tal método é conhecido como Crivo de Erastóstenes.
No entanto, este método torna-se impraticável quando n é muito grande.
Posteriormente, surgiram outros métodos como, por exemplo, o Teste de Pepin
que determina se um número de Fermat é primo, o Teste de Lucas-Lehmer para
determinar a primalidade de um número de Mersenne , e outros.
Atualmente, uma das razões para que a primalidade de números tenha recebido
mais atenção é o seu uso em diversos criptossistemas como, por exemplo, o RSA.
Vimos que é de grande importância para a Criptografia RSA a capacidade de produzir
primos grandes de forma genérica e provar que estes são realmente primos.
18
O problema de gerar um primo grande, a prinćıpio, pode ser resolvido escolhendo-
se inteiros aleatórios em um intervalo espećıfico e testando a primalidade de tais
números.
Neste caṕıtulo, apresentaremos alguns dos testes de primalidade existentes, nos
restringindo àqueles que testam a primalidade de números genéricos . Os dois pri-
meiros testes apresentados são testes probabiĺısticos: o teste de Solovay-Strassen e o
teste de Miller-Rabin com bases em resultados importantes da Teoria de Números. É
importante ressaltarmos que tais testes quando respondem que dado número é primo
devemos ter em mente que isto é apenas uma boa evidência que tal número seja
mesmo primo. Em muitas aplicações isto já é o suficiente, como é o caso em que
procuramos por um primo grande. No entanto, estes testes não produzem certifica-
dos de primalidade, provas de que o número seja realmente primo. E se realmente é
necessária uma prova de primalidade aplica-se outros tipos de testes, como é o caso do
algoritmo de Goldwasser-Killian e de Atkin, baseados na teoria de curvas eĺıpticas.
Tais algoritmos, no entanto, não fazem parte deste trabalho. Maiores informações
sobre esses algoritmos podem ser obtidas em [6] e [17].
Por último, apresentaremos um algoritmo determińıstico que testa a primalidade
de um número em tempo polinomial. Tal algoritmo foi apresentado recentemente,
constituindo um dos mais novos resultados relacionados à primalidade e que tem
ganho grande admiração por todos da área.
19
3.1 Distribuição de Primos
Para gerar um primo em um intervalo dado escolhemos um inteiro ı́mpar aleatório
e verificamos se este inteiro é primo. Se não for primo, geramos outro inteiro e
testamos sua primalidade. Continuamos com este processo até encontrarmos um
número primo.
Mas quantos candidatos devemos testar até encontrar um provável primo? A
melhor forma de responder à esta pergunta é usando a chamada função π. Se x > 0,
π(x) é definida como sendo o número de primos menores do que ou iguais a x.
O Teorema dos Números Primos [1] afirma que:
lim
x→∞
π(x)
x
log(x)
= 1.
Então, x
log(x)
é uma boa aproximação para π(x) quando x for suficientemente
grande. Assim, podemos estimar que um inteiro x escolhido aleatoriamente tem pro-
babilidade igual a 1
log(x)
de ser primo, isto é, temos que examinar aproximadamente
log(x) inteiros próximos de x para acharmos um número primo da mesma ordem que
x. Um exemplo disso é que temos que testar log 10100 ≈ 230 candidatos, aproxima-
damente, até encontrarmos um primo de 100 d́ıgitos decimais, e este valor pode ser
reduzido à metadese considerarmos somente os números ı́mpares. Uma média de 115
candidatos que terão que ser testados.
20
3.2 Teste de Solovay-Strassen
A fim de descrever o teste de Solovay-Strassen introduziremos alguns conceitos
matemáticos, incluindo o Critério de Euler.
Definição 3.2.1. Sejam p um primo positivo ı́mpar e a ∈ Z. Se a ∈ Z∗p e se existe
uma solução da congruência
x2 ≡ a mod p,
então a é chamado um reśıduo quadrático módulo p. Se não existe solução, então a
é dito ser um reśıduo não quadrático módulo p.
Definição 3.2.2. Seja a um inteiro. Para um primo ı́mpar p > 1, definimos o
śımbolo de Legendre
(
a
p
)
por
(
a
p
)
=

0, se a ≡ 0(mod p)
1, se a é reśıduo quadrático mod p
−1, se a é reśıduo não quadrático mod p.
Definição 3.2.3. Seja um número n > 1 um inteiro ı́mpar com decomposição
n =
k∏
i=1
peii .
Então o Śımbolo de Jacobi é definido como(a
n
)
=
k∏
i=1
(
a
pi
)ei
=
(
a
p1
)e1 ( a
p2
)e2
. . .
(
a
pk
)ek
.
O śımbolo de Jacobi é uma generalização do śımbolo de Legendre.
Propriedades do Śımbolo de Jacobi Sejam m e n inteiros ı́mpares positivos, e
sejam a, b inteiros. Então
a.
(
a
mn
)
=
(
a
m
) (
a
n
)
21
b.
(
a
n
)
=
(
b
n
)
, se a ≡ b(mod n).
As demonstrações destas propriedades se encontram em [7, Teorema 5.9.2].
Teorema 3.2.1 (Critério de Euler). Se p é um primo positivo ı́mpar e a ∈ Z∗p,
então
a
p−1
2 ≡
(
a
p
)
(mod p). (3.2.1)
Prova. Suponhamos, primeiramente, que
(
a
p
)
= 1. Então, existe x tal que
x2 ≡ a(mod p). Do fato que mdc(a, p) = 1 e p|(x2−a) conclúımos que mdc(x, p) = 1.
Logo, pelo Teorema 2.0.1, xp−1 ≡ 1(mod p) e, portanto,
a
p−1
2 ≡
(
x2
) p−1
2 = xp−1 ≡ 1(mod p).
Consideremos agora o caso
(
a
p
)
= −1. Já vimos acima que se a for um reśıduo
quadrático então x
p−1
2 ≡ 1(mod p). A congruência f(x) = x p−12 −1 ≡ 0(mod p) possui
no máximo p−1
2
soluções incongruentes módulo p (ver Teorema 5.2 em [32]).
No entanto, do fato de existirem p−1
2
reśıduos quadráticos e de termos
a
p−1
2 ≡ 1(mod p) para todo reśıduo quadrático, conclúımos que todos estes reśıduos
quadráticos são soluções de f(x) ≡ 0(mod p), o que nos garante que f(x) ≡ 0(mod p)
possui
exatamente p−1
2
ráızes, e que se a não for reśıduo quadrático, isto é,
(
a
p
)
= −1,
então a
p−1
2 6≡ 1(mod p).
Como ap−1 − 1 = (a p−12 − 1)(a p−12 + 1) e ap−1 − 1 ≡ 0(mod p) para mdc(p, a) = 1,
conclúımos que a
(p−1)
2 ≡ ±1(mod p).
Assim, se
(
a
p
)
= −1, temos a p−12 ≡ −1(mod p). Portanto, a p−12 =
(
a
p
)
(mod p).
�
22
Desta forma, o Critério de Euler nos diz que se a
n−1
2 6≡
(
a
n
)
(mod n) para algum
a tal que a ∈ Z∗n, então n é composto e a é dito testemunha da composição de n. Se
um número n composto satisfaz a congruência (3.2.1), n é denominado pseudoprimo
de Euler para a base a. Chamamos de número de Carmichael o composto n que
satisfaz (3.2.1) para todo a ∈ Z∗n.
Lema 3.2.1. Se n é um número de Carmichael, então n não é diviśıvel pelo quadrado
de nenhum primo e é diviśıvel por pelo menos 3 primos distintos.
Prova. Demonstração em [7, Teorema 9.3.6].
�
Consideraremos, agora, o conjunto E(n), importante nos próximos resultados,
definido como o conjunto de bases a ∈ Z∗n tal que n satisfaz a congruência (3.2.1) do
Critério de Euler, ou seja,
E(n) =
{
a ∈ Z∗n :
(a
n
)
≡ a
n−1
2 (mod n)
}
.
Lema 3.2.2. Seja n um inteiro ı́mpar, n ≥ 3. Portanto, n é primo se, e somente se,
E(n) = Z∗n.
Prova. Se n é primo, então, usando o Critério de Euler, temos
(
a
n
)
≡ an−12 (mod n)
para todo a ∈ Z∗n. Logo, E(n) = Z∗n.
Reciprocamente, suponhamos que E(n) = Z∗n e n seja composto. Então, para
todo a ∈ Z∗n tem-se:
an−1 ≡
(a
n
)2
≡ 1(mod n).
23
Como n é um número de Carmichael, então não é diviśıvel pelo quadrado de
nenhum primo (conforme Lema 3.2.1). Então n = p · q, com p primo, q > 1 e
mdc(p, q) = 1. Sejam g um reśıduo não quadrático módulo p, e seja a ≡ g(mod p) e
a ≡ 1(mod q), pelas propriedades do śımbolo de Jacobi temos que
(a
n
)
=
(
a
pq
)
=
(
a
p
) (
a
q
)
=
(
g
p
) (
1
q
)
= (−1)(+1) = −1.
Já que supomos que
(
a
n
)
= −1 ≡ an−12 (mod n) para todo a ∈ Z∗n ⇒
⇒ an−12 ≡ −1(mod q), o que contradiz o fato de a ≡ 1(mod q).
�
Baseado no teorema acima descoberto por R. Solovay e V. Strassen, inicialmente
apresentado em [34], descreveremos a seguir um algoritmo para testar a primalidade
de um número ı́mpar ≥ 3.
Algoritmo 1 (SOLOVAY-STRASSEN(n)).
escolha a aleatório em {1, . . . , n− 1}
1. se mdc(a, n) 6= 1
então retorne “composto” e pare
senão
2. se
(
a
n
)
6≡ an−12 (mod n)
então retorne “composto” e pare
senão retorne “primo”
24
O algoritmo SOLOVAY-STRASSEN [7] nos diz que tomando-se aleatoriamente um
número a ∈ {1, . . . , n− 1} onde n é um inteiro ı́mpar, verificamos se mdc(a, n) 6=
1, o que implica n ser composto. Mas se mdc(a, n) = 1, computamos o reśıduo
ε = a
n−1
2 (mod n) e o śımbolo de Jacobi δ =
(
a
n
)
. Se δ = ε, então o algoritmo retorna
que n é primo. Caso contrário, n é composto.
Obviamente, se n é primo, o algoritmo responderá corretamente, pois no passo (1)
o algoritmo nunca encontrará mdc não trivial e pelo Critério de Euler a congruência
sempre é satisfeita e o passo (2) sempre retornará que n é primo.
Mas sendo n composto, qual a probabilidade de o algoritmo retornar “primo”? A
proposição a seguir afirma que a probabilidade de erro menor do que ou igual a 1
2
.
Teorema 3.2.2. Se n é um número composto ı́mpar, então para pelo menos metade de
todas bases a ∈ {1, . . . , n−1} o algoritmo SOLOVAY-STRASSEN retornará “composto”.
Prova. Seja n um composto ı́mpar. Se a /∈ Z∗n, o passo (1) retorna “composto”.
Consideremos a ∈ Z∗n. Usando o Lema 3.2.2, temos E(n) 6= Z∗n. Como E(n) é
subgrupo de Z∗n, segue que E(n) é um subgrupo próprio de Z∗n. Logo:
|E(n)| ≤ 1
2
|Z∗n| ≤
n− 1
2
,
pelo Teorema de Lagrange.
Portanto, no máximo metade dos números entre 1 e n − 1 conduzirão a uma
resposta de que n é primo.
�
25
O algoritmo SOLOVAY-STRASSEN tem complexidade O(lg3 n) bit operações, já que
podemos calcular mdc(a, n) e o śımbolo de Jacobi
(
a
n
)
usando O(lg2 n) bit operações,
e a
n−1
2 (mod n) usando O(lg3 n) bit operações (para maiores detalhes da complexidade
acima ver [7, Teorema 9.4.2]).
Assim, o resultado de Solavay e Strassen nos garante que se n é um primo,
o algoritmo sempre retornará “primo”, pois a congruência (3.2.1) vale para cada
a ∈ {1, . . . , n − 1} gerado e também garante uma margem de erro menor do que ou
igual a 1
2
para cada vez que aplicarmos o algoritmo para uma determinada base a,
se n não é primo. Se aplicarmos o teste k vezes para distintos valores de a, então as
chances de n ser realmente primo, quando o teste o declara primo, é de pelo menos
1− 1
2k
.
3.3 Teste de Miller-Rabin
Discutiremos, agora, outro teste probabiĺıstico baseado no conceito de
pseudoprimo forte. Inicialmente, veremos alguns resultados importantes relaciona-
dos ao teste de Miller e Rabin
Definição 3.3.1. O menor expoente e tal que ae ≡ 1(mod n) é chamado ordem de a
módulo n e denotado por e = ordna.
Lema 3.3.1 (Pocklington). Seja n um inteiro positivo. Suponhamos que
n − 1 = qkr, k ≥ 1, onde q é primo e q - r. Se existe a tal que an−1 ≡ 1(mod n) e
mdc(a
n−1
q − 1, n) = 1, então para todo primo p|n temos p ≡ 1(mod qk).
26
Prova. Suponhamos que a satisfaça as hipóteses do lema. Seja p um primo tal que
p|n e seja t = ordpa. Como an−1 ≡ 1(mod n), sabemos que an−1 ≡ 1(mod p). Assim,
t|(n−1) = qkr. Além disso, como mdc(a
n−1
q −1, n) = 1, então temos a
n−1
q 6≡ 1(mod p)
e t não divide (n − 1)/q = qk−1 · r. Dáı, qk|t. Já que t|(p − 1) segue que qk|p − 1.
Portanto, p ≡ 1(mod qk).
�
Teorema 3.3.1. Seja n ı́mpar e n− 1 = 2kq com q ı́mpar e k ≥ 1. Se n é primo e
a ∈ Z∗n, então aq ≡ 1(mod n) ou existe um i ∈ {0, 1, . . . , k − 1} tal quea2
iq ≡ −1(mod n).
Prova. Consideremos a seguinte seqüência de potências módulo n:
aq, a2q, . . . , a2
k−1q, a2
kq.
Se n for um número primo, então pelo menos uma destas potências tem que ser
congruente a 1 módulo n, pois, pelo Teorema de Euler, temos
a2
kq = an−1 ≡ 1(mod n).
Seja i ≥ 1 o menor expoente tal que a2iq ≡ 1(mod n). Podemos escrever
a2
iq − 1 = (a2i−1q − 1)(a2i−1q + 1).
Como n é primo e n|(a2iq − 1), então ou n|(a2i−1q − 1) ou n|(a2i−1q + 1). Sendo i o
menor expoente tal que a2
iq − 1 é diviśıvel por n, então a2i−1q − 1 não é diviśıvel por
n. Segue que n divide a2
i−1q + 1, isto é, a2
i−1q ≡ −1(mod n).
27
Conclúımos que se n é primo, então uma das potências da seqüência dada tem que
ser congruente a −1 módulo n quando i ≥ 1. Agora, se i = 0 então aq ≡ 1(mod n) e
a esta congruência não podemos aplicar o produto notável, pois q é ı́mpar.
Portanto, se n é primo, então uma das potências da seqüência é congruente a
−1 módulo n ou aq ≡ 1(mod n).
�
A seguir apresentaremos dois lemas importantes na análise do teste de Miller-
Rabin. Para isto, definimos o conjunto
S(n) = {a ∈ Z∗n ; aq ≡ 1(mod n) ou a2
iq ≡ −1(mod n)}
para algum 0 ≤ i < t onde n − 1 = 2tq. Todo a 6∈ S(n) é dito testemunha forte da
composição de n.
Um número composto n tal que existe a ∈ S(n) é chamado de pseudoprimo forte.
Lema 3.3.2. Seja n ≥ 3 um inteiro ı́mpar. S(n) = Z∗n se, e somente se, n é primo.
Prova. Suponhamos que ∃a ∈ Z∗n tal que a não está em S(n), então a é testemunha
da composição de n. Logo, n é composto.
Reciprocamente, seja n primo. Se a ∈ Z∗n arbitrário, temos que an−1 ≡ 1(mod n).
Como
(a
n−1
2 )2 = an−1 ≡ 1(mod n)
e a equação x2 ≡ 1(mod n) tem somente duas soluções, a saber x = ±1, então
a
n−1
2 = a2
t−1q ≡ ±1(mod n).
28
Se a
n−1
2 ≡ −1(mod n), então a ∈ S(n). Agora, se an−12 ≡ +1(mod n), novamente
temos
a
n−1
4 = a
2tq
4 = a2
t−2q ≡ ±1(mod n).
Prosseguindo desta maneira, para qualquer a ∈ Z∗n teremos ou aq ≡ 1(mod n) ou
a2
jq ≡ −1(mod n) para algum j , 0 ≤ j < t.
�
Lema 3.3.3. Se n > 3 é um composto ı́mpar, então |S(n)| ≤ n−1
4
.
Prova. Suponhamos que n = 1 + 2tq, com q ı́mpar, seja um número composto.
Podemos escrever n = pe11 · · · perr . Seja k o maior inteiro tal que exista pelo me-
nos um b ∈ Z∗n com b2
k ≡ −1(mod n). Notamos que k está bem definido, pois
(−1)20 ≡ −1(mod n) e assim k ≥ 0. Também temos k ≤ v(u)− 1, onde u é o menor
inteiro positivo tal que au = 1,∀a ∈ Z∗n e v(u) é o maior inteiro tal que 2v(u)|u.
Temos pi ≡ 1 (mod 2k+1), 1 ≤ i ≤ r, pelo Lema 3.3.1, então n ≡ 1(mod 2k+1).
Tomemos m = 2kq. Então 2m | (n− 1). Consideremos os seguintes subgrupos de
Z∗n:
J = {a ∈ Z∗n ; an−1 ≡ 1(mod n)}
K = {a ∈ Z∗n ; am ≡ ±1(mod p
ei
i ),∀i}
L = {a ∈ Z∗n ; am ≡ ±1(mod n)}
M = {a ∈ Z∗n ; am ≡ 1(mod n)} .
Temos
M ⊆ L ⊆ K ⊆ J ⊆ Z∗n.
29
Vemos que todo a ∈ S(n) também pertence a L, pois se aq ≡ 1(mod n), então
é óbvio que am ≡ 1(mod n), enquanto que se a2sq ≡ −1(mod n) para algum s então
s ≤ k, pela definição de k. Mostraremos que, desde que n 6= 9, L é um subgrupo de
ı́ndice pelo menos 4 em Z∗n e, a partir disto, temos que |S(n)| ≤ n−14 .
Todo elemento de G = {a ∈ Z∗n; a ≡ ±1(mod p
ei
i ),∀i} é uma 2k-ésima potência; dáı
uma m-ésima potência, basta tomar x ≡ b ou x ≡ b2(mod peii ) que implica que x2
k ≡
±1(mod peii ) para cada i. Dessa maneira, M tem ı́ndice 2r em
K = {a ∈ Z∗n ; am ∈ G}. Analogamente, M tem ı́ndice 2 em L. Assim,
(K : L) = 2r−1. Logo,
(Z∗n : L) ≥ (Z∗n : J)(K : L) = 2r−1(Z∗n : J).
Se r ≥ 3, segue que (Z∗n : J) ≥ 4.
No entanto, se r = 2 então n não pode ser um número de Carmichael que é diviśıvel
por pelo menos 3 primos distintos (Lema 3.2.1). Então ∃a ∈ Z∗n com an−1 6≡ 1(mod n),
e assim J é um subgrupo próprio de Z∗n e portanto (Z∗n : J) ≥ 2. Logo, (Z∗n : L) ≥ 4.
Finalmente, se r = 1 então n = pe, e ≥ 2. Mas então, |J | = p − 1, e (Z∗n : J) =
= pe−1 ≥ 4, exceto quando pe = 9. Quando n = 9 existem exatamente 2 elementos
de S(n), a saber 1 e −1. Então, o número de elementos é ≤ n−1
4
.
�
Como resultado deste lema, descreveremos um algoritmo para testar a primali-
dade de n [7, Cap.9].
30
Algoritmo 2 (MILLER-RABIN(n)).
1. escolha a ∈ {1, . . . , n− 1} aleatório
2. escreva n− 1 = 2tq, q ı́mpar
3. calcule sucessivamente a0 = a
q(mod n), a1 = a
2
0(mod n), . . . , ak = a
2
k−1(mod n)
até que k = t ou ak ≡ 1(mod n)
4. se k = t e ak 6≡ 1(mod n) retorne “composto”
5. senão se k = 0 então retorne “primo”
6. senão se ak−1 6≡ −1 (mod n) então retorne “composto”
7. senão retorne “primo”
Teorema 3.3.2. Se n é primo, então MILLER-RABIN sempre retornará “primo”.
Prova. No passo (4) nunca retornará “composto”, já que sempre existe j tal que
a2
jq ≡ 1(mod n), 1 ≤ j ≤ t. Seja k o menor ı́ndice tal que ak ≡ 1(mod n), isto
é, ak = a
2kq ≡ 1(mod n). Se k = 0, o algoritmo retornará “primo” em (5). Caso
contrário, devemos ter ak−1 ≡ −1(mod n), o algoritmo retorna “primo” nos passos
(6) e (7).
�
31
Teorema 3.3.3. Se n é um número composto, então o algoritmo MILLER-RABIN re-
torna “composto” para pelo menos 3
4
de todos os a ∈ Z∗n.
Prova. Seja n um composto ı́mpar. Se a 6∈ Z∗n, então nunca acontecerá a situação
onde teremos a2
tq ≡ 1(mod n). Teremos então k = t e ak 6≡ 1(mod n). Logo, o passo
(4) declarará que n é composto.
Agora, se a ∈ Z∗n, pelo Lema 3.3.3 temos que pelo menos 3/4 de todos a ∈ Z∗n são
testemunhas fortes da composição de n e para estes valores de a o algoritmo retornará
“composto”.
�
Observamos que a maior parte do tempo gasto pelo algoritmo é para calcular aq,
a2q, . . ., a2
tq(mod n). Podemos calcular aq(mod n) usando O(lg3 n) bit operações via
um algoritmo que calcula potências módulo n (detalhes da complexidade do algoritmo
em [7, Teorema 9.4.5]) , e para calcular o restante das potências fazendo o quadrado
módulo n que também usa O(lg3 n) bit operações.
Desta forma, se n é primo, o algoritmo responderá corretamente que n é primo.
Mas, se n é composto, as chances do algoritmo retornar “primo” é de no máximo
1
4
. Assim, o algoritmo procurará encontrar uma testemunha de composição para n.
Se nenhuma testemunha é encontrada, então é declarado “primo” com probabilidade
de acerto de pelo menos 1 − 1
4
. E se não é detectada nenhuma testemunha após k
aplicações do teste de Miller-Rabin com diferentes bases aleatórias, a taxa de erro
diminui para 1
4k
.
Entretanto, tal taxa de erro é frequentemente muito menor. Monier [26] dá uma
fórmula exata para esta margem de erro, que nunca excede (φ(n)/2r−1 − 2)/(n − 3)
32
onde r é o número de fatores primos distintos de n e φ(n) é a função de Euler.
Miller [25] e Bach [8] observaram que se assumirmos que a Hipótese Generalizada
de Riemann é verdadeira, um número é primo se, e somente se, passa pelo teste para
todas as bases a com 1 < a ≤ 2(log(n))2. Isto faz com que o teste de Miller-Rabin
se torne determińıstico. Também podemos obter uma versão determińıstica para o
teste de Solovay-Strassen considerando a Hipótese Generalizada de Riemann.
3.4 Teste de Agrawal-Kayal-Saxena
Até há pouco tempo atrás, os algoritmos existentes para testar primalidade ou
eram probabiĺısticos com complexidade polinomial ou eram determińısticos mas pouco
eficientes ou dif́ıceis de implementar.
Porém em 2002, Agrawal, Kayal e Saxena do Instituto Indiano de Tecnologia em
Kanpur anunciaram um teste de primalidade determińıstico polinomial que sempre
funciona sem considerar conjecturas. Além disso, as ferramentas matemáticas empre-
gadas são consideravelmente mais simples que em testes anteriores (em particular, o
teste APR [2]).
A idéia básica de tal teste tem como suporte o seguinte teorema.
Teorema 3.4.1. Suponha que a ∈ Z∗p. Então p > 1 é primo se, e só se,
(x− a)p ≡ (xp − a) (mod p). (3.4.1)
Prova. Pelo Teorema Binomial de Newton, temos que (x − a)p=
=
∑p
i=0
(
p
i
)
(−1)p−ixiap−i. Podemos escrever P (x) = (x − a)p − (xp + (−a)p) =
33
=
∑p−1
i=1
(
p
i
)
(−1)p−ixiap−i.
Supondo p primo, temos ap ≡ a mod p (Lema 3.4.4). Caso p ı́mpar, então
(−a)p = −ap ≡ −a mod p. Caso p = 2, temos −a ≡ a mod 2, dáı (−a)p =
= ap ≡ a ≡ −a mod 2. Logo, P (x) = (x−a)p− (xp−a). Como
(
p
i
)
≡ 0 (mod p)
para 1 ≤ i < p, já que p aparece no numerador de
(
p
i
)
, mas não no denominador.
Logo, P (x) ≡ 0 (mod p).
Suponhamos que p seja composto. Seja q um primo divisor de p e seja k ≥ 1
o maior inteiro tal que qk | p (p = qkc, c ∈ Z). Temos que
(
p
q
)
= p!
q!(p−q)! =
= q
k−1c(p−1)!
(q−1)!(p−q)! .
Vamos mostrar que p não divide
(
p
q
)
. Suponhamos que p divide
(
p
q
)
. Então
qk divide
(
p
q
)
. Isto significa que q divide
(p− 1)!
(q − 1)!(p− q)!
=
(p− 1)(p− 2) · · · (p− q + 1)(p− q)!
(q − 1)!(p− q)!
=
(p− 1)(p− 2) · · · (p− q + 1)
(q − 1)!
.
Logo, q|(p − j) para algum j ∈ {1, . . . , q − 1}. Assim, q|j, o que é contradição
pois j < q e q primo.
Desta forma,
(
p
q
)
6≡ 0 (mod p), 1 < q < p. Sendo mdc(a, p) = 1, então(
p
q
)
ap−q 6≡ 0 (mod p), que é o coeficiente de xq em (x−a)p. Mas como o coeficiente
de xq em xp − a é nulo, temos xp − a 6≡ (x− a)p mod p.
�
34
Examinando a expansão binomial inteira de (x− a)n, tal resultado nos garantiria
uma maneira infaĺıvel de saber se n é primo, pois caso todos os termos que estão no
“meio” da expansão tivessem coeficientes diviśıveis por n, então n seria primo, caso
contrário teŕıamos n composto.
Mas um detalhe torna este tipo de teste impraticável, já que para n muito grande,
teremos que examinar muitos termos na expansão binomial.
A idéia do AKS é tornar o teste binomial rápido e ainda ser capaz de provar que o
teste responde corretamente mesmo quando n é composto. Ao invés de trabalharmos
com módulo n, trabalhamos com módulo um polinômio xr − 1 (onde r é um primo
razoavelmente pequeno). Ou seja, no lugar de calcular (x− a)n, calcula-se o resto da
divisão de (x− a)n por xr − 1, que é feito usando o mesmo método em Álgebra para
dividir um polinômio por outro. Dessa maneira, teremos no máximo r − 1 termos
para examinar , enquanto que na expansão de (x− a)n temos n− 1.
Como a congruência original funciona sempre que n é primo, então é óbvio que a
nova congruência
(x− a)n ≡ (xn − a) mod (xr − 1, n) (3.4.2)
também funciona quando n é primo, pois se duas coisas são iguais, então quando se
divide essas duas coisas por xr − 1, os restos são iguais também. O que não é óbvio
é que a nova congruência é sempre falsa quando n é composto, pois mesmo quando
(x− a)n 6≡ (xn − a) (mod n)
é posśıvel que dois diferentes polinômios tenham o mesmo resto quando divididos por
xr − 1. O que o AKS mostra é que se n é composto, e se escolhemos o valor “certo”
35
de r, então precisamos testar apenas um número pequeno de a’s até encontrarmos
um tal que
(x− a)n 6≡ (xn − a) mod (xr − 1, n).
Uma vez que encontramos tal a, provamos que n é composto. Ademais, não
precisamos tomar a aleatoriamente, existe uma forma determińıstica para fazer isto.
A seguir, estabeleceremos alguns resultados que serão usados posteriormente.
3.4.1 Teoria dos Números
Lema 3.4.1. Seja π(n) o número de primos positivos ≤ n. Então
n
6 log2 n
≤ π(n) ≤ 8n
log2 n
,
∀n ≥ 1.
Prova. No Teorema 4.6 em [5, Cap. 4], temos a seguinte desigualdade:
n
6 log n
≤ π(n) ≤ 8n
log n
.
Vamos mostrar que a desigualdade também é válida para o logaritmo na base 2.
Como log n ≤ log2 n, então π(n) ≥ n6 log n ≥
n
6 log2 n
.
Também temos na demonstração do Teorema 4.6 em [5] o resultado
36
π(n) ≤ n
log n
(
6 log 2 +
3
e
)
= n
log2 e
log2 n
(
6 log 2 +
3
e
)
= n
log2 e
log2 n
(
6
1
log2 e
+
3
e
)
=
n
log2 n
(
6 +
3 log2 e
e
)
≤ n
log2 n
(
6 +
3× 1, 45
e
)
≤ 8n
log2 n
.
Portanto,
n
6 log2 n
≤ π(n) ≤ 8n
log2 n
.
�
Lema 3.4.2. Sejam n ≥ 2, k ≥ 1 e d ≥ 1 inteiros tais que (nk − 1)|(nd − 1). Então
k|d.
Prova. Seja d = qk + r, q ≥ 1 e 0 ≤ r < k. Observemos que
nd − 1
nk − 1
=
nr(nqr − 1) + (nr − 1)
nk − 1
= nr(1 + nk + n2k + · · ·+ n(q−1)k) + n
r − 1
nk − 1
.
Logo, (nr − 1)/(nk − 1) é um inteiro, pois (nk − 1) divide (nd − 1). Se 1 ≤ r < k,
então 0 < (nr − 1)/(nk − 1) < 1 o que não é posśıvel. Portanto, r = 0.
�
37
Para o próximo lema, consideraremos a função
π′(x) = |{p ; p é primo , 2 ≤ p ≤ x e P (p− 1) > x2/3}|
onde P (n) é o maior divisor primo de n.
Lema 3.4.3. Existe uma constante c > 0 tal que
π′(x) ≥ c x
log2 x
para x suficientemente grande.
Prova. Em [15] temos que π′(x) ≥ c x
log x
. Como na demonstração do Lema 3.4.1,
obtemos π′(x) ≥ c x
log2 x
.
�
Lema 3.4.4. Sejam p primo e a um inteiro positivo. Então ap ≡ a (mod p).
Prova. Ver demonstração em [32, Corolário 2.1]
�
3.4.2 Corpos finitos
Sejam p um número primo positivo e d ≥ 1 um inteiro. O anel Zp é um corpo
com p elementos. Seja h(x) um polinômio irredut́ıvel de grau d no anel Zp[x], ou
seja, não existem polinômios a(x) e b(x) em Zp[x] ambos com grau ≤ d tais que
a(x)b(x) = h(x) em Zp[x]. O anel F := Zp[x]/(h(x)) consiste de todos os polinômios
em Zp[x] de grau ≤ d, onde a adição e a multiplicação são módulo h(x). [22]
38
Lema 3.4.5. O anel F é um corpo com pd elementos.
Prova. Como existem exatamente pd polinômios em Zp[x] com grau ≤ d, é óbvio
que |F| = pd. Para efeito de demonstração de que F é corpo, mostraremos somente
que cada polinômio não-nulo f(x) em F tem um inverso multiplicativo em F . Como
o grau de f(x) é ≤ d e como h(x) é irredut́ıvel, temos que mdc(f(x), h(x)) = 1.
Usando o algoritmo estendido de Euclides, obtemos dois polinômios a(x) e b(x) em
Zp[x] tais que
a(x)f(x) + b(x)h(x) = 1
em Zp[x]. Portanto, a(x) mod h(x) é o inverso multiplicativo de f(x).
�
Lema 3.4.6. Sejam K um corpo, f(x) um polinômio em K[x], e d ≥ 1 o grau de
f(x).
1. Existem no máximo d elementos α ∈ K tais que f(α) = 0.
2. Existem polinômios irredut́ıveis g1(x), . . . , gm(x) em K[x], para algum inteiro
m, tal que f(x) =
∏m
i=1 gi(x).
Prova. As demonstrações dos itens 1 e 2 se encontram em [22, Cap. 1] no Teorema
1.66 e no Teorema 1.59, respectivamente.
�
39
Lema 3.4.7. O grupo multiplicativo K∗ de qualquer corpo K é ćıclico.
Prova. Sejam q o número de elementos de K. Podemos assumir que q ≥ 3, ou seja,
que K é um corpo não-trivial. Seja s := q − 1 a ordem de K∗ e s = pr11 . . . prmm a sua
decomposição.
Para cada 1 ≤ i ≤ m, o polinômio xs/pi − 1 tem no máximo s/pi ráızes em K,
conforme Lema 3.4.6. Como s/pi < s, existe um elemento não nulo ai ∈ K∗ tal
que a
s/pi
i 6= 1, pois s é a ordem de K∗. Seja bi := a
s/p
ri
i
i . Como K
∗ é um grupo
multiplicativo de ordem s e ai ∈ K∗ então asi = 1. Segue que b
p
ri
i
i = a
s
i = 1. Seja ei
a ordem multiplicativa de bi em K. Então ei|prii . Sendo pi um número primo, temos
que ei = p
si
i para algum 0 ≤ si ≤ ri. Por outro lado, temos que b
p
ri−1
i
i = a
s/pi
i 6= 1.
Logo, si = ri e ei = p
ri
i .
Seja b := b1 . . . bm, e e a ordem multiplicativa de b em K. Afirmamos que b é um
gerador de K∗, ou seja, e = s. Suponhamos, por absurdo, o contrário. Já que bs = 1,
seque que e|s. Sendo e um divisor próprio de s, existe um ı́ndice 1 ≤ i ≤ m tal que e
divide s/pi. Suponhamos, sem perda de generalidade, que i = 1. Como b
e = 1, temos
que bs/p1 = 1. Observamos que
bs/p1 = b
s/p1
1 . . . b
s/p1
m .
Consideremos 2 ≤ j ≤ m qualquer. Temos que prjj divide s/p1. Como b
p
rj
j
j = 1,
segue que b
s/p1
j = 1. Assim,
1 = bs/p1 = b
s/p1
1 . . . b
s/p1
m = b
s/p1
1 .
40
Segue que a ordem de b1 divide s/p1. Como a ordem de b1 é p
r1
1 e s/p1 =
= pr1−11 p
r2
2 . . . p
rm
m , temos uma contradição.
�
Lema 3.4.8. Seja p ≥ 2 um primo e f(x) um polinômio em Zp[x]. Então,
f(x)p ≡ f(xp) (mod p).
Prova. A demonstração será feita por indução sobre o grau d de f(x).
Se d =0 então f(x) = a para algum a ∈ Zp. Sendo p primo, temos que
ap ≡ a (mod p) (Lema 3.4.4). Logo, o resultado é verdadeiro.
Seja d ≥ 1. Suponhamos que o resultado seja verdadeiro para todos os polinômios
em Zp[x] cujos graus sejam < d. Podemos reescrever f(x) = axd + g(x), onde a ∈ Zp
e g(x) é um polinômio em Zp[x] de grau menor do que d. Então,
(f(x))p = (axd + g(x))p
=
p∑
i=0
(
p
i
)
aixid(g(x))p−i.
Como
(
p
i
)
≡ 0 (mod p) para 1 ≤ i ≤ p− 1, temos
(f(x))p = (g(x))p + apxpd.
41
Pela hipótese de indução, (g(x))p ≡ g(xp) (mod p) e sendo ap ≡ a (mod p),
conclúımos que
(f(x))p = g(xp) + a(xp)d = f(xp).
�
Lema 3.4.9. Seja h(x) um fator qualquer de xr − 1. Se m ≡ mr (mod r), então
xm ≡ xmr (mod h(x)).
Prova. Seja m = kr+mr. Como, x
r ≡ 1 mod (xr−1), então xkr ≡ 1 mod (xr−1)
⇒ xkr+mr ≡ xmr mod (xr − 1) ⇒ xm ≡ xmr mod (xr − 1).
Portanto, xm ≡ xmr (mod h(x)).
�
Lema 3.4.10. Sejam p e r primos positivos distintos e d = ordrp . Então, todo
polinômio irredut́ıvel em Zp[x] que divide x
r−1
x−1 tem grau d.
Prova. Seja h(x) um polinômio irredut́ıvel em Zp[x] que divide x
r−1
x−1 e cujo grau é
k. Pelo Lema 3.4.5, temos que F é um corpo com pk elementos. Também temos que
F∗ é ćıclico de ordem pk − 1. Seja g(x) um gerador de F∗. Usando o Lema 3.4.8,
temos g(x)p ≡ g(xp) (mod p) ⇒ g(x)pd ≡ g(xpd) (mod p).
Seja f(x) o polinômio em Zp[x] tal que f(x)g(x) = xr − 1. Sendo
pd ≡ 1 (mod r) e usando o Lema 3.4.9, temos que xpd ≡ x mod h(x). Logo,
(g(x))p
d ≡ g(x) mod h(x).
Sendo g(x) um gerador, g(x) 6≡ 1 mod h(x). Logo, g(x) tem um inverso multi-
plicativo no corpo F , o que implica (g(x))pd−1 ≡ 1 mod h(x).
42
Como pk − 1 é a ordem de g(x), temos que (pk − 1)|(pd − 1) ⇒ k|d, conforme o
Lema 3.4.2.
Além disso, h(x)|(xr − 1) em Zp[x] e, consequentemente, em F . Logo,
xr ≡ 1 mod h(x). Já que r é primo, então r = ordh(x)x. Como a ordem de F∗ é pk−1
temos que xp
k−1 ≡ 1 mod h(x), que implica r|(pk − 1), ou seja,
pk ≡ 1 (mod r). Logo, d|k. Portanto, d = k.
�
3.4.3 O algoritmo AKS
Primeiramente, apresentaremos o algoritmo AKS [3] e posteriormente discutiremos
se o algoritmo funciona e sua complexidade.
Algoritmo 3 (AKS(n)).
n é um inteiro positivo
1. se n é da forma ab, b > 1, então retorne “composto”;
2. r = 1;
3. enquanto r < n faça
4. se mdc(n, r) 6= 1, então retorne “composto”;
5. se r é primo, então
6. seja q o maior fator primo de r − 1
43
7. se q ≥ d4
√
r log2 ne e n
r−1
q 6≡ 1 (mod r), pare;
8. r ← r + 1;
9. para a = 1 até d2
√
r log2 ne
10. se (x− a)n 6≡ (xn − a) mod (xr − 1, n), retorne “composto”;
11. Retorne “primo”.
No artigo [9] é proposto um algoritmo rápido que detecta, em tempo polinomial,
se um inteiro n > 1 é uma potência perfeita ou não. Assim, o passo (1) do AKS pode
ser executado em tempo polinomial.
O algoritmo possui dois loops. No primeiro loop, o algoritmo tenta encontrar um
primo r tal que r − 1 tem o maior fator primo q ≥ d4
√
r log2 ne e que q divida a
ordem multiplicativa de n módulo r.
Para analisar se o algoritmo está correto e sua complexidade, consideraremos o
lema a seguir.
Lema 3.4.11. Para cada n suficientemente grande, existem constantes c1 e c2 po-
sitivas para os quais existe um primo r, onde c1(log2 n)
6 ≤ r ≤ c2(log2 n)6 tal que
q = P (r − 1) ≥ 4
√
r log2 n e q|ordrn.
Prova. Sejam c como no Lema 3.4.3 e P (r−1) o maior fator primo de r−1. Seja R o
número de primos r’s no intervalo [c1(log2 n)
6, c2(log2 n)
6] tal que
P (r − 1) > (c2(log2 n)6)2/3 ≥ r2/3, para n suficientemente grande.
44
Assim,
R = π′(c2(log2 n)
6)− π′(c1(log2 n)6)
≥ π′(c2(log2 n)6)− π(c1(log2 n)6),
pois π(x) ≤ c′ x
log2 x
≤ π′(x) para algum c′, de acordo com os Lemas 3.4.1 e 3.4.3.
Então,
R ≥ c c2(log2 n)
6
log2(c2(log2 n)
6)
− π(c1(log2 n)6)
≥ c c2(log2 n)
6
log2(c2(log2 n)
6)
− 8 c1(log2 n)
6
log2(c1(log2 n)
6)
≥ c c2(log2 n)
6
log2 c2 + 6 log2(log2 n)
− 8 c1(log2 n)
6
log2 c1 + 6 log2(log2 n)
.
Como c2 ≤ log2 n para n suficientemente grande, então
R ≥ c c2(log2 n)
6
log2(log2 n) + 6 log2(log2 n)
− 8 c1(log2 n)
6
log2 c1 + 6 log2(log2 n)
≥ c c2(log2 n)
6
7 log2(log2 n)
− 8 c1(log2 n)
6
6 log2(log2 n)
=
(log2 n)
6
log2(log2 n)
(
cc2
7
− 8c1
6
)
.
Seja c3 :=
(
cc2
7
− 8c1
6
)
. Escolhemos c1 ≥ 46 e c2 tal que c3 > 0. Seja x := c2(log2 n)6
e definimos N := (n− 1)(n2 − 1) · · · (nbx1/3c − 1) =
∏bx1/3c
i=1 (n
i − 1).
Como qualquer inteiro positivo m tem no máximo log m fatores primos, então o
i-ésimo termo no produto acima tem no máximo i log m ≤ i log2 n ≤ bx1/3c log2 n ≤
≤ x1/3 log2 n fatores primos. Logo, N tem x2/3 log2 n fatores primos, no máximo.
Observamos que
x2/3 log2 n = c
2/3
2 (log2 n)
5 <
c3(log2 n)
6
log2(log2 n)
.
Então, existe um primo r tal que c1(log2 n)
6 ≤ r ≤ c2(log2 n)6 e P (r − 1) ≥ r2/3,
mas que r - N . Este é o primo r que procuramos.
45
De fato, sendo r2/3 = r1/6
√
r e que r1/6 ≥ c1/61 log2 n ≥ 4 log2 n, então
r2/3 ≥ 4
√
r log2 n.
Antes de provarmos que q|ordr(n), mostraremos que q|ordr(n) é equivalente a
n
r−1
q 6≡ 1 mod r.
Suponhamos que q|ordr(n). Como q ≥ 4
√
r log2 n, então q ≥ r2/3 >
√
r >
> (r − 1)1/2 ⇒ q2 > r − 1 ⇒ q > r−1
q
. Sendo ordr(n) > q, então ordr(n) >
r−1
q
⇒
⇒ n
r−1
q 6≡ 1 mod r (pela definição de ordr(n)).
Suponhamos que q - ordr(n). Como ordr(n)|(r − 1) (pois mdc(n, r) e
nr−1 ≡ 1 mod r), temos que r − 1 = ordr(n) · d⇒ ordr(n)| r−1q ⇒ n
r−1
q ≡ 1 mod r.
Agora podemos mostrar que q|ordr(n). De fato, suponhamos, por absurdo, que
n
r−1
q ≡ 1 (mod r). Então, r|(n
r−1
q − 1). Como q ≥ r2/3, r ≤ c2(log2 n)6 e
x = c2(log2 n)
6, temos
r − 1
q
<
r
q
≤ r
r2/3
= r1/3 ≤ (c2(log2 n)6)1/3 = x1/3.
Assim (n
r−1
q −1) é um termo de N . Mas isto implica que r|N , o que é contradição.
�
Observamos que como q é um inteiro (pois é primo), teremos que q ≥ d4
√
r log2 ne.
Teorema 3.4.2. Se n é primo, então o algoritmo retorna “primo”.
Prova. O primeiro loop não retornará “composto” pois mdc(n, r) 6= 1 para todo
r ≤ c2(log2 n)6 onde c2 é como no Lema 3.4.11. Então, no segundo loop também não
retorna ”composto”, pois a congruência (3.4.2) sempre será satisfeita. Portanto, o
algoritmo sempre retorna ”primo”quando n for primo.
�
46
Agora, vamos verificar se o algoritmo funciona quando temos n composto como
entrada. Vamos considerar que n não seja uma potência perfeita e que todo fator
primo de n seja maior do que r, pois caso contrário n seria detectado como composto
no passo (1) ou (4) do algoritmo. Vamos mostrar que n será detectado no segundo
loop.
Seja n = pe11 · · · p
ek
k a decomposição de n. Neste caso, ordrn|mmc{ordr(pi)}ki=1. De
fato, se λ =mmc{ordr(pi)}ki=1, então λ = ordr(pi)mi, mi escolhido para cada ordr(pi).
Logo,
nλ =
k∏
i=1
peiλi
=
k∏
i=1
p
ei·ordr(pi)mi
i
=
k∏
i=1
(p
ordr(pi)
i )
eimi
= 1.
Desta forma, existe um primo p fator de n tal que q|ordrp onde q = P (r− 1) para
o r encontrado no primeiro loop, pois todo fator primo de mmc{ordr(pi)}ki=1 é um
fator primo para pelo menos uma ordr(pi) De agora em diante, p será tal fator primo
de n.
No segundo loop, o algoritmo usa o valor de r encontrado para fazer o cálculo de
l = d2
√
r log2 ne binômios: (x− a) para 1 ≤ a ≤ l.
Pelo Lema 3.4.10, temos um polinômio h(x) que é fator de xr − 1 de grau
d = ordr(p), onde p é o fator primo de n tal que q|ordrp e tal polinômio é irredut́ıvel
em Zp[x].
47
Devemos notar que
(x− a)n ≡ (xn − a) mod (xr − 1, n) ⇒ (x− a)n ≡ (xn − a) mod (h(x), p).
Assim a congruência é satisfeita para cada binômio em F . O conjunto de l
binômios forma um grupo ćıclico neste corpo.
Lema 3.4.12. No corpo F , o grupo gerado pelos l binômios: (x− a), 1 ≤ a ≤ l, ou
seja,
B = {
∏
1≤a≤l
(x− a)αa ; αa ≥ 0,∀1 ≤ a ≤ l}
é ćıclico com |B| > (d
l
)l.
Prova. Demonstração é apresentada em [3]
�
Se d = ordrp e q|ordrp, então d ≥ q ≥ d4
√
r log2 ne ≥ 2d2
√
r log2 ne ≥ 2l. Usando
o resultado do lema anterior, |B| > 2l≥ 22
√
r log2 n = n2
√
r. Seja g(x) um gerador de B.
Então a ordem de g(x) em F é > n2
√
r. Este resultado nos será útil na demonstração
do teorema que garante que o algoritmo retornará “composto”, se n for composto.
O conjunto definido como
Ig(x) = {m; g(x)m ≡ g(xm) mod (xr − 1, p)},
relacionado com o gerador g(x) de B, será importante nos seguintes resultados.
48
Lema 3.4.13. O conjunto Ig(x) é fechado em relação à multiplicação.
Prova. Sejam m1, m2 ∈ Ig(x). Temos
g(x)m1 ≡ g(xm1) mod (xr − 1, p),
e
g(x)m2 ≡ g(xm2) mod (xr − 1, p).
Substituindo xm1 na segunda congruência temos,
g(xm1)m2 ≡ g(xm1m2) mod (xm1r − 1, p)⇒ g(xm1)m2 ≡ g(xm1m2) mod (xr − 1, p).
Disso obtemos,
g(x)m1m2 ≡ (g(x)m1)m2 mod (xr − 1, p)
≡ g(xm1)m2 mod (xr − 1, p)
≡ g(xm1m2) mod (xr − 1, p).
Portanto, m1m2 ∈ Ig(x)
�
Lema 3.4.14. Seja og a ordem de g(x) em F . Se m1,m2 ∈ Ig(x) e m1 ≡ m2 (mod r),
então m1 ≡ m2 (mod og).
Prova. Como m1 ≡ m2 (mod r), então m2 = m1 + kr, para algum k ≥ 0. Sendo
m2 ∈ Ig(x), temos
49
g(x)m2 ≡ g(xm2) mod (xr − 1, p)
g(x)m1+kr ≡ g(xm1+kr) mod (xr − 1, p)
g(x)m1g(x)kr ≡ g(xm1) mod (xr − 1, p) [Lema 3.4.9]
g(x)m1g(x)kr ≡ g(x)m1 mod (xr − 1, p).
Temos que g(x) 6≡ 0 implica g(xm1) 6≡ 0. Então podemos cancelar g(x)m1 em
ambos os lados da última congruência acima, obtendo
g(x)kr ≡ 1 mod (xr − 1, p).
Portanto,
kr ≡ 0 mod og ⇒ m2 ≡ m1 mod og.
�
Este lema nos diz que existem no máximo r elementos em Ig(x) que são menores
que og. Para ver isso, consideramos a contraposição do lema: Sejam m1, m2 ∈ Ig(x).
Se m1 6≡ m2 mod og, então m1 6≡ m2 mod r. Também consideramos os inteiros
positivos menores do que og no conjunto Ig(x). Sendo os elementos distintos módulo
r. Isso implica que existe um número ≤ r de elementos do conjunto Ig(x) que são
menores do que og.
Teorema 3.4.3. Se n é composto, então o algoritmo retorna “composto”.
Prova. Suponhamos, por absurdo, que o algoritmo retorne “primo”. Assim, o se-
gundo loop assegura que para todo 1 ≤ a ≤ l, temos
(x− a)n ≡ (xn − a) mod (xr − 1, n). (3.4.3)
50
Seja g(x) um gerador de B como no Lema 3.4.12. Observemos que g(x) é apenas
um produto de potências de l binômios (x − a), 1 ≤ a ≤ l que satisfaz a equação
(3.4.3). Sendo g(x) =
∏
1≤a≤l(x− a)αa , temos
g(x)n =
∏
1≤a≤l
(x− a)nαa
≡
∏
1≤a≤l
(xn − a)αa mod (xr − 1, p)
≡ g(xn) mod (xr − 1, p).
Assim, n ∈ Ig(x). Pelo Lema 3.4.8, também temos p ∈ Ig(x), pois
g(x)p ≡ g(xp) mod p ⇒ g(x)p ≡ g(xp) mod (xr − 1, p). E 1 ∈ Ig(x), trivial-
mente.
Consideramos o conjunto
E = {nipj; 0 ≤ i, j ≤ b
√
rc}.
Pelo Lema 3.4.13, E ⊆ Ig(x). Como 1 ≤ ninj < n
√
rn
√
r < og para todo
0 ≤ i, j ≤ b
√
rc, todos os elementos de E são distintos módulo og. Pelo Lema 3.4.14,
todos os elementos de E também são distintos módulo r. Dáı, |E| ≤ r. Temos que
|{(i, j); 0 ≤ i, j ≤ b
√
rc}| = (1 + b
√
rc2) > r. Então existem dois elementos ni1pj1 e
ni2pj2 em E com i1 6= i2 ou j1 6= j2, i1 ≥ i2 tais que
ni1pj1 ≡ ni2pj2 (mod r), pelo Prinćıpio da Casa dos Pombos. Mas, pelo Lema 3.4.14,
temos ni1pj1 ≡ ni2pj2 (mod og). Implicando
ni1−i2 ≡ pj2−j1 (mod og).
Como og ≥ n2
√
r e ni1−i2 , pj2−j1 < n
√
r, a congruência acima torna-se uma igual-
dade. Sendo p primo, esta igualdade implica que n = pk para algum k ≥ 1. Assim, n
já teria sido detectado no passo (1), se k ≥ 2. Portanto, p = n, que é uma contradição.
51
�
Vamos agora analisar a complexidade do algoritmo AKS. Para obter uma descrição
completa das complexidades usadas na análise do algoritmo verificar a referencia [33].
Observamos que lg n ≥ log2 n, pois se n tem k bits (n = dk−12k−1 + dk−22k−2+
+ · · · + d0), então 2k−1 ≤ n < 2k ⇒ log2 n < k = lg n. Então as complexidades do
nosso algoritmo podem ser representadas em termos de lg n.
No passo (1) o algoritmo toma um tempo O(lg3 n).
Na busca por r no primeiro loop executa O(lg6 n) iterações, conforme Lema 3.4.11.
Veremos, então, quanto tempo cada iteração neste loop leva. No passo (4) den-
tro do loop, para calcular o mdc leva O(lg3 n). Nos passos (5) e (6), leva tempo
O(
√
r lg2 n) e no passo (7) O(lg2 n + lg3 r). Totalizando O(lg3 n +
√
r lg2 r) cada ite-
ração. Como temos um total de O(lg6 n) iterações, então a complexidade do primeiro
loop é O(lg9 n+
√
r lg6 n lg2 r). Como r = O(lg6 n) então leva tempo O(lg9 n(lg lg n)2).
No segundo loop, para calcular os coeficientes do polinômio
(x − a)n mod (xr − 1, n) o algoritmo gasta O(r2 lg3 n). O polinômio
(xn − a) mod (xr − 1, n) é calculado dentro do mesmo limite de tempo. Assim,
o segundo loop leva um total de tempo O(r2
√
r lg4 n).
Sendo r = O(lg6 n), então o tempo total do algoritmo é O(lg19 n).
52
Caṕıtulo 4
Fatoração de Inteiros
Neste caṕıtulo, apresentaremos alguns métodos de fatoração existentes. Não des-
creveremos tais métodos em seus mińımos detalhes, mas sim forneceremos uma noção
de como funcionam tais métodos para estabelecermos relação com a segurança do
RSA.
Cabe-nos ressaltar que tais métodos devem ser aplicados a inteiros positivos que já
tenham sido testados por um dos algoritmos do caṕıtulo anterior e que tais algoritmos
tenham retornado que o número é composto. Isto porque o problema de decidir
se um número é primo ou composto, em geral, parece ser mais fácil de se resolver
computacionalmente que o problema de fatoração. Assim, antes de tentar fatorar um
inteiro, devemos testar tal número a fim de ter certeza que o número é composto.
Os seguintes algoritmos de fatoração que apresentaremos não fornecem todos os
primos divisores que constituem a fatoração completa de um número n, mas apenas
fatora o número em produto de dois inteiros da forma n = ab com a, b > 1. A partir
disso, podemos usar um teste de primalidade em a e b, e se obtivermos respostas de
que são compostos, aplicamos recursivamente o algoritmo de fatoração. Prosseguindo
53
dessa maneira, conseguiremos a fatoração completa de n.
4.1 Um Método Simples
Tendo testado um inteiro n > 2 e verificado que é um composto, um simples
algoritmo [10, 14] para determinar um fator de n é tentar dividir n por cada um dos
inteiros entre 2 e
√
n.
Caso algum desses números divida n, então tal número é um fator de n. O menor
fator encontrado desta forma é primo.
Como em nosso caso estamos interessados em fatorar números muitos grandes
(com no mı́nimo 200 d́ıgitos decimais), este algoritmo não é nada eficiente. Este
algoritmo executa no máximo
√
n divisões. Como n ≥ 10200 então
√
n ≥ 10100. O
algoritmo realizará no máximo 10100 divisões. Suponhamos que o computador usado
na implementação do algoritmo realize 1010 divisões por segundo, o que atualmente
é um número muito grande considerando o avanço tecnológico atual. Então para
realizar 10100 divisões levaria 10
100
1010
= 1090 segundos, ou seja, aproximadamente 1082
anos. Isto torna nosso algoritmo impraticável tendo em vista que a idade do universo
(desde o Big Bang) é estimada em 2 · 1011 anos.
No entanto, este algoritmo pode ser bastante útil se o número a ser fatorado possui
algum fator primo pequeno menor do que 106. Neste caso, o algoritmo obterá um
fator primo de n rapidamente.
Por este motivo é que se deve gerar primos p e q grandes para serem usados no
RSA, caso contrário, o sistema pode ser facilmente quebrado.
54
4.2 Método de Fermat
O algoritmo de Fermat [14] é eficiente para achar um fator de n que seja não muito
menor do que
√
n.
Suponhamos que n > 0 um composto ı́mpar. A idéia do algoritmo de Fermat é
tentar escrever n = x2 − y2 com x e y inteiros positivos. Se encontrarmos x e y tais
que n = x2 − y2, então encontramos uma fatoração de n em produto de dois inteiros
pois n = x2 − y2 = (x− y)(x + y). Assim, x− y e x + y são fatores de n.
Quando n é um quadrado perfeito, ou seja, quando existe r ∈ Z tal que n = r2,
temos x = r e y = 0. Mas quando y > 0, então x =
√
n + y2>
√
n. Isto nos sugere
o algoritmo a seguir.
Algoritmo 4 (FERMAT(n)).
Dado n ı́mpar
1. r = b
√
nc
2. se n = r2, então faça x = r e y = 0
3. senão enquanto r < n+1
2
ou s não for inteiro faça
r = r + 1
s =
√
r2 − n
4. Faça a = (r + s) e b = (r − s)
5. Retorne a e b
Veremos agora porque o algoritmo funciona.
55
Teorema 4.2.1. O algoritmo de Fermat funciona.
Prova. Para verificar que o algoritmo funciona temos que mostrar que existe
x ≥ b
√
nc tal que
√
x2 − n seja um inteiro, o algoritmo realiza um número finito
de passos.
Suponhamos que n = ab com a ≤ b. O algoritmo procura por inteiros x e y tais
que n = x2 − y2 = (x− y)(x + y). Como x− y ≤ x + y, então tomamos a = x− y e
b = x + y. Resolvendo o sistema linear em duas incógnitas temos x = a+b
2
e y = b−a
2
.
Como n é ı́mpar então a e b têm que ser ı́mpares. Logo, a + b e b − a são números
pares, o que implica que x = a+b
2
e y = b−a
2
são inteiros tais que
x2 − y2 =
(
a + b
2
)2
−
(
b− a
2
)2
= ab = n. (4.2.1)
Se a = b então o algoritmo pára no passo (2). Suponhamos 1 < a < b < n.
Como 1 < b e 1 < a temos que a − 1 > 0, então (a − 1) · 1 < (a − 1) · b ⇒
a− 1 < ab− b⇒ a− 1 + (b + 1) < ab− b + (b + 1)⇒ a + b < n + 1⇒ a+b
2
< n+1
2
.
Por outro lado, conforme a equação (4.2.1) temos que
(a + b)2
4
− (b− a)
2
4
= n ⇒ (a + b)
2
4
− n = (b− a)
2
4
≥ 0.
Logo, (a+b)
2
4
− n ≥ 0 ⇒
(
a+b
2
)
≥
√
n ≥ b
√
nc. Portanto, b
√
nc ≤ x < n+1
2
.
Analisando o algoritmo, temos que a variável r é inicializada com o valor b
√
nc
e vai sendo incrementada de uma unidade em cada loop. Como n é composto, o
algoritmo encontra um valor r = a+b
2
antes de chegar a n+1
2
.
�
Se o número n a ser fatorado tem um fator próximo a
√
n, através do algoritmo de
Fermat este fator será rapidamente encontrado. Por essa razão, deve-se usar primos
p e q não muito próximos um do outro na geração de chaves para o RSA.
56
4.3 ρ-Método de Pollard
O algoritmo em que realizamos tentativas de dividir um número n por inteiros
menores do que
√
n, apresentado na seção 4.1, é eficiente no que se refere a encontrar
um fator de n que não seja superior a 105. O algoritmo desta seção trabalha mais
eficientemente no que se refere a encontrar um fator de um inteiro maior do que 105,
no entanto limita-se a encontrar fatores de um número que não seja superior 1010.
A idéia por trás do algoritmo ρ de Pollard [10, 20] é a seguinte. Escolhemos f(x)
um polinômio irredut́ıvel em x (ver definição de polinômio irredut́ıvel na seção 3.4.2
do caṕıtulo anterior) com coeficientes inteiros e um valor inicial x0. Seja d um fator
não trivial de n (não conhecido ainda). Recursivamente, geramos a seqüência definida
por
xi ≡ f(xi−1) mod n.
Seja yi ≡ xi (mod d). Assim, yi ≡ f(yi−1) mod d. Como existe um número finito
de classes congruência módulo d teremos yi = yj para algum par (i, j). Uma vez que
isto acontece teremos yi+t = yj+t, para todo t > 0.
Se yi = yj, então xi ≡ xj (mod d). Logo, d|(xi − xj) e, consequentemente,
mdc(xi − xj, n) > 1 é um divisor de n.
O problema é que d não é conhecido e ,como consequência, não sabemos os valores
de yi e nem mesmo quando yi = yj. Neste caso, usamos a equação yi+t = yj+t como
aux́ılio. Existem infinitos pares (i, j) para os quais yi = yj. Seja l o comprimento
do ciclo. Se estamos fora do ciclo, qualquer par (i, j) para o qual l|(j − i) temos que
j ≡ i (mod l) e, assim, yi ≡ xj. Dessa forma, encontramos uma forma sistemática
de escolher pares (i, j) e para cada par calculamos mdc(xi − xj, n).
Uma maneira de encontrar muitos pares (i, j) é tomar 2α < i ≤ 2α+1 para algum
57
α natural e testar se mdc(xi − x2α , n) 6= 1. Caso o mdc não seja 1 então tomamos t
o menor inteiro tal que j + t = 2α e 2α < i + t ≤ 2α+1.
Com relação ao polinômio usado, devemos escolher f tal que que a sequência (xi)
seja parecida com uma sequência aleatória. Em geral, tomamos polinômios da forma
f(x) = x2 + c com c 6= 0 ou c 6= −2. Na prática, a escolha de polinômios dessa forma,
minimiza o número de operações executada pelo algoritmo. A complexidade deste
algoritmo é estimada em O(n1/4).
Este algoritmo torna-se eficiente para determinar o expoente de decodificação do
RSA a partir da chave pública quando aquele tem menos do que 160 bits [24, §8.2.2
Security of RSA, note (iv)].
4.4 ρ− 1-Método de Pollard
Este outro método de Pollard [10, 30] em alguns aspectos é similar ao método
anterior. O método ρ − 1 de fatoração é eficiente quando o número a ser fatorado
possui um fator primo p cujo número p− 1 possui um fator pequeno (< 104).
A idéia empregada nesse método tem como base o Teorema 2.0.1.
Seja p um fator primo (ainda não conhecido) de n ≥ 2. Obviamente p − 1 é
composto. Restringiremos nossa atenção aos números n tais que (p − 1)|L! (L um
inteiro positivo qualquer < 105). Observamos que o número L! contém todos os
primos positivos menores do que L.
Como p é primo, então cp−1 ≡ 1 (mod p) quando mdc(c, n) = 1. Calculamos
m = cL! (mod n). Para isso aplicamos um algoritmo de exponenciação modular [7].
Sendo L! = (p − 1)j, então m ≡ 1 (mod p). Logo, p|(m − 1). As chances de n não
dividir m − 1 são excelentes. Neste caso, o mdc(m − 1, n) será um fator não trivial
58
de n. Caso o mdc(m− 1, n) = n, escolhemos um outro valor para a base c.
Uma das razões para a restrição para que p−1 e q−1 não tenham fatores pequenos
na escolha dos primos p e q como chave do RSA, é que com o algoritmo ρ − 1 de
Pollard, o sistema fica vunerável.
4.5 Crivo Quadrático
Um dos mais poderosos métodos de fatoração conhecidos é o Crivo Quadrático
[10, 30]. Apesar de ser um dos melhores algoritmos existentes para fatoração (isto não
significa que possa realmente fatorar um número composto grande), existem apenas
estimativas com relação ao seu desempenho.
Este método tem como técnica uma abordagem similar à que foi feita no método
de Fermat. No lugar de procurar x e y que satisfazem n = x2 − y2, procuramos
encontrar aleatoriamente x e y que satisfazem x2 ≡ y2 (mod n). Encontrar tal par
(x, y) não significa que encontramos uma fatoração de n, mas significa que n divide
x2 − y2 = (x − y)(x + y). As chances são de pelo menos 50-50 para que os primos
divisores de n estejam distribúıdos entre os divisores de ambos os fatores (x − y) e
(x + y). Assim, d = mdc(x− y, n) será um fator não trivial de n.
A complexidade para o crivo quadrático fatorar um número n, não rigorosamente
provada, é dada por e(1+o(1))
√
log n log log n [27]. Portanto, para n muito grande o trabalho
executado por uma implementação do método cresce exponencialmente, o que torna
a fatoração de n muito grande impraticável.
59
Conclusão
No presente trabalho buscamos apresentar o RSA e alguns resultados da Teoria
dos Números relacionados ao RSA. Com este objetivo consideramos o problema de
gerar primos aleatoriamente e de fatorar inteiros grandes.
Com relação à geração de números primos, apresentamos alguns algoritmos para
testar a primalidade de números de forma genérica. Dois dos algoritmos apresenta-
dos são probabiĺısticos, o Solovay-Strassen e o Miller-Rabin, ambos com complexidade
O(lg3n). Também apresentamos um algoritmo determińıstico, o AKS, que foi recen-
temente descoberto e que tem complexidade O(lg19n).
Comparando os testes de primalidade probabiĺısticos, o uso do algoritmo de Miller-
Rabin apresenta pelo menos duas vantagens em relação ao de Solovay-Strassen: O
algoritmo de Miller-Rabin é de implementação mais simples, uma vez que o outro
algoritmo exige o cálculo do śımbolo de Jacobi. Além disso, a probabilidade de erro
é limitada por 1
4
enquanto que para o algoritmo de Solovay- Strassen a probabilidade
de erro é limitada por 1
2
.
A descoberta do AKS é de grande relevância matemática, pois como consequência
prova que o