ver/abrir - Repositório do Departamento de Ciência da Computação

Transcrição

Universidade de Brası́lia
Instituto de Ciências Exatas
Departamento de Ciência da Computação
Verificação Formal da Correção do Algoritmo
AKS
Ricardo Peixoto
Monografia apresentada como requisito parcial
para conclusão do Curso de Computação – Licenciatura
Orientador
Prof. Dr. Flávio Leonardo Cavalcanti de Moura
Brası́lia
2008
Universidade de Brası́lia – UnB
Curso de Computação – Licenciatura
Coordenadora: Prof a.̄ Dr a.̄ Priscila América Solı́s Mendez Barreto
Banca examinadora composta por:
Prof. Dr. Flávio Leonardo Cavalcanti de Moura (Orientador) – CIC/UnB
Prof. Dr. Guilherme Albuquerque Pinto – CIC/UnB
Prof. Dr. Mauricio Ayala Rincón – MAT/UnB
CIP – Catalogação Internacional na Publicação
Peixoto, Ricardo.
Verificação Formal da Correção do Algoritmo AKS / Ricardo Peixoto.
Brası́lia : UnB, 2008.
94 p. : il. ; 29,5 cm.
Monografia (Graduação) – Universidade de Brası́lia, Brası́lia, 2008.
CDU 004
Endereço: Universidade de Brası́lia
Campus Universitário Darcy Ribeiro – Asa Norte
CEP 70910–900
Brası́lia – DF – Brasil
Universidade de Brası́lia
Verificação Formal da Correção do Algoritmo
AKS
Ricardo Peixoto
Monografia apresentada como requisito parcial
para conclusão do Curso de Computação – Licenciatura
Prof. Dr. Flávio Leonardo Cavalcanti de Moura (Orientador)
CIC/UnB
Prof. Dr. Guilherme Albuquerque Pinto Prof. Dr. Mauricio Ayala Rincón
CIC/UnB
MAT/UnB
Prof a.̄ Dr a.̄ Priscila América Solı́s Mendez Barreto
Coordenadora do Curso de Computação – Licenciatura
Brası́lia, 15 de fevereiro de 2008
Dedicatória
Dedico este trabalho a meu filho, Gustavo Henrique, a minha esposa, Litiane,
a meus pais, Cleomar e Peixoto, e a meu amigo, Dioney, que nunca me deixaram
parar.
Agradecimentos
Agradeço a meu orientador, Prof. Flávio, que acreditou e tornou possı́vel este
trabalho.
Resumo
Este trabalho apresenta uma formalização, utilizando o assistente de prova
Coq, do algoritmo AKS, o qual foi apresentado por Agrawal, Kayal e Saxena em
seu artigo PRIMES is in P, divulgado em 2002 e publicado em 2004. O AKS
é o primeiro algoritmo capaz de determinar, sem erro e em tempo polinomial,
a primalidade de um número. O assistente de prova Coq é baseado em uma
lógica de ordem superior muito expressiva, conhecida como cálculo de construções
indutivas.
Palavras-chave: Algoritmo AKS, Coq, teste de primalidade, tempo polinomial,
assistente de prova, cálculo de construções indutivas.
Abstract
This work presents a formalization of the AKS algorithm in the Coq proof
assistant. The AKS algorithm was presented in the Agrawal, Kayal and Saxena’s
PRIMES is in P paper, in 2002. This is the first algorithm that can decide in
polynomial time, without error, whether a given number is prime or not. The
Coq proof assistant is based on a higher-order logic called calculus of inductive
constructions.
Keywords: AKS, Coq, prime numbers, primality test, polynomial time, proof
assistants, calculus of inductive constructions.
Sumário
Lista de Figuras
9
Capı́tulo 1 Introdução
10
Capı́tulo 2 Testes de Primalidade e o Algoritmo AKS
2.1 Noções de Complexidade . . . . . . . . . . . . . . . .
2.1.1 O Custo de um Algoritmo . . . . . . . . . . .
2.1.2 Notação Assintótica . . . . . . . . . . . . . .
2.1.3 Classes de Complexidade . . . . . . . . . . . .
2.2 Testes de Primalidade . . . . . . . . . . . . . . . . .
2.2.1 O Crivo de Eratóstenes . . . . . . . . . . . . .
2.2.2 Distribuição dos Números Primos . . . . . . .
2.2.3 Eficiência dos Testes de Primalidade . . . . .
2.3 O Algoritmo AKS . . . . . . . . . . . . . . . . . . . .
2.3.1 O Teorema Fundamental . . . . . . . . . . . .
2.3.2 O Pseudocódigo e a Correção . . . . . . . . .
2.3.3 A Complexidade Polinomial . . . . . . . . . .
Capı́tulo 3 Assistentes de Prova
3.1 Verificação Formal e Assistentes de Prova .
3.2 O Assistente de Prova Coq . . . . . . . . .
3.2.1 Tipos . . . . . . . . . . . . . . . .
3.2.2 Táticas . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
12
12
12
13
15
18
21
23
27
29
29
43
45
.
.
.
.
51
51
54
55
56
Capı́tulo 4 Metodologia
68
Capı́tulo 5 Resultados
71
Capı́tulo 6 Alguns trabalhos
83
Apêndice A Princı́pio da Indução Matemática
85
Apêndice B Teorema de Lagrange
88
Referências
91
Lista de Figuras
2.1
2.2
Comparação do crescimento de duas funções. . . . . . . . . . . . .
Conjectura atual para a relação entre as classes de complexidade.
14
17
4.1
Dependências que serão seguidas na formalização do AKS. . . . .
69
5.1
5.2
Dependências finais na formalização do algoritmo AKS. . . . . . .
Especificação final do AKS e a prova de sua correção em Coq. . .
73
74
Capı́tulo 1
Introdução
Além de despertarem uma antiga curiosidade matemática, atualmente os números primos são usados na criptografia de dados. Em geral, chaves criptográficas
são geradas a partir da multiplicação de grandes números primos. Quanto maior
o número chave, mais demorada será a sua decomposição em primos, ou seja,
a sua “quebra”. No entanto, computacionalmente, é mais difı́cil decompor um
número em seus fatores primos do que testar se grandes números candidatos a
geradores de chaves são primos ou não ([Cormen et al., 2001]. Daı́ a importância da eficiência dos testes de primalidade (algoritmos que testam se um número
é primo ou composto), desde uma antiga fascinação até uma necessidade prática atual ([Coutinho, 2004]). Até 2002, não era conhecido nenhum algoritmo
capaz de determinar, sem erros, a primalidade de um número em tempo polinomial. Na Teoria da Complexidade, o problema era comumente considerado
classe co-NP, apesar de ser conhecida uma prova de que também é classe NP
([Agrawal et al., 2004]).
Em 2002, Agrawal, Kayal e Saxena disponibilizaram na Internet o esboço de
um artigo, chamado PRIMES is in P, o qual foi aprimorado com contribuições,
entre elas a de Lenstra Jr. ([Bernstein, 2003]), e definitivamente publicado em
2004, em que apresentavam um algoritmo capaz de determinar, inequivocamente,
a primalidade de um número em tempo polinomialmente proporcional ao seu tamanho, que passou a ser conhecido como algoritmo AKS ([Agrawal et al., 2004]).
Apesar da grande importância teórica do algoritmo AKS, já que o problema
da primalidade passou a ser também classe P, na prática, ainda é mais eficiente
o uso de algoritmos probabilı́sticos de tempo polinomial para se testar a primalidade de números grandes ([Coutinho, 2004]). Isso se deve ao fato de que esses
algoritmos probabilı́sticos, mesmo necessitando de um custo adicional para reduzir sua probabilidade de erro, possuem uma curva de tempo (polinomial) bem
menos acentuada que a do algoritmo AKS1 .
Ainda assim, o algoritmo AKS pode ter aberto portas para novos testes
eficientes de primalidade, que serão possı́veis a partir de sua boa compreensão. Nestes últimos anos, foram desenvolvidos vários trabalhos a respeito do
AKS, como, por exemplo, [Bernstein, 2003], [Crandall and Papadopoulos, 2003],
1
Veremos mais à frente que o custo do AKS realmente pode ser representado por um polinômio em função da entrada, mas de grau elevado.
10
[Schoof, 2003], [Bernstein, 2004], [Tou and Alexander, 2005], entre outros, mas
não encontramos nenhum trabalho de verificação formal utilizando, por exemplo,
assistentes de prova. Isso pode se explicar, em parte, pela dificuldade e nı́vel de
detalhe que a formalização do algoritmo exige. Além disso, em seu estágio atual,
o algoritmo AKS ainda não é a melhor opção implementacional. Mesmo assim,
um trabalho de formalização do algoritmo AKS, como o proposto aqui, é relevante
para uma possı́vel utilização, mesmo que de partes do algoritmo, em softwares
certificados, especialmente os relacionados à criptografia de dados, considerando o
fato de que alguns assistentes de prova nos permitem extrair código executável do
conteúdo computacional das provas que satisfaz a especificação dada, e também
permitiria uma melhor compreensão do algoritmo, fornecendo uma prova formal
de propriedades fundamentais envolvidas em sua correção e sua complexidade.
Uma formalização completa do algoritmo AKS é um trabalho complexo, além
do escopo de uma monografia de conclusão de curso de graduação. Desta forma,
nosso objetivo é verificar formalmente apenas a correção do algoritmo, utilizando o
assistente de prova Coq ([The Coq Development Team, 2008b]), que está baseado
em uma lógica de ordem superior muito expressiva, conhecida como cálculo de
construções indutivas ([Bertot and Castéran, 2004]).
Esperamos contribuir, assim, para pesquisas futuras envolvendo testes de primalidade ou mesmo outros problemas relacionados. É importante ressaltarmos
que a formalização que aqui apresentaremos se limitará à correção do algoritmo
AKS. Mais especificamente, provaremos que, para qualquer entrada n > 1, o algoritmo pára com a resposta correta. A prova formal de que o algoritmo tem
complexidade polinomial é deixada como trabalho futuro.
Adicionalmente, esperamos que o presente trabalho seja útil como um texto
introdutório ao assistente de prova Coq para estudantes de Computação, Matemática e áreas afins, já que pouco se tem documentado sobre o assunto em
lı́ngua portuguesa. Desta forma, tentaremos explicar algumas táticas, estruturas
e caracterı́sticas do Coq. Também esperamos apresentar, de forma detalhada e
ao nı́vel de graduação, o algoritmo AKS e os teoremas relacionados. Estudantes que tenham cursado disciplinas de lógica, álgebra e algoritmos/programação
terão facilidade para entender o texto. A complexidade do algoritmo também
será demonstrada, apesar de não estarmos interessados, neste momento, em sua
prova formal. Assim, estudantes com conhecimentos em Teoria da Computação
terão facilidade para compreender o algoritmo AKS, bem como sua importância
e principal caracterı́stica: a complexidade polinomial.
11
Capı́tulo 2
Testes de Primalidade e o
Algoritmo AKS
2.1
Noções de Complexidade
Nesta seção, faremos uma breve revisão sobre complexidade temporal de algoritmos e notação assintótica. Ressaltamos que estaremos apenas tratando da
complexidade temporal de algoritmos. A complexidade espacial será deixada de
lado. Além disso, adotaremos o chamado modelo genérico RAM (random access
machine ou máquina de acesso aleatório) de computação, que pressupõe uma máquina semelhante aos computadores binários, com um único processador e capaz
de executar apenas uma instrução por vez. Assim, os algoritmos considerados
aqui podem ser vistos como programas de computadores ([Cormen et al., 2001]).
Aqueles que já conhecem o assunto podem ir diretamente para a Seção 2.2.
No entanto, àqueles estudantes que ainda não tiveram contato com a Teoria
da Complexidade, sugerimos a leitura de [Knuth, 1968], [Bach and Shallit, 1996],
[Cormen et al., 2001] e [Hopcroft et al., 2001].
2.1.1
O Custo de um Algoritmo
Do ponto de vista exclusivamente temporal, o algoritmo mais eficiente para
a resolução de um problema é aquele que leva menos tempo para dar uma resposta a entradas de um mesmo tamanho n. O tamanho da entrada depende,
especificamente, do tipo de problema e é importante que seja fixado para comparações de eficiência ([Cormen et al., 2001]). Por exemplo, em algoritmos de
ordenação de números inteiros, a entrada é constituı́da de uma seqüência de números. É de se supor que seqüências maiores gastem mais recursos computacionais
para serem ordenadas, independentemente dos algoritmos utilizados. É necessário, portanto, fixar o tamanho da entrada para compararmos o tempo gasto por
algoritmos distintos. E mais: esse tempo precisa ser o menos dependente da máquina o quanto possı́vel. Desta forma, não é conveniente medi-lo em unidades de
tempo habituais, como segundos, pois computadores distintos podem ter drásti-
12
cas diferenças de desempenho1 . Uma medida adequada para a comparação da
eficiência temporal de algoritmos é a quantidade de operações mı́nimas ou passos
([Bach and Shallit, 1996]) necessários para se gerar a saı́da, o chamado tempo de
execução ou custo de um algoritmo.
Em geral, temos custos diferentes para entradas distintas, ainda que tenham
um mesmo tamanho n. Mas muitas vezes podemos identificar aquelas que necessitam executar um maior número de passos para que seja apresentada a resposta.
O pior caso para um tamanho n refere-se às entradas de tamanho n que necessitam da maior seqüência de passos para se obter a resposta, o chamado tempo
de execução do pior caso ou custo máximo de um algoritmo para entradas de
tamanho n. De forma análoga, o tempo de execução do melhor caso ou o custo
mı́nimo de um algoritmo se refere às entradas de tamanho n que necessitam da
menor seqüência de passos para se obter a resposta. Voltando ao exemplo da
ordenação, é de se supor que um algoritmo necessite de mais passos computacionais para gerar a saı́da quando recebe uma entrada totalmente desordenada
do que quando recebe uma que esteja parcialmente ordenada, desde que ambas
tenham o mesmo tamanho n. Este é o caso dos algoritmos mais simples, como a
ordenação por inserção ([Cormen et al., 2001]). O pior caso para esse algoritmo
é quando a entrada está em ordem inversa e o melhor caso é quando a entrada já
está ordenada.
Assim, o tempo de execução do pior caso se revela como parâmetro para
ser usado em comparações entre os custos de algoritmos que resolvem o mesmo
problema2 . Se TA (n) e TB (n) são funções que representam, respectivamente, o
custo máximo dos algoritmos A e B, em que n é o tamanho da entrada, podemos
comparar essas funções, quando n cresce indefinidamente, para sabermos qual
algoritmo é, assintoticamente, mais eficiente (menos custoso).
2.1.2
Notação Assintótica
A notação O (“o” grande ou “o” maiúsculo), introduzida por Bachmann em
1892 ([Knuth, 1968]), tornou-se muito útil para indicar o tempo de execução do
pior caso de algoritmos. Formalmente, temos a seguinte
Definição 2.1.1. ([Cormen et al., 2001]) Seja g(n) uma função com domı́nio N.
Então,
f (n) : existem constantes positivas c e n0 tais que
O(g(n)) =
0 ≤ f (n) ≤ cg(n) para todo n ≥ n0 .
Ou seja, uma função f (n) pertence ao conjunto O(g(n)) se existir uma constante positiva c tal que o produto cg(n) limite superiormente f (n) a partir de
algum n. Assim, a função f (n) = 3n3 ∈ O(n4 ), pois temos que n4 ≥ 3n3 para
todo n ≥ 3. Neste caso especı́fico, temos c = 1 e n0 = 3. De fato, qualquer polinômio não negativo tem o crescimento limitado superiormente por um polinômio
1
Afinal, estamos preocupados com a eficiência de algoritmos e não com a eficiência de máquinas.
2
Mas muitas vezes, quando o pior caso raramente ocorre, a melhor medida para o custo de
um algoritmo é o caso médio ([Cormen et al., 2001]).
13
de grau maior ou igual ao seu. Por exemplo, 2n2 ∈ O(n3 ) e 2n2 ∈ O(n2 ), pois
podemos escolher constantes c e d tais que cn3 ≥ 2n2 , para todo n a partir de
algum n0 , e dn2 ≥ 2n2 , para todo n a partir de algum n1 . A Figura 2.1 mostra
uma comparação entre duas funções, f (n) e g(n). Note que a partir do ponto n0 ,
g(n) é sempre maior que f (n). Neste caso, f (n) ∈ O(g(n)).
Figura 2.1: Comparação do crescimento de duas funções.
Para um algoritmo que tenha como tempo de execução do seu pior caso a
função T (n) = αn2 + βn + γ, com α, β e γ constantes e n significando o tamanho
da entrada, podemos indicar seu tempo de execução simplesmente como O(n2 ),
pois T (n) ∈ O(n2 ) ([Bach and Shallit, 1996]). Ou seja, retiramos as constantes e
os termos de mais baixa ordem, restando apenas o termo mais elevado, o qual é
suficiente para indicar o crescimento da função. De fato,
αn2 + βn + γ
= α.
n→∞
n2
lim
Como α é constante, αn2 + βn + γ e n2 têm a mesma ordem de crescimento. Por
isso, essa medida de eficiência é conhecida como eficiência assintótica, isto é, a
eficiência no limite do tamanho da entrada, quando este cresce indefinidamente
([Cormen et al., 2001]).
Apesar de ser uma relação de pertinência, iremos escrever, a partir de agora,
f (n) = O(g(n)) para indicar que f (n) ∈ O(g(n)). Esta é a notação mais utilizada na literatura especializada e significa que f (n) é, no máximo, proporcional a g(n) ([Bach and Shallit, 1996]), o que satisfaz a definição (2.1.1) e tornase útil nas relações algébricas envolvendo aproximações ([Cormen et al., 2001] e
[Knuth, 1968]). Por exemplo, imagine a seguinte soma, a qual está provada por
14
indução no Apêndice A:
n3 n2 n
1 + 2 + 3 + ... + n =
+
+ .
3
2
6
2
2
2
2
(2.1)
Para n suficientemente grande, podemos escrever:
12 + 22 + 32 + ... + n2 =
n3 n2
+
+ O(n)
3
2
12 + 22 + 32 + ... + n2 =
n3
+ O(n2 )
3
12 + 22 + 32 + ... + n2 = O(n3 ).
(2.2)
(2.3)
Em (2.2), temos uma aproximação assintótica para a soma (2.1) quando n
torna-se grande o suficiente. Estamos dizendo que o lado direito de (2.1) é equi3
2
valente a n3 + n2 , com erro limitado a (ou de ordem máxima) n. O mesmo vale
para as demais equações, que são aproximações menos acuradas que a apresentada
em (2.2). Por fim, em (2.3), indicamos que a soma tem ordem de crescimento
limitada a n3 . Assim, a notação O é usada para indicar funções anônimas, cujos
valores exatos são desconhecidos, mas que possuem limites superiores conhecidos.
Outro ponto importante é que a convenção de usar o sinal “=” na notação
só vale para um lado. Ou seja, podemos escrever que 3n2 = O(n2 ), mas nunca
que O(n2 ) = 3n2 . Devemos lembrar que O(f (n)) representa todo um conjunto de
funções que tem ordem de crescimento limitado a f (n) e que “=” representa uma
relação de pertinência. Portanto, O(n2 ) ∈ 3n2 não faria sentido.
De forma análoga à notação O, podemos definir a notação Ω da seguinte forma:
Definição 2.1.2. ([Cormen et al., 2001]) Seja g(n) uma função com domı́nio N.
Então,
f (n) : existem constantes positivas d e n0 tais que
Ω(g(n)) =
0 ≤ dg(n) ≤ f (n) para todo n ≥ n0 .
Ou seja, uma função f (n) pertence ao conjunto Ω(g(n)) se existir uma constante positiva d tal que o produto dg(n) limite inferiormente f (n) a partir de
algum n. Assim, a função f (n) = 3n3 − 3 ∈ Ω(n2 ), pois temos que n2 ≤ 3n3 − 3
para todo n ≥ 2. Neste caso especı́fico, temos d = 1 e n0 = 2. De fato, qualquer
polinômio não negativo tem crescimento limitado inferiormente por um polinômio de grau menor ou igual ao dele. Como fizemos com a notação O, quando
f (n) ∈ Ω(g(n)), iremos escrever f (n) = Ω(g(n)). Seguindo a analogia, a notação
Ω é comumente usada para indicar o custo mı́nimo de um algoritmo.
2.1.3
Classes de Complexidade
Estamos preocupados, neste trabalho, com os problemas de decisão ou decidı́veis, que são os problemas para os quais temos respostas de simples verificação,
15
geralmente sim ou não ([Cormen et al., 2001]). Ou seja, quando se tem que decidir se uma dada entrada satisfaz ou não um problema. A primalidade é um
problema de decisão, pois queremos determinar se um número é ou não é primo.
Algoritmos não-determinı́sticos são aqueles que respondem um problema de
decisão mas que, em alguns pontos, podem escolher qual passo seguir, dentre um
número finito de possibilidades, podendo, inclusive, fornecer uma saı́da não válida
para o problema ([Bach and Shallit, 1996]). A escolha do caminho pode ser feita,
por exemplo, heuristicamente (procurando-se o melhor caminho para a resposta).
Como exemplo, imagine que temos uma lista de conferência de estoque de um
depósito qualquer. A lista pode ser percorrida de várias formas. Normalmente,
começaremos seguindo a ordem da lista mas, invariavelmente, acharemos objetos
próximos uns dos outros no estoque que acabarão por serem conferidos antes do
previsto. Neste caso, independentemente do tempo variável de execução da tarefa,
saberemos, ao final, se todo o estoque confere ou não. Um outro exemplo envolve
a primalidade ([Bach and Shallit, 1996]). Imagine um algoritmo que recebe, como
entrada, dois inteiros n e d, maiores que 1 e com d < n. Se d divide n, o algoritmo
fornece a saı́da “n não é primo”. Se d não divide n, o algoritmo fornece a saı́da
“não sei”. Neste caso, trata-se de um algoritmo de verificação de primalidade, em
que fornecemos um certificado: um possı́vel fator d de n ([Cormen et al., 2001]).
Se o certificado for verdadeiro, então n não é primo. Se for falso, nada podemos
concluir, pois n pode ter outros fatores. Assim, um algoritmo não-determinı́stico
nem sempre fornece uma resposta válida e, além disso, a cada execução, o caminho
percorrido e, portanto, a quantidade de passos podem ser diferentes.
Quando a escolha do caminho é totalmente aleatória, ou pelo menos envolve
algum tipo de randomização, temos os chamados algoritmos probabilı́sticos ou
randomizados. Se o algoritmo citado acima escolher, aleatoriamente, novos candidatos a fatores de n para cada vez que a divisão falhar, estará aumentando a
probabilidade de n ser primo. No entanto, por maior que seja a probabilidade,
no caso de uma divisão se verificar, n será composto. Algoritmos probabilı́sticos
que possuem taxa de erro bem controlada são muito usados na prática devido a
sua alta eficiência ([Bach and Shallit, 1996]).
Já os algoritmos determinı́sticos podem ser vistos como um caso especial de
algoritmos não-determinı́sticos que só possuem uma única seqüência de passos
que sempre leva à resposta correta ([Hopcroft et al., 2001]). Assim, para cada
entrada, teremos um tempo de execução fixo para esses algoritmos, além de uma
saı́da correta.
Com relação ao tempo de execução, algoritmos com custo limitado a O(nk ),
em que n representa o tamanho da entrada e k é constante, são chamados algoritmos de tempo de execução polinomial ([Cormen et al., 2001]). Na Teoria da
Complexidade, os problemas são classificados quanto à dificuldade de serem resolvidos por algoritmos. Considerando a complexidade exclusivamente temporal,
há, entre outras, três importantes classes: P, NP e co-NP.
Na classe P estão os problemas de decisão que podem ser resolvidos por algoritmos determinı́sticos em tempo polinomial. A classe P representa, assim, os problemas de melhor solução computacional ou mais fáceis ([Cormen et al., 2001]).
Há casos, entretanto, em que o tempo de execução, apesar de polinomial, é excessivamente grande, preferindo-se a utilização de algoritmos probabilı́sticos de
16
tempo polinomial mais eficientes, com margem de erro controlável.
Na classe NP estão os problemas de decisão que podem ser resolvidos por algoritmos não-determinı́sticos em tempo polinomial (“NP” vem de non-deterministic
polynomial ). Equivalentemente, podemos definir a classe NP como o conjunto
dos problemas de decisão cujas soluções que os satisfazem podem ser verificadas
em tempo polinomial ([Cormen et al., 2001]). Algoritmos de verificação são algoritmos que recebem dois valores: a entrada para o problema e um certificado.
Com a utilização do certificado, eles podem tomar corretamente pelo menos uma
das decisões.
A classe co-NP é complementar à classe NP: compreende os problemas de
decisão cujas soluções que não os satisfazem podem ser verificadas em tempo
polinomial ([Cormen et al., 2001]). Como vimos anteriormente, podemos verificar
se um determinado número n não é primo com a utilização de um certificado d,
ao realizarmos a divisão de n por d. Essa divisão pode ser realizada em tempo
polinomial, nos fornecendo um não correto quando d for fator de n (o certificado
for verdadeiro). Assim, o problema da primalidade pertence à classe co-NP.
Com essas definições, verificamos que qualquer problema pertencente à classe
P, também pertence às classes NP e co-NP, pois, se um problema decidı́vel tem
solução determinı́stica em tempo polinomial, tanto as entradas que satisfazem o
problema, como as que não o satisfazem, podem ser verificadas em tempo polinomial. Ou seja, P ⊆ NP e P ⊆ co-NP. E o fato de um problema estar na classe
NP não quer dizer que o mesmo não esteja na classe P, pois, talvez, apenas não
tenhamos descoberto um algoritmo determinı́stico em tempo polinomial que o resolva. Foi o que aconteceu com o problema da primalidade, que antes do algoritmo
AKS, apresentado em 2002, era considerado apenas pertencente a NP ∩ co-NP
([Agrawal et al., 2004]). Alguns teóricos, inclusive, sugerem que todos os problemas NP e co-NP estejam em P, mas a maioria discorda, sendo, então, P 6= NP e
P 6= co-NP a conjectura atual ([Hopcroft et al., 2001] e [Cormen et al., 2001]).
Figura 2.2: Conjectura atual para a relação entre as classes de complexidade.
Essa conjectura se sustenta nos problemas NP-completo, que são problemas
que se encontram na classe NP e compartilham caracterı́sticas comuns. Se alguém
for capaz de construir um algoritmo que resolva apenas um desses problemas
deterministicamente em tempo polinomial, todos os problemas NP passarão a ser
considerados também P. Mas acredita-se, ainda que não provado, que isso seja
impossı́vel ([Bach and Shallit, 1996]). Na Figura 2.2, vemos a relação mais aceita
atualmente entre essas classes. Para ressaltar, estamos considerando algoritmos
17
construı́dos para computadores binários (computadores realizados)3 .
2.2
Testes de Primalidade
Os números primos são estudados desde a antigüidade ([Ribenboim, 1995]).
Euclides, em seu livro Os Elementos, define o número primo como “aquele que é
medido somente pela unidade” [Coutinho, 2004]. De fato, os gregos antigos não
chamavam a unidade de número e, como não denominavam matematicamente o
zero, seus números naturais começavam no 2. Assim, pela definição de Euclides, entende-se por primo o número (a partir de 2) que é composto apenas por
ele mesmo e pela unidade. Na mesma obra, é demonstrada, com a utilização
do Teorema Fundamental da Aritmética, a infinidade do conjunto dos números
primos.
Naquela época, a dificuldade de se encontrar números primos já intrigava a
curiosidade matemática, pois sua distribuição se mostra incerta entre os naturais.
Eratóstenes, então, construiu um método para encontrar primos, considerado o
primeiro algoritmo para tal propósito, e que hoje é conhecido como Crivo ou
Peneira de Eratóstenes. O método não consiste em nenhuma fórmula explı́cita,
mas implicitamente utiliza multiplicações (em forma de contagem), que os gregos
sabiam ser mais fáceis de realizar do que divisões ([Ribenboim, 1995]).
Do Renascimento Cientı́fico ao Século XIX, os estudos sobre a primalidade
se intensificaram, mas ainda com importância puramente teórica. Fermat, Euler
e Gauss foram alguns expoentes desse tempo. Surgem muitas conjecturas, das
quais várias são derrubadas. Uma das mais famosas é o chamado número de
Fermat, que tem a seguinte forma:
n
Fn = 22 + 1, para n ≥ 0.
Fermat constatou que Fn é primo para 0 ≤ n ≤ 4 e conjecturou que Fn seria
sempre primo para qualquer n ≥ 0. Somente décadas depois, após a morte de
Fermat, Euler demonstrou que F5 = 232 + 1 = 4294967297 é composto pelos
primos 641 e 6700417, derrubando a conjectura. O problema era que, naquele
tempo, fazer cálculos com números dessa ordem era algo extremamente penoso.
Fermat também enunciou um importante teorema que envolve a primalidade, o
Pequeno Teorema de Fermat, base de muitos testes de primalidade probabilı́sticos
atuais ([Coutinho, 2004]) e do próprio algoritmo AKS ([Agrawal et al., 2004]).
Antes de enunciarmos e provarmos esse teorema, vejamos a seguinte
Proposição 2.2.1. Sejam a, b e p inteiros, com p primo. Se p divide o produto
ab, então p divide a ou p divide b (ou ambos).
Prova. Se p é primo, não possui fatores menores que p. Se p divide ab, então o
produto ab possui, ao menos, um fator p que deve estar em a ou b. Não há como
dividir esse fator em fatores menores separados em a ou b, pois ele é primo.
3
Algoritmos feitos para computadores idealizados, como os quânticos, podem ter uma outra
classificação para sua complexidade.
18
Veja que se p não é primo, então a proposição não vale. Por exemplo, 6|(4 · 3)
mas 6 - 4 e 6 - 3. Agora, vejamos o
Teorema 2.2.2 (Pequeno Teorema de Fermat).
Se m é primo, então, para qualquer a inteiro tal que mdc(a, m) = 1, temos:
am−1 = 1 (mod m).
Prova. Considere o intervalo [1, m − 1]. Sabemos que m não divide nenhum
número desse intervalo, já que são todos menores que m. Para quaisquer j e k
distintos pertencentes a esse intervalo, |j − k| também pertence ao intervalo, logo
m - (j − k). Então, como a é relativamente primo a m, temos que nenhum dos
números do conjunto {a, 2a, 3a, ..., (m−1)a} divide m. Se a divisão fosse possı́vel,
como m é primo, pela Proposição 2.2.1, ou m teria que dividir a, ou teria que
dividir um dos números no intervalo [1, m − 1].
Assim, os termos a, 2a, 3a, ..., (m − 1)a, quando reduzidos módulo m, são nãonulos e distintos entre si. Caso contrário, se ja = ka(mod m), com j e k distintos
e pertencentes ao intervalo [1, m − 1], temos, pela definição de congruência, que
m | (ja − ka) = a(j − k). Como m é primo, isso significa que ou m divide a ou
m divide (j − k), ambos absurdos.
Temos, então, que a, 2a,..., (m − 1)a são congruentes a 1, 2,..., (m − 1) módulo
m, em alguma ordem, numa relação biunı́voca4 . Podemos escrever que
a · 2a · 3a · . . . · (m − 1)a = 1 · 2 · 3 · . . . · (m − 1) (mod m).
Simplificando ambos os lados por 1 · 2 · 3 · . . . · (m − 1), temos o resultado
desejado.
Portanto, assumindo que mdc(a, m) = 1, temos que se a congruência não
se verificar, certamente m é composto. Já a recı́proca do Teorema 2.2.2 não é
verdadeira: podemos ter um certo m que é composto e que satisfaz a congruência
para algum a relativamente primo a m. Por exemplo, 53 = 1 (mod 4). Ou seja,
no caso do teste não falhar, teremos apenas uma probabilidade de que o número
m é primo, podendo ser aumentada ao se repetir o teste com um novo número a,
mas nunca nos dando a certeza. Neste caso, m é chamado pseudoprimo de base
a ([Ribenboim, 2004]).
Há uma forma mais comum desse teorema que será usada em nossa prova do
AKS:
Corolário 2.2.3.
Se m é primo, então, para qualquer a inteiro , temos:
am = a(mod m).
4
Estas são exatamente as classes residuais módulo m distintas, excluindo-se a classe 0̄
([Hefez, 2002])
19
Prova. ([Campello and Leal, 2007]). Se m - a, como m é primo, então a e m
são coprimos e podemos usar o Pequeno Teorema de Fermat:
am−1 = 1(mod m).
Então, pela definição de congruência,
m | (am−1 − 1).
Logo,
m | a(am−1 − 1),
o que é o mesmo que
m | (am − a).
Então, novamente pela definição de congruência,
am = a(mod m).
Por outro lado, se m | a, então
m | a(am−1 − 1),
o que é o mesmo que
m | (am − a).
Logo, pela definição de congruência,
am = a(mod m).
O Pequeno Teorema de Fermat nos fornece um teste de primalidade de tempo
polinomial, mas não-determinı́stico5 . Ele apenas responde com certeza para a nãoprimalidade de um número. Até 2002, na Teoria da Complexidade, o problema
era, pois, comumente considerado classe co-NP, apesar de Pratt ter mostrado, em
1974, que o problema estava na classe NP também ([Agrawal et al., 2004]).
As coisas começaram a mudar, no que diz respeito a pesquisas e necessidades
práticas, com o advento das ferramentas computacionais. Já no final do Século
XIX, Lucas descobre um método eficiente para testar a primalidade de números
de Mersenne (números que têm a forma 2p − 1, com p primo). Seu método foi
refinado por Lehmer, um dos pioneiros no uso dos computadores em teoria dos
números ([Coutinho, 2004]), em meados do século passado, e é usado até hoje,
sob o nome de teste de Lucas-Lehmer.
A partir da década de 70, o estudo da primalidade deixa de ter importância
puramente teórica devido ao aparecimento dos algoritmos de criptografia de dados
e, com o auxı́lio de computadores mais velozes, teve importantes avanços. Algoritmos de criptografia, como o RSA, baseiam-se na utilização de grandes números
primos que, multiplicados, geram um composto o qual, por sua vez, participará
5
Se mantivermos o mesmo a e repetirmos o teste, a resposta será a mesma, inconclusa. Mas
se realizarmos o teste novamente, variando o valor de a, teremos um teste probabilı́stico.
20
na formação das chaves criptográficas. Para que alguém quebre o código, será
necessária a fatoração desse número. Mas aı́ está a segurança da criptografia
RSA: computacionalmente é mais difı́cil decompor um número em seus fatores
primos do que testar a primalidade de dois grandes números para serem usados
na geração das chaves ([Cormen et al., 2001]). E quanto mais eficientes os testes
de primalidade, mais fácil será encontrar primos gigantes para formarem a chave,
tornando ainda maior essa diferença.
Basicamente, até 2002, tı́nhamos dois grupos de testes de primalidade: algoritmos determinı́sticos, mas exponenciais, e algoritmos polinomiais, mas nãodeterminı́sticos, sobretudo probabilı́sticos ([Ribenboim, 2004]). Estes últimos
ainda são muito usados na prática devido a sua alta eficiência ([Coutinho, 2004]),
entre eles o teste de Miller-Rabin ([Cormen et al., 2001]), que avalia pseudoprimos
de Fermat, e os testes com curvas elı́pticas ([Ribenboim, 2004]).
Antes de enunciarmos o algoritmo AKS, os teoremas envolvidos e a demonstração de sua correção, vamos enunciar o Crivo de Eratóstenes, que inclusive será
um dos métodos utilizados na análise da complexidade de duas de suas etapas.
Também vamos incluir um pequeno teorema sobre a distribuição dos números
primos, além de verificar como se determina o custo de execução de um teste
de primalidade em função do tamanho da entrada, já que o parâmetro usado
para tamanho da entrada de um problema varia, conforme o tipo de problema
([Cormen et al., 2001]).
2.2.1
O Crivo de Eratóstenes
Como o próprio nome diz, o Crivo de Eratóstenes separa os primos dos compostos, dentro de um intervalo dado, como se fosse uma peneira.
Algoritmo 1 Crivo de Eratóstenes
Primeiro, determine um número final para o intervalo, iniciado em 2, em que
se deseja achar todos os números primos.
Comece com o primeiro número do intervalo, no caso 2. Então, risque todos os
demais números do intervalo que sejam múltiplos de 2 (simplesmente, risque-os
contando de 2 em 2).
Agora, vá ao próximo número do intervalo que não esteja riscado, neste caso,
3. Risque os demais de 3 em 3 (múltiplos de 3).
Continue o procedimento de procurar no intervalo o próximo número não riscado (primo) e de riscar todos os seus múltiplos até que todos os números
compostos do intervalo estejam riscados. Ou seja, para cada p (o próximo
número ainda não riscado da lista), risque os demais de p em p.
Podemos simplificar o teste, deixando-o mais econômico, ao verificarmos uma
propriedade importante: ao passarmos pelo número inteiro igual ou imediatamente superior ao valor da raiz quadrada do limite do intervalo, todos os compostos já estarão riscados. Isso é uma conseqüência do seguinte
21
Teorema 2.2.4 (Teorema da Fatoração Única ou Teorema Fundamental
da Aritmética). Dado um inteiro positivo n ≥ 2, podemos sempre escrevê-lo na
forma:
n = p1 e1 · p2 e2 · ... · pk ek ,
em que 1 < p1 < p2 < ... < pk são números primos e e1 , e2 , ..., ek são inteiros
positivos.
Ou seja, qualquer número inteiro maior que 1 pode ser decomposto em números primos, e essa decomposição é única, a menos da ordem em que aparecem os
fatores.
Prova. Primeira parte: qualquer inteiro maior que 1 pode ser decomposto em
primos.
Vamos usar o Princı́pio da Indução Matemática (ver Apêndice A). Seja S o
conjunto de todos os inteiros positivos que são produtos de primos. 2 ∈ S (base
de indução), já que ele próprio é número primo e admite decomposição trivial.
Suponha que todo inteiro r, com 2 ≤ r < a para algum inteiro a > 2, seja
elemento de S (passo indutivo). Se a é primo, então também pertence a S, pois
admite decomposição trivial. Se a é composto, então a = bc, sendo que 2 ≤ b < a
e 2 ≤ c < a. Portanto, pela hipótese indutiva, temos que b e c são elementos de
S, ou seja, podem ser escritos como produtos de primos. Assim, a também é um
produto de primos.
Segunda parte: unicidade da decomposição.
Novamente usaremos o Princı́pio da Indução Matemática. Sejam n = p1 p2 ...ps
e n = q1 q2 ...qt duas decomposições de n, em que p1 ≤ p2 ≤ ... ≤ pn e q1 ≤ q2 ≤
... ≤ qt são primos (a possibilidade dos fatores serem iguais elimina a representação
em potências, como apresentada no inı́cio do teorema). Se s = 1, temos que
n = p1 = q1 q2 ...qt . Mas, como p1 é primo, então, necessariamente, t = 1, p1 = q1
e as duas decomposições são idênticas. Suponha agora que s > 1 e que a segunda
parte do teorema seja verdadeira para s − 1. De n = p1 p2 ...ps = q1 q2 ...qt , temos
que p1 é um divisor do produto q1 q2 ...qt e, logo, é um divisor de um dos fatores
qi , com 1 ≤ i ≤ t. Como qi é primo, então p1 é igual a qi . Precisamos, agora,
checar se os demais fatores também são idênticos. Seja n0 = n/p1 = n/qi . As
decomposições para n0 seriam p2 p3 ...ps = q1 q2 ...qi−1 qi+1 ...qt . Da hipótese indutiva
(s−1 fatores), temos que estas duas últimas decomposições são idênticas, a menos
da ordem dos fatores. Logo, a segunda parte do teorema também é verdadeira
para s, sendo p1 p2 ...ps e q1 q2 ...qt decomposições idênticas para n.
Assim, seja f o menor fator primo de um composto n. Então, n = f a, em que
a ≥ f também é fator de n, podendo ser primo ou composto por primos maiores
ou iguais a f . Mas, se √
a ≥ f , então, substituindo na igualdade anterior, temos
2
que n ≥ f , donde f ≤ n é o menor fator primo de um composto n.
Voltando ao crivo, suponha que estejamos prestes a riscar os compostos de p
em p para o primo p. Caso passemos por um composto que também seja múltiplo
de algum primo q < p, o mesmo já estará riscado (isso foi feito quando passamos
22
por q e riscamos os múltiplos de q em q). Então, basta começarmos a procurar
por múltiplos de p que não sejam múltiplos de √
algum primo menor do que p. Ou
2
seja, a partir de p . Mas, se p for maior que n, p2 será maior que n e estará
fora do intervalo estipulado para o crivo. Portanto, para cada primo p, basta
√
riscarmos os compostos de p em p a partir de p2 , e quando p for maior que n,
todos os compostos já estarão riscados.
Ainda podemos simplificar um pouco mais o teste. Começamos nosso intervalo
a partir de 3 e listamos apenas os números ı́mpares, já que 2 é o único número
par primo e todos os demais pares são múltiplos de 2. Desta forma, para cada
primo p, riscamos os múltiplos de 2p em 2p.
O Crivo de Eratóstenes é fácil de ser implementado e útil para encontrar
números primos em intervalos pequenos. Porém, para números muito grandes,
torna-se inutilizável devido a sua complexidade exponencial, como veremos na
Subseção 2.2.3.
2.2.2
Distribuição dos Números Primos
A distribuição dos números primos é um assunto importante, do qual depende
o bom entendimento do algoritmo AKS. Como dito anteriormente, desde a antigüidade os matemáticos sabem que os números primos são infinitos. Um teorema
que prova essa propriedade é devido a Euclides ([Monteiro, 1978] e [Hefez, 2002]),
e é conseqüência do Teorema da Fatoração Única:
Teorema 2.2.5. Existem infinitos números primos.
Prova. Suponha que p1 , p2 ,...,ps sejam todos os números primos existentes.
Sejam os inteiros a = p1 p2 ...ps e a + 1 = p1 p2 ...ps + 1. Como é maior que 1,
então, pelo Teorema da Fatoração Única, a + 1 pode ser fatorado exclusivamente
por números primos. Seja p um dos fatores primos de a + 1. O número p deve,
necessariamente, coincidir com um dos primos p1 , p2 ,...,ps , pois estes representam,
por hipótese, todos os primos existentes. Logo, p divide o produto p1 p2 ...ps = a.
Como p é fator de a+1, e divide a, segue que p tem que dividir 1, o que é absurdo.
Mas esse teorema só mostra que os números primos são infinitos. Não diz nada
sobre como são distribuı́dos. Há um importante teorema sobre a distribuição dos
números primos, o qual mostra que a quantidade de primos entre 2 e um inteiro
positivo n, freqüentemente denotada por π(n), é
n
.
ln(n)
Esse teorema foi conjecturado por vários matemáticos ([Ribenboim, 1995]),
entre eles, Gauss. Por volta de 1850, Tschebycheff mostrou que
n
n
0, 922
≤ π(n) ≤ 1, 105
(2.4)
ln(n)
ln(n)
π(n) ∼
π(n)
e, portanto, se limn→∞ n/ln(n)
existir, então este converge para 1. Mas essa
convergência só foi provada em 1896, nos trabalhos independentes de Hadamard e Vallé Poussin, o que ficou conhecido como Teorema dos Números Primos
23
([Coutinho, 2004]). A demonstração desse teorema é bastante difı́cil, por isso não
iremos prová-lo aqui. Para maiores detalhes, veja [Ribenboim, 1995]. No entanto,
[Coutinho, 2004] nos apresenta um interessante teorema que envolve a distribuição dos números primos e que pode ser visto como uma “prova fraca” de uma das
desigualdades de (2.4), sendo importante para se entender o custo de uma das
etapas do algoritmo AKS ([Coutinho, 2004]):
Teorema 2.2.6. Sejam n um inteiro positivo e P(2n) o conjunto de todos os
primos positivos menores ou iguais a 2n. Então,
Y
2n
=
pk p ,
n
p∈P(2n)
onde6
kp =
∞
X
(b
m=1
2n
n
c − 2b m c).
m
p
p
Prova. Primeiro, note que a soma kp é finita, pois, quando pm > 2n, temos que
b
2n
n
c = b m c = 0.
m
p
p
A quantidade de múltiplos positivos de q menores ou iguais a n pode ser
denotada por bn/qc. Por exemplo, a quantidade de múltiplos positivos de 4
menores ou iguais a 20 é igual a quantidade de múltiplos positivos de 4 menores
ou iguais a 22, ou seja, b20/4c = b22/4c = 5, que são exatamente os múltiplos
4, 8, 12, 16 e 20.
Mas os múltiplos positivos de q menores que n também são menores que n!. E
mais: esses múltiplos participam da formação de n!, com pelo menos uma potência
de q. Em outras palavras, q bn/qc |n!. Mas um múltiplo de q pode também ser uma
potência de q, de modo que queiramos representar todas as potências de q que
estão na fatoração de n!. Isso é especialmente útil se q for primo. Usaremos a
notação
∞
X
(bn/pk c) =
µ(n, p) =
k=1
bn/pc + bn/p2 c + bn/p3 c · · · bn/pm c,
para representar a quantidade total de potências, a qual chamaremos multiplicidade, de um primo p ≤ n na fatoração de n!. Perceba que múltiplos de potências
maiores também são múltiplos de potências menores, por isso são contados mais
de uma vez, justamente na quantidade de potências de p que possuem. E essa
soma é finita, pois quando pk > n, passarão a ser somados apenas 0’s.
Desenvolvendo o binomial, temos
2n
2n!
=
.
n
n!n!
6
Os sinais bc serão usados para representar o inteiro igual ou imediatamente inferior, e os
sinais de serão usados para representar o inteiro igual ou imediatamente superior.
24
Podemos, então, usar a notação de multiplicidade para representar as potências de p que há nesse binomial. Note que as potências de p que formam n!
também são potências de p formadoras de 2n!. E em 2n! há, pelo menos, o dobro
de potências de p que há em n!. Mas esses fatores em comum serão cancelados
na fração, pois são termos comuns entre o numerador
e o denominador. Então,
podemos dizer que a multiplicidade de p em 2n
é
n
∞
∞
X
X
k
µ(2n, p) − 2µ(n, p) =
(b2n/p c) − 2
(bn/pk c).
k=1
k=1
E isso é exatamente kp do enunciado do teorema. Assim, para cada um dos p
primos que existem em P(2n), existe um respectivo kp , que é a sua multiplicidade
em 2n
. Multiplicando
cada um deles elevado ao seu respectivo kp , obtemos
n
2n
exatamente n .
Desse teorema seguem dois corolários, sendo que o segundo será usado no
cálculo do custo do algoritmo AKS:
Corolário 2.2.7. Cada termo kp do Teorema 2.2.6 é menor ou igual a blog2 (2n)c.
Prova. Seja ps a maior potência de p que divide 2n. Neste caso, kp não pode ser
maior que s, pois representa, justamente, a quantidade de fatores primos p em 2n.
Por outro lado, ps ≤ 2n. Aplicando log nos dois lados, temos slog2 p ≤ log2 (2n).
Mas p é primo positivo, logo p ≥ 2 e log2 p ≥ 1. Então,
kp ≤ s ≤ blog2 (2n)/log2 pc ≤ blog2 (2n)c.
Corolário 2.2.8. Se n é um inteiro positivo, então 2n ≤ (2n2 )# , onde m# ,
denominado primorial de m, representa o produto de todos os primos positivos
menores ou iguais ao inteiro positivo m.
Prova. Seja r um inteiro positivo. O produto,
Y
pr = ((2n)# )r ,
(2.5)
p∈P(2n)
pois significa, justamente, multiplicar todos os primos positivos menores ou iguais
a 2n elevados a r.
Como
Y
2n
=
pk p
n
p∈P(2n)
e kp ≤ blog2 (2n)c, se fizermos r = blog2 (2n)c em (2.5), teremos que
2n
divide ((2n)# )r ,
n
25
2n
pois o produto de potências de primos
que
representa está incluı́do no produto
n
Q
r
de potências maiores de primos de p∈P(2n) p . Portanto,
2n
≤ ((2n)# )r .
n
Mas,
2n
2m(2m − 1)(2m − 2) · · · (m + 2)(m + 1)
=
=
n
m!
2m (2m − 1) 2(m − 1) (2m − 3) 2(m − 2)
(m + 2) (m + 1)
=
···
≥ 2n ,
m m−1 m−2 m−3 m−4
2
1
do que segue:
2n ≤ ((2n)# )r .
Se essa relação vale para o inteiro positivo n, então vale para n2 , ou seja,
2
2n ≤ ((2n2 )# )r .
Aplicando log base 2 em ambos os lados, temos:
2
log2 (2n ) ≤ log2 (((2n2 )# )r )
n2 ≤ rlog2 ((2n2 )# ).
Como escolhemos r = blog2 (2n2 )c, então
n2 ≤ (log2 (2n2 ))log2 ((2n2 )# )
≤ (log2 2 + log2 n2 )log2 ((2n2 )# )
≤ (1 + 2log2 n)log2 ((2n2 )# ).
Assim,
n≤
p
p
(1 + 2log2 n)log2 ((2n2 )# ) ≤ (1 + 2log2 n) · log2 ((2n2 )# ).
(2.6)
Mas,
n≥
p
(1 + 2log2 n)
para n ≥ 2. Disto, e de (2.6), segue que
n ≤ log2 ((2n2 )# )
2n ≤ (2n2 )# .
26
2.2.3
Eficiência dos Testes de Primalidade
Já dissemos que até antes do algoritmo AKS ser apresentado, os algoritmos
que testavam a primalidade de um número eram divididos, com relação ao tempo
de resposta para o tamanho da entrada, entre os determinı́sticos exponenciais e
os não-determinı́sticos polinomiais. Mas como é feita essa medida de eficiência7 ?
Antes de mais nada, temos que saber qual o parâmetro usado para medir o tamanho da entrada, como referido no inı́cio da seção. De uma forma geral, esses
testes basicamente realizam operações numéricas com o dado de entrada afim de
se verificar sua primalidade. Computadores binários realizam cálculos binários,
os quais terão um custo de tempo maior quanto mais bits (dı́gitos binários) estiverem envolvidos nas operações. Ou seja, quanto mais bits possuir a entrada,
maior será o custo do algoritmo. Desta forma, o tamanho da entrada usado para
o cálculo da eficiência dos testes de primalidade é a quantidade de bits da entrada.
Mas a quantidade de bits depende diretamente da entrada. Na verdade, para
uma entrada n, a quantidade b de bits é ≈ log2 n. Devido às propriedades da
notação assintótica, assumimos b = log2 n (o número b de bits usados para a
representação binária de n) como sendo o tamanho da entrada n.
Isso pode causar um certo desconforto quando analisamos a eficiência de um
teste de primalidade. Por exemplo, um teste de primalidade de custo polinomial
será aquele que tenha custo O((log2 n)k ) para algum k inteiro. Por outro lado, um
algoritmo que seja O(n), ou pior, será dito exponencial. Não podemos perder de
vista que n não representa o tamanho da entrada, papel desempenhado por b (a
quantidade de bits da entrada). Ou seja, um custo O((log2 n)k ) equivale a O(bk ),
em que b é a quantidade de bits da entrada (tamanho da entrada) e k é um inteiro,
portanto polinomial. Por outro lado, um custo O(n) equivale a O(2log2 n ) = O(2b ),
ou seja, exponencial.
Podemos, então, realizar os cálculos dos custos das operações elementares de
inteiros (soma, subtração, multiplicação e divisão) realizadas por computadores
binários, que são as operações básicas para operações mais complexas e o ponto
de partida para o custo dos testes de primalidade. Deixaremos de fora outras
operações mais simples e fatores que não dependem tanto do tamanho da entrada (operações de comparação, arquitetura da máquina, latência de memória,
tempo de transferência de dados etc) e que, portanto, não influenciam na notação
assintótica.
No caso da soma entre dois inteiros, os bits dos dois números são somados um
a um, da direita para a esquerda, levando em consideração, ainda, o bit de reserva
quando a soma dos bits anteriores for maior que 1 (o conhecido ”vai um” da soma).
Considere que o maior dos números, n, tenha b bits de comprimento. A outra
parcela também poderá ser representada por b bits de comprimento, preenchida
com 0’s à esquerda, caso seja necessário. Assim, haverá pelo menos b somas. No
entanto, não consideramos o cálculo com os bits de reserva. Poderemos ter, no
máximo, um bit de reserva para cada bit a partir do segundo. Ou seja, podemos
ter mais b − 1 somas, totalizando um máximo possı́vel (pior caso) de 2b − 1 somas
(um polinômio na variável b, de grau 1). Assim, pela notação assintótica, temos
7
Importante salientarmos que estamos nos referindo, exclusivamente, à eficiência temporal.
A complexidade espacial não será considerada neste trabalho.
27
que o custo da soma entre dois inteiros é O(b), em que b representa o número de
bits do maior número da entrada. Como b = log2 n, temos que o custo da soma
entre dois números inteiros menores ou iguais a n é O(log2 n).
Na multiplicação, consideramos novamente b o número de bits do maior fator.
Primeiro, multiplicamos o maior fator por cada bit do menor fator. Em binário,
isso é relativamente fácil. Para cada bit 1 do menor fator, geramos um produto
elementar idêntico ao maior fator, mas deslocado à esquerda proporcionalmente
à ordem do bit no menor fator. Para cada bit 0, teremos um produto nulo. Desta
forma, teremos, no máximo, b produtos gerados (no caso em que os fatores têm
o mesmo número de bits e todos são 1). Ou seja, um custo máximo de b operações. Ao final, somamos todos os produtos elementares e obtemos a multiplicação.
Cada soma terá um custo máximo de 2(b + 1) − 1 = 2b + 1 operações, que é o
custo máximo encontrado anteriormente para a soma, considerando uma parcela
com b + 1 bits (devido ao deslocamento à esquerda de cada parcela subseqüente).
Como são b produtos elementares, teremos b − 1 somas. Desta forma, considerando ainda o custo inicial para a geração dos produtos elementares, o custo total
da multiplicação será (b − 1)(2b + 1) + b = 2b2 − 1 operações, o que é O(b2 ).
Assim, o custo da multiplicação entre dois números inteiros menores ou iguais a
n é O((log2 n)2 ). Esse resultado era esperado, se pensarmos que a multiplicação
de inteiros não passa de uma repetição de somas que têm custo O(b), e a quantidade dessas somas (produtos elementares) depende diretamente da quantidade
de dı́gitos dos fatores.
Para a subtração a − b, em que a e b são números inteiros, lembramos que
se trata da soma de a com o oposto de b. Logo, há apenas o trabalho inicial de
trocar o bit de sinal de b para depois realizar a soma normalmente. Assim, o
custo da operação de subtração entre dois números inteiros menores ou iguais a
n é O(log2 n).
Como na multiplicação temos o encadeamento de somas, na divisão entre
inteiros temos o encadeamento de subtrações. Para dois números inteiros a e b,
a divisão a/b representa a quantidade de vezes que b pode ser subtraı́do de a.
Caso a seja maior ou igual a b, subtraı́mos b de a sucessivamente até atingirmos
um valor menor que b. Não vamos demonstrar aqui, mas o custo para a divisão8
e, conseqüentemente, para o cálculo de restos é O((log2 n)2 ), para dois números
menores ou iguais a n.
2.2.3.1
Custo do Crivo de Eratóstenes
A única operação efetuada no Crivo de Eratóstenes é a soma, que é executada
na contagem de 2p em 2p (considerando o crivo mais econômico, em que constam
apenas ı́mpares). Para cada primo p, adicionamos 2p sucessivamente, obtendo
3p, 5p, 7p etc, que são os múltiplos ı́mpares de p, até n. Como as parcelas estão
limitadas a n, teremos um custo limite de O(log2 n) para cada soma. Precisamos
agora saber quantas somas serão feitas. Mais precisamente, quantos compostos
ı́mpares de p existem até n.
8
Para verificação, [Coutinho, 2004] sugere a leitura de von zur Gathen e J. Gerhard, 1999,
Modern Computer Algebra, Cambridge University Press.
28
Seja k > 0 um inteiro. Se kt ≤ n para algum inteiro positivo t, então os
múltiplos de k menores ou iguais a n são:
kt, em que t = 1, 2, 3, ..., bn/kc.
Assim, existem bn/kc múltiplos de k de 1 a n. Como estamos interessados nos
múltiplos ı́mpares, temos, aproximadamente, metade desse valor, ou seja, bn/kc/2
múltiplos ı́mpares de k menores que n.
Somando 2p de cada vez, indo de p até n, realizaremos, no máximo, bn/kc/2
somas, ao custo de O(log
√ 2 n) cada uma. Mas precisaremos fazer isso para cada
primo menor ou igual a n. Suponha que P (k) seja o conjunto de todos os primos
menores ou iguais a k. Desta forma, realizaremos, no máximo
X
X
X
√
bn/kc/2 ≤
n/2k ≤
n/2 ≤ (n n)/2 = (n3/2 )/2
√
p∈P ( n)
√
p∈P ( n)
√
p∈P ( n)
somas, a um custo de O(log2 n) cada uma. Portanto, descartando a constante 1/2,
a qual é insignificante para a notação
O, encontramos um custo total máximo de
√
3/2
O(n log2 n). E como log2 n ≤ n para n ≥ 4, temos um custo total limitado a
O(n2 ). Esta é uma estimativa alta para o custo do Crivo de Eratóstenes, calculada
de forma simples após muitas concessões. Existem estimativas melhores, mas
ainda sim exponenciais ([Coutinho, 2004]). O importante é que essa estimativa
será usada para analisar duas etapas do algoritmo AKS, a qual faz uso do crivo.
2.3
O Algoritmo AKS
Em 2002, os indianos Manindra Agrawal, Neeraj Kayal e Nitin Saxena disponibilizaram na Internet um artigo contendo um algoritmo capaz de realizar um
teste de primalidade determinı́stico em tempo polinomial, resolvendo um antigo
problema matemático ([Ribenboim, 2004]). Após contribuição de Lenstra Jr., eles
publicaram a versão definitiva de seu artigo em 2004 ([Agrawal et al., 2004]).
2.3.1
O Teorema Fundamental
A idéia do algoritmo vem de um lema usado em [Agrawal and Biswas, 2003]
como a base para um teste probabilı́stico de tempo polinomial:
Lema 2.3.1. Sejam a e n inteiros, com n ≥ 2 e mdc(a, n) = 1. Então, n é primo
se, e somente se,
(X + a)n = X n + a (mod n).
Antes de provarmos o lema, vejamos o que ele significa. A notação (mod n)
após a identidade, usada em [Agrawal et al., 2004], significa que os dois polinômios são comparados após a redução dos seus coeficientes módulo n. Ou seja,
(X + a)n = X n + a no anel de polinômios Zn [X].
Por exemplo, o polinômio P (X) = 7X + 3 será reduzido a 2X + 3 no anel
Z5 [X], pois 7 = 2 mod 5 e 3 = 3 mod 5. Assim, (7X + 3) = (2X + 3) mod 5.
29
Portanto, o Lema 2.3.1 nos traz uma identidade de classes de polinômios
módulo n. Vamos à
Prova. Do lado esquerdo, utilizando o teorema binomial, temos:
n
n
n
(X + a) = X + a +
n−1 X
n
k=1
k
X n−k ak .
(2.7)
Consideraremos, primeiro, o caso de n ser primo. Como
n
n!
=
,
k
k!(n − k)!
temos que
n
· k!(n − k)! = n!.
k
(2.8)
Mas n |n! e n é primo, então, de (2.8) e da Proposição 2.2.1, n deve dividir o
produto nk · k!(n − k)!. Só que, como n é primo, para todo 0 < k < n, n - k! e
n - (n − k)!. De fato, n primo não pode dividir nenhum fatorial de inteiro menor
que n, pois esses fatoriais
são compostos apenas de fatores primos menores que
n
n. Portanto, n | k para todo 0 < k < n, tornando esses coeficientes, e todo o
somatório em (2.7), nulos módulo n.
Assim,
(X + a)n = X n + a (mod n)
n−1 X
n
n
n
X +a +
X n−k an = X n + a (mod n)
k
k=1
X n + an = X n + a (mod n).
Do Pequeno Teorema de Fermat (Corolário 2.2.3), an = a (mod n), quando n
é primo, o que completa a primeira parte da prova.
Por outro lado, se n for composto, existe ao menos um fator primo q de n.
Para k ∈ N, suponha q k | n, e q k+1 - n, ou seja, k é a maior potência de q que
divide n. Logo,
∃ c ∈ Z tal que
Neste caso9 , q k -
n
q
n
= c e q - c.
qk
(2.9)
, pois, do contrário, terı́amos:
n
n (n − 1)(n − 2)...(n − q + 1)
n n−1
=
q |
=
.
q
q
(q − 1)!
q q−1
k
Mas q k | nq
temos que
9
n−1
q−1
significa que o resultado da divisão deve ser inteiro e, de (2.9),
Prova modificada de [Tou and Alexander, 2005].
30
n n−1
q q−1
qk
c n−1
.
=
q q−1
Como q - c, e q é primo, então, para que o resultado anterior seja inteiro,
n−1
(n − 1)(n − 2)...(n − q + 1)
q|
=
,
q−1
(q − 1)!
o que significa, novamente por q ser primo (Proposição 2.2.1), que
q | (n − 1) ou q | (n − 2) ou q | (n − 3) ou ... ou q | (n − q + 1).
E, neste caso,
n = 1 (mod q) ou n = 2 (mod q) ou ... ou n = q − 1 (mod q).
Um absurdo, pois assumimos que q | n.
Além disso, q k é relativamente primo a aq , pois mdc(a, n) = 1. Como q é fator
de n, segue que mdc(a, q) = 1. Então, potências de q não possuem qualquer fator
em comum com a ou
potências de a e, assim, mdc(aq , q k ) = 1.
com
n
q
Portanto, n - q · a , o que significa que nem todos os coeficientes do somatório em (2.7) são nulos módulo n e a identidade não se verifica no anel Zn [X],
completando nossa prova, já que dois polinômios numa mesma variável só são
iguais se possuı́rem os mesmos coeficientes para cada monômio de mesmo grau.
Esse lema representa um teste determinı́stico interessante de primalidade, não
fosse ele exponencial! Para comprovar isso, basta mostrarmos que um dos passos
da computação da identidade seja exponencial em função do tamanho da entrada.
Bom, mas a identidade está sobre Zn [X], de forma que não estamos preocupados
como esse anel foi implementado. Então, comecemos já computando (X + a)n em
Zn [X] para n > 0. O primeiro cuidado que precisamos ter é em como expandir
esse termo. Uma forma de fazer isso é utilizando recursão:
(X + a)n = (X + a)(X + a)n−1 .
Neste caso, precisaremos realizar n − 1 produtos. Como a multiplicação tem
custo O((log2 n)2 ), conforme mostrado na Subseção 2.2.3, só o cálculo desses
produtos, sem contar os demais cálculos de redução módulo n, terá um custo
O((n − 1)(log2 n)2 ) = O(n(log2 n)2 ), que é uma função exponencial do tamanho da
entrada em bits. Assim, podemos dizer que esse método tem custo, pelo menos10 ,
Ω(n(log2 n)2 ).
Também
podemos tentar usar a expansão binomial (X + a)n = X n + an +
Pn−1
n
n−k k
a , como fizemos na prova do lema. Neste caso, terı́amos n − 1
k=1 k X
parcelas no somatório. Para avaliar cada coeficiente módulo n, será necessária
uma divisão, que tem custo O((log2 n)2 ), conforme mostrado na Subseção 2.2.3.
10
Como a notação Ω, ao contrário da notação O, é usada para limitar inferiormente o crescimento de funções, podemos ter certeza que não há nada melhor.
31
Mas, no pior caso, quando n é primo, teremos que avaliar os n − 1 coeficientes. Portanto, o custo total para o pior caso é O(n(log2 n)2 ), que já sabemos ser
exponencial.
Uma forma de diminuir o número de operações é calcular quadrados. A partir de X + a, calculamos (X + a)2 , fazendo (X + a)(X + a). E, em seguida,
fazemos as simplificações módulo n necessárias. Depois, calculamos (X + a)4 =
(X + a)2 (X + a)2 , e assim prosseguimos até (X + a)n . Sem considerar as reduções
módulo n intermediárias, teremos realizado, no máximo, apenas log2 n produtos
de polinômios. O problema é que cada produto agora tem custo O(g 2 (log2 n)2 ),
em que g é o grau do polinômio que está sendo multiplicado, já que a multiplicação de polinômios de um mesmo grau g requer, no pior caso, em torno de g 2
multiplicações11 . No primeiro passo, ou seja, no primeiro produto, o grau é 1.
Depois, 2, 22 , . . . , 2log2 n/2 . Como não há limite para o grau dos polinômios em
Zn [X], o grau dos fatores envolvidos em cada quadrado cresce√exponencialmente.
Assim, só o custo do cálculo para o último quadrado será O( n(log2 n)2 ), e, portanto, ainda exponencial em relação ao tamanho da entrada que, como sabemos,
é medido em número de bits. Como não verificamos os
√ demais custos, podemos
dizer que esse método tem custo igual ou pior que O( n(log2 n)2 ).
Seja como for, não é possı́vel calcular a identidade do Lema 2.3.1 em tempo
polinomial. Segundo [Agrawal et al., 2004], o custo desse cálculo é Ω(n).
Então, uma forma de melhorar a eficiência do teste, reduzindo os coeficientes
envolvidos nos cálculos da identidade do Lema 2.3.1, seria avaliar ambos os lados
módulo um polinômio na forma X r − 1 para algum r > 0 ∈ Z:
(X + a)n = X n + a (mod X r − 1, n).
(2.10)
Ou seja, obtemos os restos das divisões (polinomiais) de (X +a)n e X n +a pelo
polinômio X r − 1, os quais possuirão graus menores que r, e depois os avaliamos
módulo n ([Ribenboim, 2004]). Como o polinômio X r − 1 gera um ideal no anel
Zn [X], temos que aquela notação indica que a identidade agora será avaliada no
anel quociente Zn [X]/(X r − 1) ([Agrawal et al., 2004]). Ou seja,
(X + a)n = X n + a em Zn [X]/(X r − 1).
Agora, é possı́vel computar essa nova identidade em tempo polinomial. Para
mostrar isso, ao contrário do que fizemos com a identidade anterior, não basta
mostrar o custo de um único passo. Na verdade, teremos que mostrar que todos
os passos dessa computação terão custo limitado por um polinômio em função do
tamanho da entrada. Novamente, não é importante saber como o anel quociente
será implementado. Apenas queremos saber quanto custa verificar a identidade
naquele anel. Assim, começaremos com a expansão de quadrados, que sabemos
que gera, no máximo, log2 n produtos. Precisamos descobrir, então, quanto custa
o cálculo de um quadrado em Zn [X]/(X r − 1).
11
No pior caso, temos g +1 coeficientes não nulos em cada polinômio. Fazendo a multiplicação
distributivamente, teremos (g + 1)2 multiplicações.
32
Seja p um polinômio reduzido módulo (X r − 1) em Zn [X]. O cálculo de p2
tem custo limitado por O(r2 (log2 n)2 ) em Zn [X], já que o grau g de p é limitado a r. É possı́vel que p2 tenha grau maior que r em Zn [X]. Então, para
acharmos p2 em Zn [X]/(X r − 1), ainda teremos que reduzir p2 módulo X r − 1.
Mas isso quer dizer que teremos que reduzir cada termo X j do polinômio p2 ,
dividindo j por r, quando j ≥ r. Se o grau de p é limitado a r − 1, então
podemos conceder que não teremos j > 2r e não teremos mais que r termos
de grau maior ou igual a r. O custo máximo da divisão de um inteiro limitado a 2r é O((log2 2r)2 ) = O((log2 2 + log2 r)2 ) = O(1 + (log2 r)2 ) = O((log2 r)2 ).
Portanto, o custo total das divisões será O(r(log2 r)2 ). Mas ainda precisamos
somar esses novos termos reduzidos de X, de expoentes menores que r, com
os antigos de mesmo grau, para que o polinômio tenha sua forma usual. Teremos que fazer, no máximo, r somas de coeficientes, limitados a n2 , pois antes
da multiplicação os coeficientes eram limitados a n. Isso terá um custo total de O(rlog2 n2 ) = O(2rlog2 n) = O(rlog2 n). O próximo passo será reduzir
cada um dos, no máximo, r coeficientes módulo n, para que o polinômio p2
fique ajustado no anel Zn [X]/(X r − 1) de forma definitiva. Teremos que fazer, no máximo, r divisões por n de coeficientes limitados a 2n2 , pois antes das
somas dos coeficientes de mesmo grau, os mesmos eram limitados a n2 . Isso
terá um custo de O(r(log2 2n2 )2 ) = O(r(log2 2 + log2 n2 )2 ) = O(r(2log2 n)2 ) =
O(4r(log2 n)2 ) = O(r(log2 n)2 ). Assim, terminamos todos os passos para o cálculo do quadrado de um polinômio p em Zn [X]/(X r − 1). O custo total é
O(r2 (log2 n)2 ) + O(r(log2 r)2 ) + O(rlog2 n) + O(r(log2 n)2 ) = O(r2 (log2 n)2 ). Veja
que a parte mais custosa é a primeira, ou seja, o cálculo de p2 em Zn [X]. Isso
quer dizer que o cálculo de p2 em Zn [X]/(X r − 1) é tão custoso quanto o cálculo
de p2 em Zn [X].
Agora que sabemos quanto custa um quadrado de polinômio no quociente
Zn [X]/(X r −1), podemos calcular o custo total da expansão, que terá, no máximo,
log2 n produtos. Multiplicando, o custo da expansão é O(r2 (log2 n)3 ). Porém, para
concluirmos a verificação da identidade, ainda precisamos reduzir o polinômio do
lado direito, no caso em que este tenha grau maior ou igual a r (quando n ≥ r).
Mas isso requer apenas uma divisão de n por r, com custo O((log2 n)2 ). Por fim,
realizamos a comparação, que pode ser feita em tempo polinomial. Então, o custo
total da verificação da identidade é O(r2 (log2 n)3 ) + O((log2 n)2 ) = O(r2 (log2 n)3 ).
Por enquanto, não estamos preocupados com a escolha desse r. Apenas dizemos
que pode ser qualquer inteiro positivo. Se não houver nenhuma relação entre r e
n, por exemplo, se r for apenas uma constante escolhida, o custo é (O(log2 n)3 ),
devido às propriedades da notação assintótica. Veja que a principal diferença,
com relação à identidade anterior, é que o grau dos quadrados não mais cresce
indefinidamente. Pelo contrário, é limitado a r. Isso quer dizer que, mesmo
que r seja bem maior que n, haverá um limite em que a função passa a crescer
polinomialmente.
Assim, este é um teste polinomial interessante de primalidade, não fosse ele
não-determinı́stico! Senão, vejamos. O anel Zn [X]/(X r −1) é o conjunto de todas
as classes residuais do anel Zn [X] reagrupadas módulo o ideal gerado por X r − 1.
Disto, segue que qualquer igualdade em Zn [X] se mantém em Zn [X]/(X r − 1)
([Coutinho, 2004]). Por isso, a identidade (2.10) se verifica para todos os valores
33
de a e r quando p é primo, seguindo diretamente do Lema 2.3.1.
Por outro lado, existem algumas classes distintas em Zn [X] que passam a
compartilhar o mesmo conjunto de classes após aplicada a relação de equivalência
módulo o ideal (X r − 1). Isso quer dizer que, infelizmente, alguns n compostos
também satisfazem (2.10) para alguns valores de r e a, tornando essa identidade
um teste não-determinı́stico. No entanto, Agrawal, Kayal e Saxena conseguiram
mostrar que é possı́vel escolher um r, de modo que, se a identidade for satisfeita
para um certa quantidade de a’s, n é, ao menos, potência de um primo. Antes de
provarmos o teorema principal que mostra essa propriedade, vamos enunciar três
lemas que estão em [Coutinho, 2004] e serão usados em sua prova.
Lema 2.3.2. Sejam a e k inteiros não negativos e p > 1 um primo. Então,
k
k
(X + a)p = X p + a em Zp [X].
Prova. Mais uma vez, usaremos o Princı́pio da Indução Matemática (ver Apêndice A). Se k = 0, a verificação é imediata. Assim, suponha que
k
k
(X + a)p = X p + a em Zp [X]
para algum k ≥ 0. Se a identidade se verificar para k + 1, então a prova estará
completa. Temos que
(X + a)p
k+1
k
k
= ((X + a)p )p = (X p + a)p ,
(2.11)
sendo que a última igualdade é obtida assumindo-se a hipótese de indução.
Do Lema 2.3.1, segue que
(X + a)p = (X p + a).
Como X é uma variável, a identidade deve valer para qualquer valor de X. Então,
k
trocando X por X p , temos:
k
k+1
(X p + a)p = (X p
+ a).
Logo, disto, e de (2.11),
(X + a)p
k+1
k+1
= (X p
+ a).
Lema 2.3.3. Sejam n, r e a inteiros positivos e p > 1 um primo. Se
(X + a)n = X n + a em Zp [X]/(X r − 1),
então
i
i
(X + a)n = X n + a em Zp [X]/(X r − 1) para qualquer i ≥ 0 ∈ Z.
34
Prova. Novamente, vamos usar a Indução Matemática (ver Apêndice A). Se
i = 0, então o resultado é imediato. Suponha que
i
i
(X + a)n = X n + a em Zp [X]/(X r − 1) para algum i ≥ 0.
Pela hipótese inicial do lema,
(X + a)n = X n + a em Zp [X]/(X r − 1).
Então,
(X + a)n = X n + a + q(X)(X r − 1) para algum q(x) ∈ Zp [X].
i
Substituindo X por X n , temos:
i
i+1
(X n + a)n = X n
i
i
+ a + q(X n )(X n r − 1).
i
Mas, como (X r )n = 1 mod(X r − 1), segue que12
i
i
X n r − 1 = (X r )n − 1 = 1 − 1 = 0 em Zp [X]/(X r − 1).
Destas duas últimas igualdades, temos que
i
(X n + a)n = X n
i+1
+ a em Zp [X]/(X r − 1).
(2.12)
Mas, pela hipótese indutiva,
i+1
(X + a)n
i
i
= ((X + a)n )n = (X n + a)n em Zp [X]/(X r − 1).
(2.13)
Assim, de (2.12) e (2.13), temos:
i+1
(X + a)n
= Xn
i+1
+ a em Zp [X]/(X r − 1),
o que finaliza a prova.
Lema 2.3.4. Sejam n, r e a inteiros positivos e p > 1 um primo. Se
(X + a)n = X n + a em Zp [X]/(X r − 1),
então
i j
i j
(X + a)n p = X n p + a em Zp [X]/(X r − 1) para quaisquer i, j ≥ 0 ∈ Z.
Prova. Da hipótese inicial e do Lema 2.3.3, temos que
i
i
(X + a)n = X n + a em Zp [X]/(X r − 1).
Logo,
i j
i
j
i
j
(X + a)n p = ((X + a)n )p = (X n + a)p em Zp [X]/(X r − 1).
12
Qualquer potência de X múltipla de r deixará resto 1 após a divisão por X r − 1.
35
(2.14)
Como toda igualdade em Zp [X] dá lugar a uma igualdade em Zp [X]/(X r − 1),
i
podemos aplicar o Lema 2.3.2 a (2.14), substituindo o X daquele Lema por X n ,
já que X é variável e pode assumir qualquer valor. Assim, obtemos
i j
i
j
i j
(X + a)n p = (X n + a)p = X n p + a em Zp [X]/(X r − 1),
o que completa a prova.
Agora vamos enunciar o teorema principal envolvido no algoritmo. Seguiremos
os passos que estão em [Coutinho, 2004] e, às vezes, em [Bernstein, 2003]. Tratase de uma versão levemente alterada, com algumas diferenças na notação e em que
tentamos esclarecer melhor alguns pontos, atualizada com a modificação proposta
por Lenstra Jr. ([Coutinho, 2004] e [Agrawal et al., 2004]), a qual melhorou a
eficiência do algoritmo em relação à primeira versão, de 2002.
Teorema 2.3.5. Sejam n ≥ 2 ∈ Z, r um primo positivo, S o conjunto {1, 2, ..., r}
e U (r) o grupo abeliano dos elementos inversı́veis de Zr . Se
i) r - n,
ii) n é relativamente primo a cada um dos elementos de S,
√
2db (r−1/d)c
iii) 2r−2
para qualquer inteiro d que divide (r − 1)/v, onde v
≥
n
r
é a ordem de n em U (r) e
iv) a identidade (X + a)n = X n + a, em Zn [X]/(X r − 1), se verificar para todo
a ∈ S,
então n é potência de primo.
Antes de prosseguirmos com a prova, vamos analisar as informações do enunciado do teorema. Primeiro, como r é primo e não divide n, segue que r e n são
coprimos. Assim, n é inversı́vel em Zr e, portanto, está em U (r). Seja p um primo
positivo que divida n. Então, mdc(r, p) = mdc(r, n) = 1, ou seja, p e r também
são coprimos, e p é inversı́vel em Zr . Seja hn, pi o subgrupo de U (r) gerado
por n e p. Assim, podemos construir o grupo quociente U (r)/hn, pi. Para um
maior esclarecimento, veja o Exemplo B.0.4 do Apêndice B, que também possui
uma apresentação do Teorema de Lagrange, fundamental para o entendimento da
prova que se segue.
Prova. A ordem de U (r) (sua quantidade de elementos), que passamos a denotar
por |U (r)|, é igual a r − 1, pois r é primo e, portanto, relativamente primo a todos
os inteiros positivos menores que r. Então, esses r − 1 inteiros são inversı́veis em
Zr , sendo exatamente os elementos de U (r). Seja d a ordem de U (r)/hn, pi, ou
seja, d = |U (r)/hn, pi|. Como13
|U (r)/hn, pi| =
13
Veja Apêndice B.
36
|U (r)|
,
|hn, pi|
então
d=
|U (r)|
(r − 1)
=
=⇒ |hn, pi| = (r − 1)/d.
|hn, pi|
|hn, pi|
(2.15)
Pelo Teorema de Lagrange (Apêndice B), a ordem v de n em U (r), ou seja, o
menor inteiro v tal que nv = 1, divide a ordem de hn, pi, que, de (2.15), é igual a
(r − 1)/d. Mas se v divide (r − 1)/d, existe algum c inteiro tal que cv = (r − 1)/d.
Assim, cvd = (r − 1). Como a ordem v também divide |U (r)| = (r − 1), podemos
escrever cd = (r − 1)/v. Logo, d divide (r − 1)/v, conforme a hipótese iii do
teorema.
Suponha m1 , m2 , ..., md as d classes do grupo quociente U (r)/hn, pi. Seja h
um fator irredutı́vel de X r − 1 em Zp [X]. Como Zp é um corpo finito, o anel
quociente K = Zp [X]/(h) é um corpo finito. Seja G o subgrupo de K ∗ gerado
pelos elementos X mi + a, onde 1 ≤ i ≤ d e a ∈ S.
Suponha a seguinte cota inferior para a ordem do subgrupo G:
√
|G| ≥ n2b (r−1)/dc .
(2.16)
A prova dessa cota será feita posteriormente, nos moldes de [Coutinho, 2004], e é
devida a um resultado provado por Lenstra Jr. p
([Agrawal et al., 2004]).
Considere os produtos ni pj , para 0 ≤ i, j ≤ b (r − 1)/dc. Como p ≤ n, então
ni pj ≤ ni nj ≤ n2ij . Podemos, assim, reescrever essa desigualdade como:
√
(2.17)
1 ≤ ni pj ≤ n2b (r−1)/dc .
Cada classe ni pj de Zr pertence ao subgrupo hn, pi de U (r), pois esse subgrupo
é formado justamente pela multiplicação de todas as potências14 de n e p em U (r).
Mas, de (2.15), o subgrupo hn, pi tem ordem (r−1)/d e, portanto, não há mais
que (r −1)/d elementos
ni pj em Zr . Como i e j variam
p a partir
pdistintos na forma
2
de 0, há um total de (b (r − 1)/dc+1) pares (i, j), com 0 ≤ i, j ≤ b (r − 1)/dc.
Como isso é maior que (r − 1)/d, as classes ni pj não podem ser todas distintas
em Zr . Desta forma, existem pares
(k1 , l1 ) 6= (k2 , l2 ) tais que nk1 pl1 = nk2 pl2 (mod r).
(2.18)
Sejam u = nk1 pl1 e v = nk2 pl2 . Suponha que v ≥ u. Como u = v (mod r),
então v = u + qr para algum q inteiro positivo. Assim,
X v = X u+qr = X u (X r )q .
Como (X r )q deixa resto 1 após a divisão por (X r − 1), segue que
X v = X u+qr = X u (X r )q = X u · 1 = X u em Zp [X]/(X r − 1).
Mas, como vimos antes,
14
Lembrando que as potências das classes se repetem a partir do expoente igual a sua ordem
em U (r).
37
X v = X u em Zp [X]/(X r − 1)
equivale a
∃ q(X) tal que X v = X u + q(X)(X r − 1) em Zp [X].
(2.19)
Como h(X) | (X r − 1), então
∃ s(X) tal que (X r − 1) = s(X)h(X).
Substituindo isso em (2.19), temos:
∃ q(X) tal que X v = X u + q(X)s(X)h(X) em Zp [X],
o que significa que a congruência se mantém no corpo K, ou seja,
X v = X u em K = Zp [X]/(h).
(2.20)
Porém, da hipótese iv do teorema,
(X + a)n = X n + a em Zn [X]/(X r − 1)
para cada a ∈ S, o que equivale a
∃ t(X) tal que (X + a)n = X n + a + s(X)n (mod X r − 1)
para cada a ∈ S. Da mesma forma que fizemos anteriormente, se p divide n,
então s(X) é múltiplo de p também. Assim,
(X + a)n = X n + a em Zp [X]/(X r − 1)
para cada a ∈ S. Então, pelo Lema 2.3.4,
i j
i j
(X + a)n p = X n p + a em Zp [X]/(X r − 1) para quaisquer i, j ≥ 0 ∈ Z
e para cada a ∈ S. Como qualquer igualdade em Zp [X]/(X r − 1) se mantém em
Zp [X]/(h), segue que
i j
i j
(X + a)n p = X n p + a em Zp [X]/(h) para quaisquer i, j ≥ 0 ∈ Z
e para cada a ∈ S.
Mas esta última igualdade vale para quaisquer que sejam os expoentes i, j
inteiros. Então, podemos escrever:
k1 pl1
= Xn
k2 pl2
= Xn
(X + a)u = (X + a)n
k1 pl1
+ a = X u + a em Zp [X]/(h)
(2.21)
k2 pl2
+ a = X v + a em Zp [X]/(h)
(2.22)
para cada a ∈ S e
(X + a)v = (X + a)n
para cada a ∈ S.
38
De (2.20), (2.21) e (2.22), temos que
(X + a)u = (X + a)v em Zp [X]/(h)
para cada a ∈ S.
Como X é uma variável, podemos substituı́-la por qualquer valor mantendo
a identidade. Vamos substituir X por X mi , em que mi é, como já apresentado
anteriormente, uma das d classes do grupo quociente U (r)/hn, pi (i pode variar
de 1 a d):
(X mi + a)u = (X mi + a)v em Zp [X]/(h)
para cada a ∈ S.
Assim, os produtórios de cada membro da identidade, quando se varia a em
S, devem permanecer iguais. Ou seja,
Y
Y
(X mi + a)u =
(X mi + a)v em K = Zp [X]/(h).
a∈S
a∈S
Como esses produtos geram o subgrupo G de K ∗ , conforme apresentado anteriormente, temos que g v =g u em K para todo g ∈ G. Isso implica que todos os
elementos de G, (e também 0) são soluções da equação polinomial Y v − Y u em
K. Mas (2.17) implica em:
√
(r−1)/dc
√
√
=⇒ 0 ≤ u − 1 ≤ n2b (r−1)/dc =⇒ 0 ≤ u ≤ n2b (r−1)/dc + 1
(r−1)/dc
√
√
=⇒ 0 ≤ v − 1 ≤ n2b (r−1)/dc =⇒ 0 ≤ v ≤ n2b (r−1)/dc + 1.
1 ≤ u ≤ n2b
e
√
1 ≤ v ≤ n2b
Como estamos
√ supondo que v ≥ u, então a diferença (v − u) é no mı́nimo 0 e
2b (r−1)/dc
no máximo n
+ 1, neste último caso, quando u é mı́nimo e v é máximo.
Então, podemos escrever que
√
(v − u) + 1 ≤ n2b (r−1)/dc ,
e, combinando isso com a cota inferior para |G|, em (2.16), temos
|G| ≥ (v − u) + 1.
Mas isso significa que o polinômio Y v −Y u admite mais que (v −u)+1 soluções
em K, considerando a solução nula. Mas esse polinômio não pode admitir mais
que (v − u) + 1 soluções em um corpo se v > u. Para ilustrar esse fato, imagine
v = 2 e u = 1. Neste caso, (v − u) + 1 = 2. Admitir mais soluções que isso seria
admitir pelo menos 3 soluções. Mas o polinômio Y v − Y u = Y 2 − Y admite, no
máximo, 2 soluções num corpo, já que seu grau é 2. Logo, se v ≥ u e v ≯ u, só
resta a opção v = u. Assim,
nk1 pl1 = u = v = nk2 pl2 .
39
Agora vamos analisar esses expoentes. Se k1 = k2, então pl1 = pl2 , do que
segue que l1 = l2 . Mas isso significa que (k1 , l1 ) = (k2 , l2 ), o que é absurdo, pois
admitimos que esses pares eram distintos. Logo, k1 6= k2 . Só que isso significa
que
nk1 −k2 = pl1 −l2 .
Temos que uma potência de n é potência de p. Mas, como as potências de
p só possuem p como fator primo, segue que a potência de n também só pode
possuir p como fator primo. Disto, ou n é p ou é potência de p, como querı́amos
mostrar.
Note que a demonstração do Teorema 2.3.5 depende da prova de que |G| ≥
√
(r−1)/dc
n
]. Como já citamos anteriormente, essa prova se deve a um resultado
obtido por Lenstra Jr. ([Agrawal et al., 2004]). Vamos agora provar essa cota,
seguindo, novamente, os passos de [Coutinho, 2004].
√
Lema 2.3.6. A ordem do subgrupo G é maior ou igual a n2b (r−1)/dc .
2b
Prova. Sejam f1 (X), f2 (X), f3 (X), ..., fj (X) funções fk : S → N, ou seja, funções
que recebem os elementos de S como entrada e nos dão o resultado como um
número natural. Vamos associar cada função fk à d-upla
Dk = (pk (X m1 ), pk (X m2 ), ..., pk (X md )), no corpo K = Zp [X]/(h),
onde pk é o polinômio
pk (X) =
Y
(X + a)fk (a) .
a∈S
Portanto, os elementos de cada Dk são elementos de G, conforme a construção
daquele subgrupo usada na prova do Teorema 2.3.5. Mas esses elementos podem
se repetir em cada d-upla e, além disso, sua ordem importa. Assim, temos permutações, com repetição permitida, de d elementos de G e, da Análise Combinatória,
isso significa que temos
|G|d
(2.23)
d-uplas distintas.
Podemos mostrar, ainda, que determinadas funções distintas sempre serão
associadas a d-uplas distintas. Sejam f1 e f2 . Se as respectivas d-uplas associadas,
D1 e D2 , forem iguais, então
p1 (X mi ) = p2 (X mi ) em K para todo 1 ≤ i ≤ d.
b c
(2.24)
Sejam b e c dois naturais. Desenvolvendo p1 (X mi )n p em Zp [X]/(X r − 1),
temos:
Y
b c
b c
p1 (X mi )n p =
((X mi + a)f1 (a) )n p =
a∈S
40
=
Y
b pc
(X mi + a)f1 (a)n
=
a∈S
Y
((X mi + a)n
b pc
)f1 (a) .
(2.25)
a∈S
Mas, da hipótese iv do Teorema 2.3.5, (X + a)n = X n + a em Zn [X]/(X r − 1)
para todo a ∈ S. Como p divide n, temos também que
(X + a)n = X n + a em Zp [X]/(X r − 1)
para todo a ∈ S. Então, podemos aplicar o Lema 2.3.4 em (2.25), obtendo
b pc
p1 (X mi )n
=
Y
b pc
(X mi n
b pc
+ a)f1 (a) = p1 (X mi n
) em Zp [X]/(X r − 1).
a∈S
E, como h divide X r − 1, essa igualdade também vale em K = Zp [X]/(h). Disto,
e de (2.24), segue que
b pc
p1 (X mi n
) = p2 (X mi n
b pc
) em K, ∀ 1 ≤ i ≤ d.
(2.26)
Façamos g(X) = p1 (X) − p2 (X). Como U (r) possui r − 1 classes distintas dos
elementos inversı́veis módulo r e o quociente U (r)/hn, pi possui d classes distintas,
representadas por m1 , ..., md e geradas pelos elementos de U (r) módulo potências
de n e p, então, para qualquer inteiro 1 ≤ e ≤ r − 1, existem b, c ∈ N tais que
e = mi nb pc (mod r). Mas isso significa que e = mi nb pc + tr para algum t inteiro.
Assim,
b c
b c
g(X e ) = g(X mi n p (X r )t ) = g(X mi n p ) em Zp /(X r − 1),
já que X r = 1 em Zp /(X r − 1). Como h(X) divide o polinômio X r − 1, então
b pc
g(X e ) = g(X mi n
b pc
(X r )t ) = g(X mi n
) em Zp [X]/(h).
Disto, e de (2.26), segue que
g(X e ) = 0 em Zp [X]/(h) = K.
(2.27)
Seja o conjunto R = {X e | 1 ≤ e ≤ r − 1} ⊆ K. Como X r = 1 em K, por ser
primo, r é o primeiro expoente w > 0 de X tal que X w = 1 em K. Portanto, r
é a ordem de X em K ∗ e todos os elementos de R são distintos. Mas, de (2.27),
cada elemento de R é raiz de g(X) em K. Então, por admitir r − 1 raı́zes, g(X)
é um polinômio de, no mı́nimo, grau igual a r − 1 no corpo Zp (X). Assim, se
X
X
f1 (a) < r − 1 e
f2 (a) < r − 1,
(2.28)
a∈S
a∈S
então p1 (X) = p2 (X) em Zp [X]. Mas, da hipótese ii do Teorema 2.3.5, temos
que n é relativamente primo a cada um dos elementos de S. Isso quer dizer que
mdc(n, a − a0 ) = 1 para quaisquer a e a0 distintos no intervalo [1, r]. Disto, segue
que (X + a) − (X + a0 ) = a − a0 6= 0 em Zp [X].
Logo, os polinômios X + a e X + a0 são distintos e irredutı́veis em Zp [X],
para distintos a e a0 de S. Portanto, como a fatoração de polinômios é única,
segue que p1 (X) = p2 (X), considerando a hipótese (2.28), somente se as funções
41
f1 e f2 forem iguais. Assim, o conjunto das d-uplas distintas Dk , de elementos
de G, tem pelo menos tantos elementos quantas são as funções fk para as quais
P
a∈S fk (a) < r − 1. Mas, como essas funções têm o conjunto dos naturais como
contradomı́nio, precisamos saber quantas são as somas de naturais que resultam
num valor menor que r − 1. Somente os naturais até r − 2 podem ser incluı́dos
nestas somas, pois fica claro que uma soma do natural r − 1 com qualquer outro
não é menor que r − 1. Também, a ordem em que esses naturais são somados
não importa. Desta forma, temos uma combinação de r elementos (a ordem
de S, que é o domı́nio das funções) de um total de r − 1 (os naturais de 0 a
r − 2), com repetição permitida. Da Análise Combinatória, isso significa que
temos exatamente
(r − 1) + r − 1
2r − 2
=
r
r
possibilidades. Então, disto, e de (2.23), temos:
2r − 2
d
|G| ≥
.
r
E, da hipótese iii do Teorema 2.3.5, segue que
√
2r − 2
d
|G| ≥
≥ n2db (r−1)/dc
r
e, portanto,
√
|G| ≥ n2b
(r−1)/dc
.
Na subseção seguinte, apresentaremos uma versão modificada do AKS a partir
da versão que está em [Coutinho, 2004], que, por sua vez, é uma variação do que
está em [Bernstein, 2003], a qual formalizaremos no assistente de prova Coq.
42
2.3.2
O Pseudocódigo e a Correção
Algoritmo 2 AKS
Entrada: n > 1 inteiro
{*Número a ser testado*}
Saı́da: primo ou composto
ETAPA 1:
se n é potência de algum k > 1 ∈ Z, com expoente maior que 1, então
imprima composto e pare.
ETAPA 2:
2
calcule N = 2n(n − 1)(n2 − 1)(n3 − 1)...(n4dlog2 ne − 1) e determine o menor
primo r que não divide N .
ETAPA 3:
se n é divisı́vel por algum primo q < r, então
se q = n então
imprima primo e pare
senão
ETAPA 4:
se (X + a)n = X n + a no anel Zn [X]/(X r − 1) para todo a ∈ S = {1, 2, ..., r},
então
imprima primo e pare
senão
Veja que se trata de um algoritmo que possui quatro etapas bem distintas.
A Etapa 4 faz a verificação da identidade (2.10) mas, antes, o algoritmo realiza
algumas operações para atender às propriedades do Teorema 2.3.5. Demonstraremos, agora, a correção do algoritmo, provando que realmente se trata de um
algoritmo determinı́stico.
Teorema 2.3.7. A saı́da do algoritmo AKS é primo se, e somente se, n for
primo.
Prova. =⇒ Se n for primo, o algoritmo deve parar com a resposta primo na
Etapa 3 ou na Etapa 4. Por ser primo, n não pode ser potência de nenhum
inteiro maior que 1. Assim, o algoritmo passará pela Etapa 1. Na Etapa 2, será
determinado o menor r primo que não divide o N calculado. Se o r encontrado
for maior que n, então haverá um primo q menor que r que divide n: o próprio
n, e o algoritmo parará na Etapa 3 com a resposta primo. Caso r não seja maior
que n, então a Etapa 4 será executada. Como n é primo, pelo Lema 2.3.1, temos
que (X + a)n = X n + a em Zn [X]. Como toda igualdade em Zn [X] se mantém em
Zn [X]/(X r − 1), a identidade da Etapa 4 se verificará para quaisquer que sejam
a e r, e o algoritmo retornará primo na saı́da.
⇐= Se n for composto, o algoritmo deve parar com a resposta composto na
Etapa 1, ou na Etapa 2 ou na Etapa 4. Se n for potência, de expoente maior
que 1, de algum inteiro, então o algoritmo parará na Etapa 1 com a resposta
composto. Se o algoritmo chegar à Etapa 2, então n não é potência de inteiro,
43
com expoente maior que 1. Não há parada na Etapa 2, então o algoritmo chegará
à Etapa 3, após ter calculado N e encontrado r. Se houver algum q menor que r
que divida n, então o algoritmo parará na Etapa 3 com a resposta composto. Por
outro lado, se não houver, perceba que, na Etapa 2, N é múltiplo de n e de 2.
Portanto, o primo r encontrado também não divide n e nem 2. Logo, 2 < r 6= n.
Disto, segue que, se o algoritmo passar pela Etapa 3, 2 < r < n.
Assim, considerando n composto, se o algoritmo chegar à Etapa 4, teremos
um r primo que não divide n, conforme hipótese i do Teorema 2.3.5, e teremos que
n não possui divisores menores ou iguais a r, o que implica mdc(n, a) = 1 para
todo a ∈ S = {1, 2, ..., r}, conforme a hipótese ii do Teorema 2.3.5. Se tivermos
como comprovar que a hipótese iii também estará satisfeita, poderemos aplicar
o Teorema 2.3.5 à congruência da Etapa 4. Mas r não divide N . Então, r não
divide nenhum dos fatores (nk − 1), com 1 ≤ k ≤ 4dlog2 ne2 daquele produto.
Disto, segue que
nk 6= 1 (mod r) para todo 1 ≤ k ≤ 4dlog2 ne2 .
Assim, a ordem v de n em U (r), ou seja, o primeiro expoente positivo k que
torna nk = 1 (mod r), tem que ser maior que 4dlog2 ne2 . Lembrando que, pelo
Teorema de Lagrange (ver Apêndice B), a ordem v de n em U (r) divide a ordem
de U (r) = r − 1, suponha um inteiro positivo d que divida (r − 1)/v. Portanto,
d≤
(r − 1)
(r − 1)
(r − 1)
<
≤
,
2
v
4dlog2 ne
4(log2 n)2
(2.29)
já que dlog2 ne representa o menor dos inteiros maiores ou iguais a log2 n.
Por outro lado,
r
r
r
p
(r − 1)
(r − 1)
(r − 1)
c ≤ 2d
= 2 d2 ·
= 2 d(r − 1).
2db
(2.30)
d
d
d
Mas, de (2.29), temos:
s
p
(r − 1)
(r − 1)
(r − 1)(r − 1)
2 d(r − 1) ≤ 2
=2·
=
.
2
4(log2 n)
2(log2 n)
log2 n
Disto, e de (2.30), segue que
r
2db
(r − 1)
(r − 1)
c≤
.
d
log2 n
Então,
√
n
Como
2db
(r−1)/dc
≤ n(r−1)/log2 n =
√
log2 n
n(r−1) = 2r−1 .
n
n!
n(n − 1)(n − 2)...(n − k + 1)
=
=
k
k!(n − k)!
k(k − 1)(k − 2)1
44
(2.31)
para quaisquer n ≥ k ≥ 0 inteiros, temos:
2r − 2
(2r − 2) (2r − 3) (2r − 4)
r−1
r
(r + 1)
=
···
=
r
r
r−1 r−2
r − (r − 3) r − (r − 2) 1
=
r−1
Y
2r − j
j=2
r−j
.
(2.32)
Mas
2r − j
j
=2+
.
r−j
r−j
E como
2+
j
j
> 2, quando 0 < j < r, e 2 +
≥ 3, quando 0 < dr/2e ≤ j,
r−j
r−j
para r ≥ 4, dos r − 2 fatores do produto (2.32), teremos pelo menos br/2c ≥ 2
maiores ou iguais a 3. Os restantes serão maiores ou iguais a 2. Mas o produto de
dois fatores maiores ou iguais a 3 é maior que o produto de três fatores maiores
ou iguais a 2, pois 32 ≥ 23 . Isso quer dizer que, para r ≥ 4, o produto (2.32), de
r − 2 fatores, é maior ou igual ao produto de r − 1 fatores iguais a 2, pois temos,
ao menos, 2 fatores maiores que 2 e o restante igual ou maior que 2. Ou seja,
Y
r−1
2r − 2
2r − j
=
≥ 2r−1
r
r−j
j=2
4
para r ≥ 4. E se r = 3, então 2r−2
= 3 = 4 = 2r−1 . Assim, e de (2.31),
r
Y
r−1
2r − 2
2r − j
≥ 2r−1 ≥
=
r
−
j
r
j=2
√
log2 n
n(r−1) = 2r−1
para r ≥ 3. E, já que necessariamente r > 2 se o algoritmo atinge a Etapa 4,
conforme dito anteriormente, temos que a hipótese iii do Teorema 2.3.5 também
se verifica.
Como todas as hipóteses do Teorema 2.3.5 estão confirmadas na execução da
Etapa 4, podemos aplicá-lo com segurança na identidade daquela etapa. Como n é
composto, a igualdade só poderá se verificar para todo a ∈ S se n for uma potência
de primo. Mas essa condição foi “filtrada” pela Etapa 1. Logo, a identidade da
Etapa 4 não se verificará para algum a ∈ S e o algoritmo parará com a saı́da
composto.
2.3.3
A Complexidade Polinomial
Nesta subseção iremos mostrar que o AKS realmente é um algoritmo de resposta em tempo polinomial. Mas, para que isso seja verdade, cada uma de suas
etapas deve ter custo polinomial. Então, analisaremos etapa por etapa.
45
Custo da Etapa 1
Nessa etapa, será verificado se existe um inteiro a > 1 e um expoente k >
1 tais que ak = n. Existem alguns algoritmos capazes de realizar essa tarefa
em tempo polinomial. Mostraremos uma técnica simples, que consiste em uma
recursão de k após a inversão do expoente em n e após a mudança de base para
2 ([Santos et al., 2002]). Se
ak = n,
então
n1/k = a =⇒ (2log2 n )1/k = a =⇒ 2(log2 n)/k = a.
Assim, podemos fazer uma recursão em k, calculando potências de 2. Se,
em uma dessas recursões, acharmos um inteiro a, então n é potência de a. A
representação de n em logaritmo base 2 é imediata em computação binária e
não representa qualquer custo adicional. Com essa nova representação, podemos
rapidamente verificar que k está limitado a log2 n. De fato, o expoente k é máximo
quando a é mı́nimo ([Coutinho, 2004]), ou seja, 2. Assim, o maior k só pode ser
log2 n. Então, faremos, no máximo, log2 n divisões de números limitados a log2 n.
Portanto, cada divisão terá custo de O((log2 (log2 n))2 ) e o custo total das divisões
será O(log2 n(log2 (log2 n))2 ). Como log2 n < n, podemos fazer uma concessão pela
notação O para simplificar um pouco esse custo, já que nosso objetivo é apenas
mostrar que se trata de um algoritmo polinomial. Então, consideremos que esses
passos nos dão um custo O((log2 n(log2 n)2 ) = O((log2 n)3 ).
Mas, para cada divisão realizada, temos que calcular uma potência de 2. Potências de 2 são multiplicações sucessivas por 2 que, em binário, têm custo constante, pois tratam-se de apenas deslocar um bit para a esquerda. Então, uma
multiplicação por 2 é desprezı́vel para a notação O. No entanto, o expoente das
potências depende do valor n da entrada e, quanto maior, maior será a quantidade
de multiplicações. Precisamos saber, então, quantas multiplicações por 2 iremos
fazer. No pior caso, quando n é potência de 2 e k = log2 n, faremos, justamente,
log2 n multiplicações por 2. Então, podemos concluir nossa estimativa do custo da
primeira etapa como O(log2 n(log2 n)3 ) = O((log2 n)4 ) que, como sabemos, trata-se
de um custo polinomial.
Custo da Etapa 2
Nessa etapa, primeiro vamos analisar o custo do cálculo de N . Para cal2
cular a maior das potências, n4dlog2 ne , são feitas multiplicações entre números
2
limitados a n4dlog2 ne . Uma multiplicação entre números dessa ordem tem custo
2
O((log2 (n4(log2 n) ))2 ) = O((4(log2 n)2 log2 n)2 ) = O((log2 n)6 ). Como são, no máximo, 4dlog2 ne2 multiplicações, então o custo total para o cálculo da maior das
potências é O(4(log2 n)2 (log2 n)6 ) = O((log2 n)8 ). Após o cálculo da potência, há,
ainda, a subtração de uma unidade. O custo da subtração para números até
2
2
n4dlog2 ne é O(log2 (n4(log2 n) )) = O((log2 n)3 ). Assim, o custo total para o cálculo
do maior termo de N é O((log2 n)8 ) + O((log2 n)3 ) = O((log2 n)8 ). Mas ainda
temos que calcular os outros termos, com potências de expoentes menores que
4dlog2 ne2 . Considerando que são, no máximo, 4dlog2 ne2 , o custo total para calcular todos os termos é limitado a O(4(log2 n)2 (log2 n)8 ) = O((log2 n)10 ). Veja que
46
fomos bem generosos com a notação O, pois os expoentes das outras potências
são menores que 4dlog2 ne2 , começando em 1. Além, disso, poderı́amos ter usado
a multiplicação de quadrados, como fizemos na análise do custo da identidade
2
(2.10), para calcular n4dlog2 ne , o que diminuiria o custo de N .
Ainda resta multiplicar todos os termos, inclusive 2n, para o cálculo final
de N . São da ordem de 4dlog2 ne2 multiplicações a um custo de, no máximo,
2
O((log2 (n4(log2 n) ))2 ) = O((4(log2 n)2 log2 n)2 ) = O((log2 n)6 ) cada uma, considerando o valor máximo envolvido nas operações. O custo total das multiplicações
será, então,
O(4(log2 n)2 (log2 n)6 ) = O((log2 n)8 ).
Assim, o custo final para a computação de N será O((log2 n)10 ) + O((log2 n)8 ) =
O((log2 n)10 ), que é polinomial. Mas, nessa etapa, ainda temos que computar o
menor primo r que não divide N .
Temos que
2
2
2n(n − 1)(n2 − 1)...(n4dlog2 ne − 1) ≤ 2n · n · n2 · · · n4dlog2 ne .
Então, como dlog2 ne2 ≤ (log2 n + 1)2 ,
2
N ≤ 2n · n · n2 · · · n4(log2 n+1) = 2n · nj ,
onde
4(log2 n+1)2
j=
X
nk .
k=1
Mas, como o somatório dos c primeiros naturais é c(c + 1)/2, temos:
4(log2 n + 1)2 (4(log2 n + 1)2 + 1)
j=
= 8(log2 n + 1)4 + 2(log2 n + 1)2 .
2
Então,
4
2
N ≤ 2n · n8(log2 n+1) +2(log2 n+1)
4
2
≤ 2n8(log2 n+1) +2(log2 n+1) +1 .
Aplicando logaritmo base 2 em ambos os lados, temos:
log2 N ≤ 1 + (8(log2 n + 1)4 + 2(log2 n + 1)2 + 1)log2 n.
Somando 1 apenas ao lado direito:
log2 N < 2 + (8(log2 n + 1)4 + 2(log2 n + 1)2 + 1)log2 n.
Então, existe um inteiro positivo m tal que
log2 N < m ≤ 2 + (8(log2 n + 1)4 + 2(log2 n + 1)2 + 1)log2 n.
E disto, segue que
4 +2(log n+1)2 +1
2
N < 2m ≤ 4n8(log2 n+1)
47
.
Mas o Corolário 2.2.8 nos garante que o produto de todos os primos positivos
menores ou iguais a 2m2 é maior ou igual a 2m . Então, como N < 2m não pode
ser múltiplo de todos os primos menores ou iguais a 2m2 , r será, no máximo, igual
a 2m2 . Assim, se
m ≤ 2 + (8(log2 n + 1)4 + 2(log2 n + 1)2 + 1)log2 n,
então
r ≤ 2m2 ≤ 2(2 + (8(log2 n + 1)4 + 2(log2 n + 1)2 + 1)log2 n)2 .
Podemos, agora, usar a notação O para estimar r, ou seja, seu crescimento
à medida que n cresce, e simplificar nossos cálculos adiante. Vemos que o maior
grau do polinômio em log2 n da desigualdade acima é 10, pois temos que realizar
a distributiva da multiplicação antes de elevarmos ao quadrado. Então, nossa
estimativa para r é O((log2 n)10 ).
Uma forma simples para encontrar r é testar a divisão de N por cada primo,
a partir de 2, até encontrarmos o primeiro que não divide N . Para isso, podemos
usar o Crivo de Eratóstenes para descobrirmos todos os primos de 2 a r. Na
Subseção 2.2.3, fizemos uma estimativa para o custo do crivo em O(n2 ) e afirmamos realmente se tratar de um teste de primalidade exponencial. Mas como
poderemos usá-lo em uma das etapas do algoritmo AKS se queremos justamente
provar que este se trata de um algoritmo em tempo polinomial? A resposta para
isso é que, apesar de o crivo ter custo exponencial em relação à entrada, não o
aplicaremos diretamente à nossa entrada n e, sim, a r, que tem uma estimativa
polinomial. Assim, teremos um custo de O(r2 ) = O((log2 n)10 )2 ) = O((log2 n)20 ).
Por sua vez, cada divisão de N pelos primos até r terá custo
4
2
O((log2 N )2 ) = O((log2 (2n8(log2 n+1) +2(log2 n+1) +1 ))2 )
= O((8(log2 n + 1)4 + 2(log2 n + 1)2 + 1)log2 2n)2 ) = O((log2 n)10 ).
Como são, no máximo, r divisões15 , então o custo total de todas as divisões será
O((log2 n)10 )(log2 n)10 ) = O((log2 n)20 ).
Desta forma, verificamos que os últimos dois passos superam a computação
do cálculo de N e, assim, são os determinantes para o custo dessa etapa, o qual é
O((log2 n)20 ), portanto, polinomial. É possı́vel usarmos um método mais eficiente
que o Crivo de Eratóstenes para encontrarmos r, desde que não seja probabilı́stico. Caso seja, não teremos a certeza de que o r encontrado realmente é primo,
tornando o AKS probabilı́stico. Além disso, poderı́amos ter usado, para r, a estimativa de Tschebycheff, que está citada na Subseção 2.2.2. Essas duas medidas
poderiam ter diminuı́do, e muito, nossa estimativa de custo da Etapa 2.
Custo da Etapa 3
Um método simples é usar, nessa etapa, o Crivo de Eratóstenes de forma
semelhante ao que fizemos na etapa anterior: achar todos os primos q menores que
r e, à medida que encontramos esses primos, iremos testar se dividem n. Assim,
15
Aqui, fizemos uma concessão muito grande, já que nem todos os inteiros até r são primos.
48
novamente o custo do crivo aplicado a r será O(((log2 n)10 )2 ) = O((log2 n)20 ), que
é polinomial.
Mas também teremos que realizar uma divisão de r para cada q encontrado.
O custo de uma divisão de r por um inteiro menor é
O((log2 r)2 ) = O((log2 (log2 n)10 )2 ) = O((10log2 log2 n)2 ).
Concedendo r divisões, o custo total será O(((log2 n)10 )(10log2 log2 n)2 ), que é
menor que o custo de apenas aplicar o crivo. Então, o custo total dessa etapa está
limitado pelo custo de se aplicar o Crivo de Eratóstenes a r, que é O((log2 n)20 ).
Custo da Etapa 4
Na Etapa 4 iremos verificar a identidade
(X + a)n = X n + a no anel Zn [X]/(X r − 1)
para todo a ∈ S = {1, 2, ..., r}. Já vimos, no inı́cio desta seção, que o custo para
computar a identidade é O(r2 (log2 n)3 ). Naquela ocasião, r ainda não estava em
função de n. Podia ser visto como apenas uma constante, sem influência na notação assintótica. Mas a identidade representava um teste não-determinı́stico de
primalidade, diferente de agora. Com um custo adicional para computar um r
apropriado, e mais alguns ajustes, a identidade passou a ser um teste determinı́stico. Assim, precisamos substituir r por seu custo, calculado quando analisamos
a Etapa 2. Além disso, a identidade será verificada uma vez para cada a ∈ S, ou
seja, r vezes. O custo para essa etapa será, então,
O(r(r2 (log2 n)3 ) = O(r3 (log2 n)3 ) = O((((log2 n)10 )3 )(log2 n)3 ) =
= O(((log2 n)30 )(log2 n)3 ) = O((log2 n)33 ),
que, apesar de alto, representa um custo polinomial.
De todas as etapas, a mais custosa é a Etapa 4. Só por ela, podemos estimar o custo total do algoritmo AKS em O((log2 n)33 ), ou seja, realmente se trata
de um algoritmo em tempo polinomial. Seja b ≈ (log2 n) o número de bits da
entrada. Como vimos na Seção 2.2.3, b é o melhor parâmetro para ser usado
como tamanho da entrada em testes de primalidade. Desta forma, o custo que
estimamos para o algoritmo AKS é O(b33 ), ou seja, de custo limitado superiormente por um polinômio de grau 33 em relação a quantidade de bits da entrada.
Há, todavia, estimativas bem melhores que a nossa para o custo do algoritmo,
já que fizemos várias concessões, entre elas a utilização de métodos não muito
eficazes em algumas etapas. Em [Agrawal et al., 2004], a estimativa é melhor que
((O(log2 n)(15/2)+1 ).
É evidente que, se comparado aos testes determinı́sticos anteriores a ele, o
algoritmo AKS é mais eficiente16 , já que nenhum responde em tempo polinomial.
Mas, se comparado aos testes probabilı́sticos em tempo polinomial mais usados,
o algoritmo AKS possui um custo mais alto devido, principalmente, à Etapa 4.
16
Estamos nos referindo, como fizemos a todo momento neste trabalho, à eficiência temporal,
ou seja, o tempo de resposta em relação ao tamanho da entrada.
49
Por isso, os testes probabilı́sticos de primalidade continuam a ser os mais usados
atualmente ([Coutinho, 2004]). Ainda que se tenha uma resposta absolutamente
correta em tempo polinomial, é preferı́vel uma resposta ainda mais rápida, com
possibilidade de erro desprezı́vel, sem falar em outros critérios, como dificuldades
de implementação e eficiência espacial17 .
De qualquer forma, o AKS resolveu um problema teórico antigo importante,
ao mostrar que a primalidade está na classe P. Isso pode ter aberto um caminho para se entender melhor a primalidade e, também, para se resolverem outros
problemas computacionais semelhantes. Para isso, um correto entendimento do
algoritmo AKS é fundamental, começando pelos passos algébricos mı́nimos envolvidos. Uma forma de ajudar a trilhar esse caminho seria uma formalização do
algoritmo utilizando um assistente de prova. Veremos o que é um assistente de
prova, sobretudo o Coq, no capı́tulo seguinte.
17
A eficiência espacial se refere ao crescimento do uso da memória em relação ao tamanho da
entrada e pode ser crucial para a eficiência total de um algoritmo ([Cormen et al., 2001]).
50
Capı́tulo 3
Assistentes de Prova
3.1
Verificação Formal e Assistentes de Prova
Há algumas décadas, havia a idéia de que os computadores poderiam substituir os matemáticos, podendo provar teoremas sozinhos. Até os dias atuais,
no entanto, os computadores mostraram-se limitados nessa tarefa e tal idéia foi
abandonada ([Friedman, 2006]). De fato, os resultados de indecidibilidade deixam
claro que um tal nı́vel de automatização é impossı́vel. No entanto, computadores
vêm sendo utilizados com bastante sucesso na construção de provas, por meio de
um processo semi-automático em que o usuário direciona os caminhos a serem
seguidos pelo computador.
A verificação formal de software e hardware torna-se importante devido à utilização destes em um número cada vez maior de atividades humanas, que vão
desde matrı́culas em disciplinas da universidade até transações bancárias e gerenciamento de tráfego aéreo. Desta forma, a verificação formal das teorias matemáticas, utilizadas diretamente ou indiretamente por tais sistemas, é fundamental,
de forma que a verificação matemática e a verificação de programas cada vez mais
se tornam relacionadas e próximas.
Apesar de haver um consenso de que nem tudo na Matemática pode ser formalizado, em [Friedman, 2006] temos alguns motivos importantes para se continuar
a formalização e verificação de teorias matemáticas, além do que indicamos acima:
• Benefı́cios para o estudo da Teoria de Prova, da lógica matemática. Há
a idéia de que a estrutura das provas pode trazer mais benefı́cios do que
a prova em si. Por exemplo, teoremas distintos podem ter uma mesma
estrutura de prova que guarda algo em comum entre eles. Isso pode vir
a ser utilizado para classificar as provas de acordo com sua formalização.
No caso especı́fico do algoritmo AKS, uma formalização pode revelar passos
algébricos e classes de teoremas que podem estar relacionados com teoremas
usados nos demais testes de primalidade ou em outros campos. Isso pode
ajudar no desenvolvimento de novos teoremas e testes de primalidade mais
eficientes.
• A certeza: como uma reivindicação filosófica dos fundamentos da Matemática, temos que saber se algo está ou não está realmente provado, encerrando
51
disputas acerca disso, ainda que em uma situação mais rara. Um exemplo
pode estar no chamado Último Teorema de Fermat. Por volta de 1637,
Fermat anunciou que possuı́a uma prova “maravilhosa” de que a equação
X n + Y n = Z n não possui soluções inteiras não nulas para quando n > 2,
mas que a margem do livro era “muito estreita para escrevê-la”. Esse teorema ficou sem demonstração por séculos, após tentativas fracassadas de
vários matemáticos. Até que em 1994, Wiles anunciou uma demonstração.
Mas a prova continha um erro. Foram necessários mais alguns meses para
Wiles corrigir a prova e ela ser aceita ([López-Ortiz, 1997]). Essa prova
pode ainda conter um erro? Apesar do consenso de que Fermat não possuı́a
a prova, podemos ter certeza disso? Uma formalização da prova do Último
Teorema de Fermat pode ajudar a responder essas perguntas. É proposto
como um dos 100 teoremas importantes da matemática para serem formalizados em [Wiedijk, 2008].
• Alguns matemáticos não dão importância à formalização matemática por
saberem que nem toda a Matemática pode ser formalizada. Mas cada vez
mais coisas são formalizadas, de forma que não há um limite claro para o
que pode e o que não pode ser formalizado. Se esse processo continuar,
poderemos sensibilizá-los, atraindo ainda mais contribuidores.
• Contribuir para a verificação formal de software e sistemas computacionais,
diminuindo a probabilidade de erros. Por exemplo, em 2002, uma pesquisa
do NIST (National Institute of Standards and Technology) estimou que erros
de software acarretam prejuı́zos em torno de 59 bilhões de dólares por ano à
economia dos Estados Unidos [Research Triangle Institute, 2002]. A situação é semelhante ao considerarmos a indústria de hardware, que freqüentemente faz recalls de seus produtos. O caso mais famoso desses recalls ocorreu
em 1994, quando processadores da Intel apresentaram erros de divisão de
ponto flutuante. Erros como esses podem ser diminuı́dos se o processo de
verificação de software e hardware for melhorado. No caso especı́fico do
AKS, uma formalização pode ajudar a aprimorar a verificação de softwares
geradores de chaves criptográficas, portanto, diretamente ligados à segurança de dados. Além disso, pode permitir a extração de código já validado
para ser usado por esses programas.
As ferramentas utilizadas em verificação formal são conhecidas como assistentes de prova. Como exemplos de assistentes de prova, podemos citar o Coq
([The Coq Development Team, 2008b]), o PVS ([SRI International, 2008]), o Isabelle/HOL ([Paulson and Nipkow, 2008]), entre outros. Os assistentes podem ser
divididos em duas partes fundamentais ([Barendregt and Geuvers, 2001]):
1. Um verificador de prova (proof checker), o qual segue noções, definições,
axiomas e provas formalizados numa dada linguagem lógica. As definições
são verificadas pela sua boa formação e as provas, por sua correção. Tudo
isso seguindo a semântica e a sintaxe da lógica escolhida.
2. Um sistema de desenvolvimento de provas, o qual disponibiliza às pessoas
um meio interativo e mais fácil de realizar sua prova.
52
Atualmente, os assistentes de prova estão bem desenvolvidos devido à quantidade de pessoas que já trabalharam com eles desde a década 1960. Muitos
teoremas matemáticos foram e continuam sendo verificados formalmente com a
utilização desses softwares. O processo de verificação formal pode ser dividido em
3 partes:
1. Especificação da teoria: nesse momento, o usuário precisa descrever os termos utilizados na teoria, como os tipos de dados.
2. Especificação das propriedades a serem provadas (teoremas, lemas, etc).
3. Construção das provas dessas propriedades. Nessa etapa, o usuário conduz
o assistente na construção da prova.
Alguns assistentes de prova podem, inclusive, gerar, como saı́da, o objeto de
prova, um arquivo que contém a prova em código de baixo nı́vel. Neste caso, o
objeto de prova pode ser checado por outro verificador de prova independente
([Friedman, 2006]). O conceito de objeto de prova está relacionado com o conhecido isomorfismo de Curry-Howard, que relaciona programas de computador com
provas matemáticas. Essa correspondência pode ser facilmente compreendida no
contexto do λ-cálculo simplesmente tipado ([Barendregt, 1992]), que nos permite
utilizar programação na construção de provas e lógica na construção de programas. Por exemplo, suponha que nossa tarefa seja construir uma prova para a
seguinte afirmação:
(P → Q) → (Q → R) → P → R,
(3.1)
onde P , Q e R são objetos proposicionais quaisquer. Uma prova de (3.1) consiste
em construir um λ-termo t que tenha (3.1) como tipo, isto é, t : (P → Q) →
(Q → R) → P → R. Pode-se verificar que o λ-termo
λx:P →Qy:Q→Rz:P .y(xz)
(3.2)
é solução de (3.1). Esse termo expressa como construir uma prova de R a partir
de provas arbitrárias de P → Q, Q → R e P , respectivamente a saber, x, y e z.
Uma questão que surge naturalmente neste contexto é: mas como podemos
confiar em um assistente de prova se, ele mesmo, também é um programa que
pode conter erros? Uma forma de responder a essa pergunta está em um critério, conhecido como Critério de de Brujin: “um assistente de provas satisfaz
o Critério de de Brujin se ele gera (de alguma forma) um objeto de prova que
pode ser checado por um algoritmo fácil ” ([Barendregt and Geuvers, 2001]). Ser
checado por um algoritmo “fácil” quer dizer que pode ser checado por um verificador de prova realmente pequeno e que possua um código facilmente verificável
(manualmente). Para o exemplo acima, isso consistiria em fornecer o objeto de
prova (3.2) e a afirmação (3.1) para o verificador de prova constatar que, de fato,
t : (P → Q) → (Q → R) → P → R.
Apesar de nunca podermos ter a certeza absoluta, já que sempre haverá a
(mesmo que remota) possibilidade de algum tipo de falha eletrônica que permita
a aceitação de uma prova falsa, seguindo esse critério, conseguimos a mais alta
53
confiabilidade que uma prova pode ter ([Barendregt and Geuvers, 2001]), pois
todo o processo passa a depender de uma pequena prova verificada por humanos.
Mas, e no caso dos assistentes de prova que não nos fornecem o objeto de prova?
Neste caso, há duas classes, os que podem ter traduzido o script de prova que será
usado por seu próprio verificador interno para um objeto de prova não padrão e os
que não possuem, ainda, qualquer possibilidade de produzir objetos de prova. As
pessoas que utilizam provas feitas nesta última classe precisam confiar no sistema
utilizado.
Em geral, os assistentes de prova têm os seguintes princı́pios ([Friedman, 2006]):
• O usuário determina o refinamento de objetivos e hipóteses, de acordo com a
estrutura de dedução natural. Isso está de acordo com a organização lógica
geral das provas matemáticas atuais.
• O usuário cita definições e teoremas já existentes nas bibliotecas do assistente. Uma apropriada construção de bibliotecas é importante devido ao
suporte ao reuso. Qualquer nova prova construı́da poderá ser introduzida
nas bibliotecas para futuro reuso.
• Também é crucial que o assistente de provas seja capaz de fazer inferências
relativamente triviais por si só. Caso contrário, a experiência mostra que o
processo demandaria muito tempo.
Formalmente, temos a seguinte notação ([Barendregt and Geuvers, 2001]) para
uma prova:
Γ `L p : A
que significa que a partir de um conjunto Γ de hipóteses podemos obter A, por
meio de uma lógica L. O termo p representa a prova formal, que, em geral, é
construı́da aos poucos com a ajuda de táticas que produzem um script da prova,
como veremos na seção a seguir.
3.2
O Assistente de Prova Coq
Como citamos na introdução, o Coq é um assistente de prova baseado em
uma lógica de ordem superior, conhecida como cálculo de construções indutivas, que é uma variação do λ-cálculo tipado ([Bertot and Castéran, 2004]). Portanto, utiliza uma teoria de tipos muito expressiva, onde, pelo isomorfismo de
Curry-Howard, os tipos são vistos como proposições e os termos como provas
[Barendregt and Geuvers, 2001].
A linguagem de especificação usada é chamada Gallina e é com ela que se
definem expressões matemáticas e se realizam as provas. Já a linguagem de comando é chamada Vernacular. É com ela que indicamos o que iremos fazer,
seja iniciar uma definição, iniciar um lema, começar a prova de um lema etc
([The Coq Development Team, 2008c]).
O Coq possui um conjunto relativamente extenso de provas nas bibliotecas nativas ([The Coq Development Team, 2008f]), além de contribuições de pesquisadores e professores de várias instituições ([The Coq Development Team, 2008g]),
54
tudo sob licença GNU LGPL. Isso permite uma interação entre o desenvolvimento
de provas e é importante para o reuso ([Friedman, 2006]). A versão que utilizaremos é a 8.1pl3, disponı́vel em [The Coq Development Team, 2008a]. Assim,
sempre estaremos nos referindo a essa versão em particular.
3.2.1
Tipos
Todas as expressões em Coq possuem um tipo. Se combinarmos expressões,
utilizando ou não certos conectivos, para gerar novas expressões bem formadas,
estas também terão algum tipo. Por exemplo, declaremos a variável b do tipo
nat:
Variable b:nat.
Podemos agora utilizar a constante 2 do tipo nat para escrever a expressão 2b,
que também será do tipo nat. Por outro lado, se utilizarmos a constante true,
do tipo bool, ao escrever a expressão true b, haverá um erro, pois não é uma
expressão bem formada ([Bertot and Castéran, 2004]).
Inicialmente, ao carregarmos o Coq, temos alguns tipos básicos como nat e
bool. O tipo de um tipo é chamado de sort. O Coq possui 3 sorts pré-definidos:
• Prop, para as expressões proposicionais (expressões que podem ser avaliadas
como falsas ou verdadeiras, de acordo com sua carga semântica).
• Set, para descrever tipos de dados e especificações. Os termos cujo tipo é
uma especificação são chamados de programas.
• Type, que são utilizados na construção dos universos que estão relacionados
à consistência do sistema de tipos. Os identificadores Prop e Set possuem
tipo Type, que por sua vez possui tipo Type.
A partir desses três sorts (que também são tipos, já que termos e tipos pertencem à mesma classe no cálculo de construções indutivas), podemos construir todos
os demais tipos que precisarmos. Mas seria muito trabalhoso começarmos apenas
com esses tipos para provarmos expressões matemáticas. Justamente tendo em
vista o suporte ao reuso, existem os tipos nat, bool, e mais tantos outros que podem ser carregados ao chamarmos as bibliotecas apropriadas (Z, para os inteiros,
Q, para os racionais etc).
Há um certo paralelismo entre a teoria de tipos e a teoria de conjuntos
([Barendregt and Geuvers, 2001]). Por exemplo, podemos considerar que elementos de um mesmo tipo pertencem a um mesmo conjunto, o conjunto de todos os
elementos com aquele tipo. Vejamos como é construı́do o tipo nat, que representa
o conjunto dos números naturais. Podemos fazer isso no Coq com o comando:
Print nat.
A resposta, então, será:
Inductive nat : Set := O : nat | S : nat -> nat
For S: Argument scope is [nat scope]
55
Isso quer dizer que o tipo nat é do tipo Set (como esperávamos), construı́do
de forma indutiva, com o uso de dois construtores, O, do tipo nat e S, do tipo
nat->nat.
O construtor O é do tipo nat. O construtor S requer uma entrada nat para
dar uma saı́da nat (nat->nat), ou seja, é uma função unária. Assim, S O será
do tipo nat. Então, também podemos escrever S (S O), S (S (S O)) etc. Se
O é o zero e S é a função sucessor, podemos representar todos os naturais dessa
forma. O é o natural 0, S O é o natural 1 (sucessor de 0), S (S O) é 2 etc. E a
correspondência de notação é feita no escopo nat scope. Os comandos Check 5
e Check S (S (S (S (S O)))) geram a mesma saı́da:
5
:
nat.
Por outro lado, se usarmos o comando Unset Printing Notations, estaremos descarregando as notações do escopo e, agora, ao usarmos o comando Check
5, obteremos a saı́da:
S (S (S (S (S O))))
: nat.
3.2.2
Táticas
No Coq, as provas e as especificações permanecem no mesmo arquivo. Após
enunciada a especificação, abre-se o campo de provas e podemos começar a aplicar
as táticas. Isso é feito de forma interativa. Cada tática é um comando que,
inclusive, pode ser desfeito. Existe uma ferramenta gráfica, chamada CoqIDE
([The Coq Development Team, 2008a]), que auxilia no processo de construção das
provas. Também é possı́vel utilizar outras ferramentas de interação, como o Proof
General e o Pcoq ([The Coq Development Team, 2008e]).
Podemos enunciar um lema da seguinte forma:
Lemma dois mais dois:
2+2=4.
Isso significa que queremos provar 2+2=4. O identificador dois mais dois é
utilizado para referências futuras.
Ao iniciarmos a prova, aparecerá o seguinte:
1 subgoal
-----------------------------(1/1)
2 + 2 = 4
Abaixo da linha pontilhada temos 1 objetivo a ser provado. Acima da linha são
colocadas as hipóteses (inexistentes no nosso exemplo). Devido ao isomorfismo de
Curry-Howard, uma prova em Coq nada mais é do que um termo t da linguagem
do cálculo de construções indutivas que possui como tipo o que se está afirmando,
56
no caso 2+2=4. De uma forma geral, a construção de um tal termo não é nada
trivial. O Coq possui, então, várias táticas que nos permitem construir pouco a
pouco esse termo, ou seja, uma prova de 2+2=4. Vamos começar com a tática
simpl.
Agora, o campo de prova será
1 subgoal
-----------------------------(1/1)
4 = 4
A tática simpl é uma tática de redução que procura simplificar o termo de
prova. Neste caso, ela realizou a soma 2+2. Agora, a prova é trivial, pois 4=4.
Podemos usar a tática trivial, que é capaz de identificar igualdades triviais.
trivial.
E obtemos no campo de provas Proof completed, o que mostra que chegamos
ao fim da prova. Ainda precisamos pedir para o Coq guardar nossa prova, com
o nome que escolhemos no inı́cio do comando Lemma, para podermos utilizá-lo
futuramente. Só assim sairemos do campo de provas. O comando é
Qed.
O Coq nos dá a saı́da:
simpl in |- *.
trivial.
dois mais dois is defined
E isso significa que dois mais dois foi definido utilizando a tática simpl seguida
de trivial. O termo que possui tipo 2+2=4 pode ser visto com o comando Print:
Print dois mais dois.
refl equal 4
: 4 = 4
Na verdade, esta é uma prova muito simples e trivial. Poderı́amos ter simplesmente usado a tática auto, que realiza uma busca completa por definições e
provas nas bibliotecas carregadas para tentar provar o objetivo, já que, quando
inicialmente carregado, o Coq importa parte da biblioteca Arith, que possui,
além do tipo nat e do escopo nat scope, provas envolvendo o tipo nat.
Vejamos uma outra prova, lembrando que, por ser baseado em uma lógica de
ordem superior, podemos usar quantificadores em predicados:
Proposition tauto ou:
forall A:Prop, A-> (A ∨ ∼A).
57
Internamente, os comandos Proposition, Lemma, Theorem, entre outros, representam a mesma coisa. A diferenciação pode ser útil para uma melhor organização das provas ([The Coq Development Team, 2008c]). Estamos dizendo que,
para toda proposição A, A implica em A ou na negação de A. Teremos o seguinte
no campo de prova:
1 subgoal
-----------------------------(1/1)
forall A : Prop, A -> A ∨ ∼A
Comecemos com a tática intro, que introduz hipóteses no campo de hipóteses
a partir do termo de prova.
intro A.
Então, teremos:
1 subgoal
A : Prop
-----------------------------(1/1)
A -> A ∨ ∼A
Ou seja, introduzimos a hipótese A no nosso campo de hipóteses a partir do
que estava no campo de provas. O que temos agora é, seja A qualquer proposição.
Então, A implica em A ou na negação de A. É justamente essa a idéia do quantificador universal. O que fizemos foi aplicar a regra de introdução do quantificador
universal. Ainda podemos fazer a introdução da implicação, já que a implicação
pressupõe, como hipótese, o antecedente1 . Assim, façamos
intro H.
Como saı́da, teremos:
1 subgoal
A : Prop
H : A
-----------------------------(1/1)
A ∨ ∼A
Isso significa: seja A uma proposição; se tivermos uma prova de A (neste caso H),
então podemos provar A ou a negação de A. Poderı́amos ter feito as duas táticas
intro de uma única vez com a tática intros A H. Ou simplesmente, intros.
Neste caso, o Coq faz todas as introduções de hipóteses possı́veis nomeando-as
seguindo um algoritmo interno.
1
Se tivermos o antecedente, teremos o conseqüente.
58
Assim, reduzimos todo o nosso termo de prova inicial a apenas uma disjunção.
Para provar a disjunção, basta provar o seu lado esquerdo ou o direito. Mas nós
temos o lado esquerdo como hipótese. Ou seja, temos uma prova de A, a saber, H.
Podemos usar a tática left, que diz que provaremos o lado esquerdo da disjunção.
left.
Agora, temos:
1 subgoal
A : Prop
H : A
-----------------------------(1/1)
A
Bom, mas como temos A como a hipótese H, basta dizermos isso ao Coq com
a tática exact H, ou pedirmos para ele procurar no banco de hipóteses com a
tática
assumption.
E isso completa a prova.
Essa prova também é bem simples. Se trata de uma tautologia. O Coq
pode resolver tautologias com a tática tauto. Bastaria essa única tática para
provarmos nossa proposição. Novamente, a tática auto também resolveria por
ser mais abrangente que tauto. De fato, tauto tenta resolver apenas as tautologias, caso não consiga, dará um erro informando a falha. Já auto tentará
vários recursos, inclusive tauto, mas não dará erro se falhar. Apenas deixará
as coisas como estão. Por causa disso, a tática auto pode levar mais tempo
para resolver um objetivo, o que, às vezes, torna melhor usar outras no lugar
([The Coq Development Team, 2008c]).
É claro que nem todas as provas são fáceis de serem realizadas assim. Seria
bom se bastasse digitar auto e esperar o Coq resolver tudo. Vejamos uma prova
um pouco mais complexa (mas nem tanto) envolvendo inteiros, que necessitará da
biblioteca ZArith e de uma de suas provas. Assim, primeiro pedimos para o Coq
carregar a biblioteca ZArith que, entre outras coisas, possui o tipo Z definido:
Require Import ZArith.
Agora, o comando Print Z irá mostrar:
Inductive Z : Set := Z0 : Z | Zpos : positive -> Z
| Zneg : positive -> Z
For Zpos: Argument scope is [positive scope]
For Zneg: Argument scope is [positive scope]
59
Ou seja, o tipo Z é formado por três construtores. Z0, Zpos e Zneg. Sem entrar
muito em detalhes, um representa 0, outro, os positivos e o último, os negativos.
Vamos, agora, iniciar o seguinte lema:
Lemma exemplo apply:
forall n:Z, (n<=0)%Z ∨ (3*n-1>n)%Z.
No campo de prova, teremos o seguinte:
1 subgoal
-----------------------------(1/1)
forall n : Z, (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
O sinal %Z usado significa que tudo que está entre parêntesis deve ser considerado com relação ao tipo Z. A biblioteca ZArith, ao ser carregada, não muda o
escopo. Se escrevêssemos apenas forall n : Z, (n <= 0) ∨ (3 * n - 1 >
n), o Coq consideraria ainda o escopo dos naturais: a constante 3 seria vista como
nat, a multiplicação interpretada como entre tipos nat e as comparações também.
Assim, terı́amos uma expressão mal formada, já que n é tipo Z, e o Coq geraria
um erro. Algumas bibliotecas adicionais a ZArith, como Znumtheory, alteram
o escopo, de forma que terı́amos o contrário: se trabalharmos com o tipo nat,
teremos que indicar %nat. De qualquer forma, tanto a notação quanto o escopo
podem ser mudados a qualquer instante, inclusive no meio da prova, tornando o
Coq muito flexı́vel.
O nosso lema exemplo apply diz que, para qualquer n inteiro, então n ≤ 0
ou 3n − 1 > n. De fato, sempre que n ≤ 0, temos 3n − 1 < n. Podemos usar
a tática intros para preencher nosso campo de hipóteses e diminuir o termo de
prova. Assim, teremos:
1 subgoal
n : Z
-----------------------------(1/1)
(n <= 0)%Z ∨ (3 * n - 1 > n)%Z
Olhando as provas da biblioteca ZArith, existe uma que pode nos ajudar. É
o teorema chamado Ztrichotomy. Esse teorema está carregado, pois faz parte
de ZArith. Podemos verificá-lo com o comando Check Ztrichotomy, que nos
fornece:
Ztrichotomy
: forall n m :
Z, (n < m)%Z ∨ n = m ∨ (n > m)%Z
O tipo de Ztrichotomy é uma fórmula com dois quantificadores universais.
Corresponde a uma prova de que para quaisquer 2 inteiros, ou eles são iguais, ou
um é maior que o outro. Podemos, então, usar a tática:
elim Ztrichotomy with n 0%Z.
60
A tática elim é a mais simples ([The Coq Development Team, 2008c]) das
táticas indutivas. Ztrichotomy representa uma disjunção a partir de quaisquer
2 inteiros. Neste caso, o comportamento de elim será o de eliminar a disjunção,
desde que indiquemos de quais inteiros estamos falando, por isso usamos o with.
Mas eliminar uma disjunção do campo de hipóteses é mostrar que qualquer um
dos lados da disjunção nos leva ao objetivo. Uma prova, como Ztrichotomy, pode
ser invocada a qualquer momento como se estivesse realmente entre as hipóteses.
Assim, teremos:
2 subgoals
n : Z
-----------------------------(1/2)
(n < 0)%Z -> (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
-----------------------------(2/2)
n = 0%Z ∨ (n > 0)%Z -> (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
Perceba que a disjunção (n < 0) ∨ n = 0 ∨ (n > 0) é vista, pelo Coq,
como (n < 0) ∨ (n = 0 ∨ (n > 0)), ou seja, um disjunção entre dois membros. Por isso, agora temos que provar apenas 2 sub-objetivos, e não 3.
O sub-objetivo atual é o (1/2). Todas as táticas que usarmos serão aplicadas
a ele. Se quisermos mudar o foco de prova para o segundo sub-objetivo, podemos
usar o comando Focus 2. Mas, como isso não é necessário, continuemos com
o primeiro sub-objetivo, que se trata de uma implicação. Podemos, então, usar
novamente a tática intros e teremos:
2 subgoals
n : Z
H : (n < 0)%Z
-----------------------------(1/2)
(n <= 0)%Z ∨ (3 * n - 1 > n)%Z
-----------------------------(2/2)
n = 0%Z ∨ (n > 0)%Z -> (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
A nova hipótese H pertence apenas ao contexto do primeiro sub-objetivo, o
qual se trata de uma disjunção. Então, basta que provemos apenas um de seus
lados. Como H é suficiente para provar o lado esquerdo, usaremos a tática left:
2 subgoals
n : Z
H : (n < 0)%Z
-----------------------------(1/2)
(n <= 0)%Z
-----------------------------(2/2)
n = 0%Z ∨ (n > 0)%Z -> (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
61
Se temos uma prova de n < 0, então sabemos que n é menor ou igual a 0.
Será que não há uma prova dessa propriedade? Sim, a biblioteca ZArith possui o
lema Zlt le weak, que é uma prova para forall n m :Z, (n < m)%Z -> (n
<= m)%Z. Observe que o conseqüente dessa implicação se encaixa exatamente
no nosso sub-objetivo. Então, podemos usar a tática apply Zlt le weak, e
obtemos:
2 subgoals
n : Z
H : (n < 0)%Z
-----------------------------(1/2)
(n < 0)%Z
-----------------------------(2/2)
n = 0%Z ∨ (n > 0)%Z -> (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
Veja que agora não precisamos provar n ≤ 0. Mas precisamos provar n < 0,
que é justamente o que diz o lema Zlt le weak: para uma prova de n ≤ 0, basta
uma de n < 0.
Agora, como temos a hipótese H a nosso favor, a tática assumption é suficiente
para completar o primeiro sub-objetivo, restando apenas o segundo:
1 subgoal
n : Z
-----------------------------(1/1)
n = 0%Z ∨ (n > 0)%Z -> (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
Note que a hipótese H foi apagada do contexto, pois era parte do primeiro
sub-objetivo. Após usarmos novamente a tática intros, teremos:
1 subgoal
n : Z
H : n = 0%Z ∨ (n > 0)%Z
-----------------------------(1/1)
(n <= 0)%Z ∨ (3 * n - 1 > n)%Z
Como a hipótese H é uma disjunção, podemos usar a tática elim H, o que
exigirá que provemos dois sub-objetivos:
2 subgoals
n : Z
H : n = 0%Z ∨ (n > 0)%Z
-----------------------------(1/2)
n = 0%Z -> (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
62
-----------------------------(2/2)
(n > 0)%Z -> (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
Agora, podemos usar intros novamente, e teremos:
2 subgoals
n : Z
H : n = 0%Z ∨ (n > 0)%Z
H0 : n = 0%Z
-----------------------------(1/2)
(n <= 0)%Z ∨ (3 * n - 1 > n)%Z
-----------------------------(2/2)
(n > 0)%Z -> (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
Poderı́amos proceder como fizemos antes, usando left e depois procurarmos
uma prova de que n = 0 implica em n ≤ 0 para aplicá-la2 . Mas a biblioteca
ZArith possui um novo conjunto de regras, Hint, para a tática auto seguir.
Basta usarmos a tática auto with zarith e a tática auto será executa com seu
comportamento padrão mais as novas regras definidas no Hint zarith. Desta
forma, o Coq consegue verificar que a hipótese H0 satisfaz o sub-objetivo. E
teremos:
1 subgoal
n : Z
H : n = 0%Z ∨ (n > 0)%Z
-----------------------------(1/1)
(n > 0)%Z -> (n <= 0)%Z ∨ (3 * n - 1 > n)%Z
No passo anterior, não era necessário a tática intros. Bastava a tática auto
with zarith diretamente. Podemos fazer isso agora e a prova estará completa.
Esta prova poderia ser terminada apenas com as táticas:
intros.
elim Ztrichotomy with n 0%Z; auto with zarith.
intros.
elim H; auto with zarith.
Qed.
O ponto-e-vı́rgula após as táticas elim significa que auto with zarith será
aplicado a todos os novos sub-objetivos gerados. No primeiro caso, o primeiro
sub-objetivo (aquele que utilizamos a prova Zlt le weak) será automaticamente
provado. Mas ainda teremos o segundo. Mas no segundo caso, o auto with
zarith conseguirá provar os dois sub-objetivos gerados após a eliminação de H.
2
E há! É o lema chamado Zeq le.
63
Agora, vejamos uma prova simples, mas não trivial, que parece ser fundamental para especificarmos a primeira etapa do algoritmo AKS. Vamos provar
formalmente que, para todo n inteiro positivo e todo m natural não nulo, n|nm :
Lemma n div pow n:
(Zpower nat n m)).
forall (n:Z) (m:nat), n>0 ->
(gt m 0) -> (n |
Antes de prosseguirmos, vamos explicar a notação. Neste momento, precisamos das bibliotecas ZArith e Zpower carregadas. Esta última altera o escopo
para Z. A relação > (maior que) será considerada entre tipos Z, pois a notação
foi alterada. O nosso Lema n div pow n requer que o nat m seja maior que 0.
Podemos fazer de duas maneiras: ou escrevemos (m>0)%nat, como fizemos nas
outras provas com Z, ou esquecemos a notação e usamos diretamente o predicado
binário gt (greater than), que compara dois termos nat. Print gt nos mostra:
gt = fun n m :
nat => (m < n)%nat :
nat -> nat -> Prop.
Assim, gt a b é verdadeiro se a>b (a e b do tipo nat). A sı́mbolo >, por
sua vez, agora está vinculado ao predicado Zgt, que faz o mesmo que gt, porém,
envolvendo tipos Z. Além disso, a biblioteca Zpower tem duas especificações para
potência. A função binária Zpower, que retorna, como tipo Z, o valor de um inteiro
elevado a outro inteiro, e a função binária Zpower nat, que retorna, também
como tipo Z, o valor de um inteiro elevado a um natural. O sı́mbolo ^ é vinculado
a Zpower (a ^ b = Zpower a b, para a e b do tipo Z). Mas, como queremos
considerar expoentes do tipo nat, usaremos diretamente a função Zpower nat.
Poderı́amos, também, criar um novo sı́mbolo de notação. Por exemplo:
Infix "**":= Zpower nat.
Isso faria com que o Coq passasse a reconhecer a**b como Zpower nat a b.
Voltando à nossa formalização, após introduzir o comando Lemma acima, teremos o seguinte no campo de prova:
1 subgoal
-----------------------------(1/1)
forall (n : Z) (m : nat), n > 0 -> (m > 0)%nat -> (n | Zpower nat
n m)
Usamos a tática intros e passamos a ter:
1 subgoal
n : Z
m : nat
H : n > 0
H0 : (m > 0)%nat
-----------------------------(1/1)
(n | Zpower nat n m)
64
Agora, usemos a seguinte tática:
replace (Zpower nat n m) with (n*(Zpower nat n (m-1))).
Passaremos a ter, no campo de prova:
2 subgoals
n : Z
m : nat
H : n > 0
H0 : (m > 0)%nat
-----------------------------(1/2)
(n | n * Zpower nat n (m - 1))
-----------------------------(2/2)
n * Zpower nat n (m - 1) = Zpower nat n m
A tática replace A with B procura a expressão A e a substitui pela expressão
B, desde que tenham o mesmo tipo. Além disso, gera um sub-objetivo para que
se valide a substituição. O nosso primeiro sub-objetivo é relativamente trivial
ao Coq, que pode verificar automaticamente que n inteiro divide um múltiplo de
n devido a algumas provas de ZArith, desde que n6= 0. Como temos n>0 como
hipótese, podemos, então, usar a tática auto with zarith:
1 subgoal
n : Z
m : nat
H : n > 0
H0 : (m > 0)%nat
-----------------------------(1/2)
n * Zpower nat n (m - 1) = Zpower nat n m
Devemos, ao final, provar que nossa substituição foi válida. Há uma prova de
que Zpower nat n m = n*(Zpower nat n (m - 1)), chamada n exp minus 1,
desenvolvida para o nosso projeto. Essa prova apenas requer n>0 e m>0. Porém, o
nosso o objetivo possui as expressões invertidas em relação a nossa prova. Temos,
então, que usar a tática symmetry, que implementa a simetria na relação de
igualdade. Assim, após a tática, teremos:
1 subgoal
n : Z
m : nat
H : n > 0
H0 : (m > 0)%nat
-----------------------------(1/2)
Zpower nat n m=n*(Zpower nat n (m -1))
65
Agora, podemos usar nossa outra prova. Como ela exigirá n>0 e m>0 e já
temos essas exigências como hipóteses, a usaremos aliada à tática assunption, o
que completa prova:
apply n exp minus 1; assumption.
Como podemos ver, há diversas formas de se realizar uma prova. Além disso,
existem diversas outras táticas. E mais: o usuário pode criar suas próprias táticas.
Isso é particularmente útil nos casos em que se usa várias vezes as mesmas táticas
seguidas. Pode-se, então, criar uma tática que faça o trabalho das táticas de uma
só vez.
Além disso, cabe ressaltar que o Coq possui o recurso de assumir a prova como
válida antes de terminá-la, para que continuemos a trabalhar com outras provas.
A prova passa a ser vista como um axioma. Isso é particularmente útil se tivermos
dependendo de uma prova auxiliar. Por exemplo, suponha que queiramos provar
A→E
e sabemos que essa prova, feita diretamente, é longa e trabalhosa, pois requer o uso
extensivo de táticas, tornando-a, inclusive, pouco legı́vel. Mas, ao examinarmos
a estrutura de E, vemos que é possı́vel construirmos uma prova de
D → E.
Além disso, procurando nas bibliotecas nativas, descobrimos que há uma prova
de
A→B
e, com um pouco mais de pesquisa, encontramos, nas contribuições de terceiros,
uma prova de
B→C
que, pela estrutura de C, nos faz imaginar que é possı́vel provar
C → D.
Assim, podemos montar uma possı́vel forma para nossa prova inicial, que será
A → B → C → D → E,
deixando, por enquanto, as provas D → E e C → D como axiomas.
Como, inicialmente, achamos possı́vel provar D → E, começamos por trabalhar nessa prova, enquanto somente a prova C → D fica assumida como axioma.
Ao final, poderemos até não completar a prova, mas temos uma possı́vel forma
para ela, mais organizada e mais legı́vel do que uma prova feita de uma vez só.
Aliás, se não conseguirmos provar uma prova extensa, feita de uma única vez,
o que faremos com o trabalho incompleto realizado? No caso da prova dividida
em provas auxiliares, mais pessoas trabalhando nos axiomas restantes poderão
66
completar a prova. Além disso, as provas intermediárias poderão ser úteis em
trabalhos futuros, desempenhando papel fundamental de suporte ao reuso.
67
Capı́tulo 4
Metodologia
A idéia é construir, inicialmente, uma especificação geral para o AKS e uma
prova de que sua saı́da é sempre correta. A partir desse objetivo, começaremos
a especificar os teoremas e as propriedades envolvidos em cada etapa do algoritmo como provas auxiliares que, temporariamente, serão iniciados como axiomas. Essas provas auxiliares também poderão, à medida em que forem sendo
desenvolvidas, ser divididas em provas ainda menores.
O trabalho desenvolvido dessa forma traz os benefı́cios apontados no final
da Seção 3.2. Assim, necessitaremos, também, de uma boa pesquisa nas bibliotecas nativas ([The Coq Development Team, 2008f]) e nas contribuições de terceiros
([The Coq Development Team, 2008g] e [INRIA, 2008]) à procura de provas que
possamos reutilizar em nosso projeto. Mas, muitas vezes, nos depararemos com
especificações que não foram construı́das de forma a atenderem particularmente
nosso problema. Neste caso, poderemos adaptá-las ou construir provas novas.
Esperamos, ao final, conseguir provar todos os axiomas intermediários.
Assim, começaremos com a especificação da seguinte fórmula:
φ(n) = n > 1∧¬(Pot n)∧rNdiv r(N n)∧((qDiv r n∧q = n)∨(¬(qDiv r n)∧IdAKS n)),
onde Pot, rNdiv, qDiv e IdAKS são fórmulas e N é uma função unária que iremos
especificar como:
Pot n = ∃m∃e(m > 1 ∧ e > 1 ∧ n = me );
rNdiv r n = Primo r ∧ r - n ∧ ∀s(Primo s → s - n → s ≥ r);
qDiv r n = ∃q(q < r ∧ Primo q ∧ q | n);
IdAKS n = ∀a(a ∈ {1, 2, ..., r} → (X + a)n = X n + a) em Zn [X]/(X r − 1);
2
N n = 2n(n − 1)(n2 − 1)(n3 − 1)...(n4dlog2 ne − 1).
Primo é um predicado que significa “é primo positivo”. Além disso, para não
sobrecarregar a notação, estamos considerando que todos os termos numéricos
acima estão em Z. Assim, a fórmula φ pode ser entendida como “n é inteiro
68
maior que 1, n não é potência de inteiro maior que 1 com expoente maior que 1,
r é o menor primo positivo que não divide N e, ou existe um primo positivo q
menor que r que divide n e q = n, ou não existe primo positivo q menor que r que
divide n e a congruência (X + a)n = X n + a no anel Zn [X]/(X r − 1) se verifica
para todo a em {1, 2, ..., r}”.
Além disso, teremos que provar nossa especificação com um teorema semelhante a
∀p(p ∈ Z → p > 1 → (p é primo ↔ φ(p)),
ou seja, um inteiro positivo p é primo se, e somente se, φ(p) é verdadeira.
Os predicados envolvidos em φ correspondem às etapas do AKS. Assim, ao
especificarmos aqueles predicados, estaremos especificando cada uma das etapas
do algoritmo. Mas, para isso, precisaremos, ainda, realizar algumas provas de
teoremas envolvidos em cada etapa. Por exemplo, se n é potência de inteiro
maior que 1 com expoente maior que 1, não pode ser primo. Uma prova como
essa será fundamental para a primeira etapa pois, se Pot n for verdadeiro, então
a fórmula φ será falsa.
Seguiremos, assim, uma estrutura de dependência como a mostrada na Figura
4.1.
AKS
Etapa 1
Etapa 3
Etapa 2
Etapa 4
Provas
Auxiliares
Provas das
bibliotecas nativas
Figura 4.1: Dependências que serão seguidas na formalização do AKS.
As provas auxiliares serão agrupadas em arquivos auxiliares. O arquivo principal só conterá as provas principais, que serão as formalizações das etapas e a
formalização final.
Após uma pesquisa em ([The Coq Development Team, 2008f]), decidimos que
a principal biblioteca do Coq que iremos usar é a ZArith, mais algumas de suas
auxiliares, como Znumtheory e Zpower. Essas bibliotecas possuem inúmeros lemas
e propriedades provados com respeito à Teoria dos Números, inclusive envolvendo
69
primalidade. A biblioteca Reals, inicialmente, pareceu muito interessante devido
à quantidade de especificações que possui, como, por exemplo, o teorema binomial,
e possibilidade de trabalhar com inteiros também (de fato, qualquer inteiro é
real). Mas, ao pesquisarmos um pouco mais, vimos de que se trata de uma
biblioteca fortemente fundamentada em axiomas, o que não ocorre com ZArith,
que possui apenas provas concluı́das. Assim, o tipo principal usado será o tipo Z.
A versão do Coq que utilizaremos será a 8.1pl3, aliada à interface gráfica CoqIDE
([The Coq Development Team, 2008b]).
70
Capı́tulo 5
Resultados
Construı́mos 3 arquivos de provas próprias, chamados AKS.v, aux AKS.v e
FermatGen.v. Além disso, há 1 arquivo de provas alteradas dos projetos “Correctness of RSA algorithm” ([Almeida and Thery, 1999]) e “Library for floating point
numbers” ([Thery and Boldo, 2001]), chamado de aux Sophia mod.v, e mais 11
arquivos de provas originais: Aux.v, Fermat.v, Iterator.v, Permutation.v, Tatic.v, Ulist.v, ZdivExp.v, Zfact.v, ZisMod.v, Zprod.v e Zprogession.v, do
projeto “Numbers equal to the sum of two square numbers” ([Thery, 2004]).
Nossas provas precisaram de muitas outras provas auxiliares que puderam
ser encontradas nas bibliotecas nativas ou nos projetos acima citados, disponı́veis
como contribuições ao Coq. Mas, dos 11 arquivos de provas originais de “Numbers
equal to the sum of two square numbers”, dois são de vital importância: Aux.v,
que possui muitas provas elementares, e tornou-se um ótimo complemento para
as provas nativas de ZArith, e Fermat.v, que traz uma única prova: a do Pequeno Teorema de Fermat (Teorema 2.2.2). Dos outros 9, apenas algumas poucas
provas de ZisMod.v e ZdivExp.v são utilizadas diretamente. No entanto, devido
à dependência criada para os arquivos ZisMod.v, ZdivExp.v, precisamos manter,
ao menos, os outros 7 arquivos do projeto original. Assim, esses arquivos podem
ser vistos como uma biblioteca extra. De fato, tentamos colocar todo o conteúdo
dos 11 arquivos num único, mas houve problemas de dependência. Como são
muitas, seria um esforço extra entender toda a dependência existente entre as
provas. Assim, preferimos deixar esses arquivos intactos por enquanto, havendo
a possibilidade de sintetizá-los no futuro.
Já o arquivo aux Sophia mod.v possui 17 provas e 2 definições modificadas
por nós para que atendessem nosso projeto. Em sua maioria, essas provas tratavam do tipo nat, e nós precisávamos que tratassem do tipo Z. Assim, agora
possuı́mos provas para somas iteradas, para o Teorema Binomial, entre outras,
que utilizam o tipo Z.
Mesmo com todas essas provas, os 3 arquivos totalmente criados por nós ainda
possuem 44 provas e 13 definições que são usadas na nossa especificação do AKS,
perfazendo, aproximadamente, 1000 linhas, excluindo os comentários. Há, ainda,
algumas provas não concluı́das que estão comentadas e outras que estão concluı́das, mas não utilizadas na especificação do AKS. Disponibilizamos todo o
material do projeto na Internet em [de Moura and Peixoto, 2008], para que possa
ser verificado.
71
Apenas uma das provas principais ainda não foi concluı́da. Trata-se da prova
congr AKS step 2, do arquivo AKS.v. Essa prova corresponde à volta da congruência (2.10) e foi deixada como axioma para que pudéssemos concluir a prova
geral.
Entre as provas importantes concluı́das que utilizamos, podemos citar:
• A forma usual para o Pequeno Teorema de Fermat (Corolário 2.2.3), que
chamamos fermat little def, do arquivo aux AKS.v, e que, por sua vez,
depende da prova do Pequeno Teorema de Fermat, que está no arquivo
Fermat.v, citado anteriormente.
• A ida do Teorema 2.3.1, que chamamos de gen lit fermat step 1, no
arquivo FermatGen.v, e que depende de fermat little def. Essa prova
é fundamental para a prova congr AKS step 1, também concluı́da, do arquivo AKS.v e que corresponde à ida da congruência (2.10).
• A prova de que, para todo inteiro positivo n, há um menor primo positivo
r que não divide n, que chamamos ex min r, no arquivo AKS.v.
• A existência de infinitos números primos (Teorema 2.2.5), que chamamos
inf prime, do arquivo aux AKS.v. Essa prova aparece em [Wiedijk, 2008]
como um dos 100 teoremas matemáticos importantes a serem formalizados e
que já teria sido provada em Coq por O’Connor, mas não estaria disponı́vel
nas contribuições. Não pudemos achar mais qualquer referência à prova
de O’Connor e, então, tivemos que desenvolver a nossa própria, pois era
fundamental para a prova ex min r.
As provas principais do AKS estão no arquivo AKS.v. São provas e definições
que representam as etapas do algoritmo, bem como a especificação final. A Figura
5.1 mostra a relação de dependência para as provas principais. Assim, tratase de uma relação geral de dependências, em que aparecem apenas as provas
diretamente utilizadas nas provas principais. Não vemos as dependências entre
as provas menores, até porque o diagrama ficaria enorme.
72
73
Legenda
power_not_prime
p_pow_Valid
Provas terminadas
Prova não terminada
Etapa 4 parte I
Zis_gcd_1
Zis_gcd_sym
Zabs_pos
Zabs_intro
Zdivide_trans
prime_dec
Zis_gcd_intro
prime_rel_prime
Zle_lt_or_eq
Zabs_eq_case
Zdivide_le
prime_le_2
not_prime_prime_divide
not_prime_prime_divide_gen
N_valid1
q_not_div_Valid1
Etapa 3
AKS_Valid
Zdivide_opp_l_rev
Ztrichotomy
Zis_mod_def_inv
Zis_mod_def
gen_lit_fermat_step_1
Congr_AKS_step_1
Figura 5.1: Dependências finais na formalização do algoritmo AKS.
Provas do arquivo AKS.v
Provas do arquivo aux.AKS,v
Provas do arquivo Aux.v
Provas do arquivo ZisMod.v
Provas do arquivo aux_Sophia_mod.v
Prova do arquivo FermaGen,v
Provas da biblioteca Arith
Provas da biblitoeca ZArith
le_S_gt
Etapa 2
inj_le_inv
max_ndiv_lt
ex_prime_p_ndiv_n
min_prime_ndiv
Z_of_nat_Zabs_nat
Zlt_0_ind
le_lt_or_eq
prime_le_2
prime_ndiv_le_ex_ndiv
prime_ndiv_Valid2
prime_ndiv_Valid1
ex_min_r
Etapa 1
Etapa 4 parte II
Zmult_1_r
Zle_or_lt
prime_divisors
prime_le_2
Congr_AKS_step_2
Provas de apoio
A Figura 5.2 mostra as codificações, em Coq, de nossa especificação e de nossa
prova do algoritmo AKS, que se encontram no arquivo AKS.v. Logo após, incluı́mos as descrições de nossas principais provas, as quais foram geradas pela ferramenta coqdoc ([The Coq Development Team, 2008d], Part IV, Practical Tools),
que tem a caracterı́stica de gerar documentação mais legı́vel, tanto em HTML
como em LATEX, a partir de arquivos fonte Coq. Além disso, com a utilização de
algumas macros, podemos inserir comentários mais apropriados entre o código.
Cabe também ressaltar que o código LATEX gerado ainda foi parcialmente alterado
por nós.
Figura 5.2: Especificação final do AKS e a prova de sua correção em Coq.
74
Prova gen lit fermat step 1, correspondente à ida do Teorema 2.3.1
Se n é primo, então (X + a)n = X n + a (mod n). Os polinômios serão
representados como expressões do tipo inteiro, mas com a variável X quantificada
universalmente. Usaremos binomiais e o Pequeno Teorema de Fermat para a
prova.
Lemma gen lit fermat step 1 : ∀ a n x :Z, a>0 → prime n →
Zis mod ((x +a)ˆn) (x ˆn +a) n.
Prova.
intros.
Se n é primo, então é maior ou igual a 2.
generalize H0 ; intros; apply prime le 2 in H0.
Como a prova da expansão binomial utiliza expoente natural, incluı́mos uma
premissa de que o módulo natural de n é maior que 1.
assert (gt (Zabs nat n) 1).
elim Zabs nat lt with 1 n; auto with zarith.
Definição de Zis mod: os dois primeiros termos geram o mesmo resto quando
divididos pelo terceiro. Zis mod ((x + a)n )(xn + a)n → ((x + a)n ) mod n =
(xn + a) mod n.
apply Zis mod def ; auto with zarith.
Reescrever expoentes como naturais.
repeat rewrite ← Zpower Zpower nat; auto with zarith.
Expansão binomial: soma iterada de coeficientes binomiais.
rewrite exp Pascal.
Separamos os termos inicial e final do somatório, que permanece somente com os
termos intermediários, que devem ser nulos modulo n.
rewrite sum nm fi inv ; auto with zarith.
Simplificamos, pois
n
0
=1e
n
n
= 1, (binomial def1 e binomial def3).
rewrite binomial def1.
replace (plus 1 (pred (Zabs nat n))) with (Zabs nat n); auto with zarith.
75
rewrite binomial def3.
Simplificar expressões. Teremos que provar depois.
replace (1*(x **(Zabs nat n-Zabs nat n)* a ** Zabs nat n)) with (aˆn).
replace (1*(x **(Zabs nat n-0)* a ** 0)) with (x ˆn).
rewrite Zmod plus eq; auto with zarith.
replace ((sum nm (pred (pred (Zabs nat n))) 1 (fun k : nat ⇒
binomial (Zabs nat n) k × (x ** (Zabs nat n - k ) × a ** k )) + aˆn) mod
n) with
((sum nm (pred (pred (Zabs nat n))) 1 (fun k : nat ⇒
binomial (Zabs nat n) k × (x ** (Zabs nat n - k ) × a ** k )) mod n +
aˆn mod n) mod n).
assert (sum nm (pred (pred (Zabs nat n))) 1 (fun k : nat ⇒
binomial (Zabs nat n) k × (x ** (Zabs nat n - k ) × a ** k )) mod n = 0).
replace (pred (pred (Zabs nat n))) with (Zabs nat n - 2)%nat; auto with zarith.
apply inv sum nm.
intros.
rewrite H3 ; rewrite H4 ; auto with zarith.
intros.
rewrite Zmod mult; auto with zarith.
O núcleo da prova:
n
k
mod n = 0, com 0 < k < n e n primo.
rewrite bin mod n prime; auto with zarith.
apply inj le in H3.
rewrite inj minus1 in H3 ; auto with zarith.
rewrite Z of nat Zabs nat in H3 ; auto with zarith.
simpl in H3.
rewrite inj plus.
replace (Z of nat 1) with 1; auto with zarith.
rewrite H3.
simpl.
rewrite ← Zmod plus eq; auto with zarith.
Ajuste final, com o Pequeno Teorema de Fermat: (X n + an ) = (X n + a) mod n
quando n é primo.
rewrite fermat little def ; auto with zarith.
Provas finais, remanescentes dos passos anteriores.
rewrite
rewrite
rewrite
rewrite
Zpower Zpower nat; auto with zarith.
Zmod plus eq; auto with zarith.
Zmod mod ; auto with zarith.
← Zmod plus eq; auto with zarith.
76
rewrite Zplus comm; auto with zarith.
symmetry.
rewrite ← Zpower Zpower nat; auto with zarith.
replace (a**0) with 1; auto with zarith.
rewrite Zmult 1 r ; rewrite Zmult 1 l ; auto with zarith.
rewrite Zmult 1 l.
replace (minus (Zabs nat n) (Zabs nat n)) with 0%nat; auto with zarith.
replace (x **0) with 1; auto with zarith.
rewrite Zpower Zpower nat; auto with zarith.
Qed.
Prova congr AKS step 1, correspondente à ida da identidade 2.10
Ao chegar à Etapa 4, o algoritmo AKS verifica a congruência (X +a)n = X n +a
(mod X r −1, n) para todo a entre 1 e r. Como estamos tratando o polinômio X r −1
como expressão de tipo inteiro, com a variável X quantificada universalmente,
temos que descartar a possibilidade de ser igual 0.
Definition congr AKS (n r :Z ): Prop:=
∀ x a: Z, (x ˆr -1) 6= 0 → 1≤a≤r →
Zis mod (((x +a)ˆn) mod n) (((x ˆn)+a) mod n) (x ˆr -1).
Se n é primo, então congr AKS se verifica para qualquer a.
Lemma congr AKS step 1 : ∀ n r : Z, prime n → congr AKS n r.
Prova
unfold congr AKS.
intros.
generalize H ; intros; apply prime le 2 in H.
Incluı́mos a assertiva de que (X + a)n = X n + a (mod n), pois temos essa prova
para quando n é primo.
assert (Zis mod ((x + a)ˆn) (x ˆn + a) n).
apply gen lit fermat step 1 ; auto with zarith.
apply Zis mod def inv in H3 ; auto with zarith.
Já que xr − 1 6= 0, temos apenas dois casos a considerar.
assert ((x ˆr -1) < 0 ∨ (x ˆr -1) > 0).
elim Ztrichotomy with (x ˆr -1) 0; auto with zarith.
elim H4.
77
Caso X r − 1 < 0, tratamos o sinal e depois substituı́mos a assertiva (X + a)n =
X n + a (mod n).
intros.
unfold Zis mod.
apply Zdivide opp l rev.
rewrite H3 ; auto with zarith.
Caso X r − 1 > 0, apenas substituı́mos a assertiva (X + a)n = X n + a(mod n).
intros.
Qed.
Especificação e prova final do AKS
AKS (n) é verdadeiro se, e somente se, n é inteiro maior que 1, n não é potência
de inteiro positivo maior que 1 e de expoente maior que 1, e, sendo r o menor
primo positivo que não divide N (n), ou há um primo positivo q menor que r que
divide n e é igual a n, ou não existe primo positivo menor que r que divide n e a
congruência (X − a)n = (X n − a) (mod X r − 1, n) se verifica para todo 1 ≤ a ≤ r.
Definition AKS (n: Z ): Prop:=
n>1 ∧ ¬p pow n ∧ (∃ r :Z, min r r (N n) ∧ (q div eq r n ∨ (q not div r n
∧ congr AKS n r ))).
p é um inteiro primo positivo se, e somente se, AKS (p) for verdadeiro.
Theorem AKS Valid : ∀ p:Z, prime p ↔ AKS p.
Prova
intros.
Iniciamos decompondo a bi-implicação.
unfold iff.
Ida: se p é um inteiro primo positivo, então AKS (p) é verdadeiro.
split; intros.
AKS (p) = p > 1 ∧ ¬(p pow n) ∧ (∃r:Z, (min r r (N n) ∧ (q div eq r n ∨
(q not div r n ∧ congr AKS n)))).
78
unfold AKS.
Se p é primo, então p > 1.
split; generalize H ; intros; apply prime le 2 in H ; auto with zarith.
Se p é primo, temos um prova de que p não é potência.
split.
red ; intros; apply p pow Valid in H1 ; auto with zarith.
Para todo inteiro positivo n, existe um menor primo positivo que não divide n.
Seja r o menor primo que não divide o positivo N (p). Provaremos depois que N
(p) realmente é positivo.
elim ex min r with (N p).
intros r H1 ; ∃ r ; split; auto with zarith.
Mas r ≤ p ou p < r.
elim Zle or lt with r p.
Supondo r ≤ p,
intros.
como p é primo positivo, não pode haver primo positivo q que divida p, pois os
únicos divisores de p são −p, p, 1 e −1.
right; split; unfold q not div ; intros.
red ; intros; apply prime divisors in H5 ; apply prime le 2 in H4 ; auto with
zarith.
A cong AKS (p r) = (X + a)p = X p + a (mod X r − 1, p) para todo a em
{1, 2, 3, ..., r}.
Mas, como p é primo, sabemos que a identidade irá valer para quaisquer valores
de r e a, como conseqüência da identidade (X + a)p = X p + a (mod p).
apply congr AKS step 1 ; auto with zarith.
Agora, suponha p < r.
intros.
Neste caso, há um primo menor que r que divide p: o próprio p.
79
left; unfold q div eq; ∃ p; auto with zarith.
Tudo isso foi baseado no fato de que N (p) seria positivo.
Então, segue a prova.
unfold N ; auto with zarith.
Volta: se AKS (p) é verdadeiro, então p é um inteiro primo positivo.
AKS (p) = p > 1 ∧ ¬(p pow n) ∧ (∃r:Z, (min r r (N n) ∧ (q div eq r n ∨
(q not div r n ∧ congr AKS n)))).
unfold AKS in H ; intuition.
Há dois casos a considerar: suponha que há um primo x menor que r que divide
n e é igual a n.
elim H2 ; clear H2 ; intros r H1 ; intuition.
elim H1 ; clear H1 ; intros; intuition.
Logo, se x = p e x é primo, então p é primo.
rewrite H6 in H1 ; auto with zarith.
Por outro lado, se não existe primo menor que r que divide n e a congruência for
verificada para todo 1 ≤ a ≤ r, então p é potência de primo positivo, desde que
todo 1 ≤ a ≤ r seja relativamente primo a p. Supondo esta última propriedade:
apply congr AKS step 2 in H4 ; auto with zarith.
Mas se p não é potência, pois passou pela Etapa 1, então o expoente não deve ser
maior que 1.
elim H4 ; clear H4 ; intros;
assert (∼x0 >1)%nat.
Prova por absurdo: se o expoente é maior que 1, então p é potência, contrariando
o que temos.
red ; intros; assert (p pow p); unfold p pow.
∃ x ; split; apply prime le 2 in H1 ; auto with zarith; ∃ x0 ; split; auto with zarith.
80
Absurdo.
auto with zarith.
Portanto, se o expoente é maior que 0 e não é maior que 1, sobra o caso de ser
igual a 1.
assert (x0 =1)%nat; auto with zarith.
Logo, p = x1 , mas, como x é primo, p tem que ser primo.
rewrite H7 in H5.
unfold Zpower nat in H5 ; unfold iter nat in H5.
rewrite Zmult 1 r in H5.
Fizemos isso baseados no fato de todo 1 ≤ a ≤ r ser relativamente primo a p.
Como não há primo positivo menor que r que divida p, e r também não divide p,
segue imediatamente a prova.
intros.
apply q not div Valid1 with p r a in H3 ; auto with zarith.
Qed.
81
Conclusão
Neste trabalho, apresentamos uma prova formal da correção do algoritmo AKS
feita em Coq. A prova ainda não está completa, pois falta a formalização da álgebra necessária à prova congr AKS step 2, que corresponde à volta da identidade
(2.10). Mas, além de termos formalizado uma prova geral para o AKS, terminamos uma das partes fundamentais do algoritmo, a prova congr AKS step 1,
que corresponde à ida da identidade (2.10). Além disso, as Etapas 1, 2 e 3 estão totalmente formalizadas. Portanto, provamos, formalmente, que o algoritmo
AKS responde corretamente quando recebe um primo como entrada, e estamos
a caminho da formalização completa da correção do algoritmo, o que pode ser
realizado por qualquer pessoa interessada no assunto e que queira contribuir com
o projeto.
Como provas auxiliares, temos, ainda, a formalização da ida do Lema 2.3.1, a
prova do Corolário 2.2.3, uma prova da existência de infinitos números primos, a
prova da existência, para um inteiro positivo n, do menor primo positivo que não
divide n, além da formalização de outras estruturas algébricas menores importantes ao algoritmo, que podem ser úteis a projetos futuros, incluindo software
certificado.
Esperamos ter construı́do, também, um texto que sirva tanto de referência ao
bom entendimento do algoritmo AKS, explicando, em uma linguagem mais clara
para o estudante de graduação, as suas caracterı́sticas e os principais teoremas
relacionados, como uma pequena introdução ao uso do assistente de prova Coq,
assunto com pouquı́ssimas referências em lı́ngua portuguesa.
Ressaltamos, ainda, que todas as provas desenvolvidas para este projeto serão
disponibilizadas sob licença GNU LGPL, para que possam ser reutilizadas em
outros projetos.
82
Capı́tulo 6
Alguns trabalhos
Artigos
• [Agrawal et al., 2004] - A versão final do artigo PRIMES is in P, em que o
algoritmo AKS é apresentado com a alteração proposta por Lenstra Jr..
• [Bernstein, 2003] - Trabalho ainda não publicado, de Daniel Bernstein, especialista em criptografia de dados. É um dos mais referenciados quando o
assunto é o algoritmo AKS, pois possui explicação e prova bem elegantes e
completas, mas sem explicar os fundamentos algébricos menores.
• [Bernstein, 2004] - Nesse trabalho, Bernstein apresenta um algoritmo probabilı́stico que certifica a primalidade de um número e que utiliza a idéia
do algoritmo AKS.
• [Crandall and Papadopoulos, 2003] - Uma discussão sobre uma possı́vel implementação do algoritmo AKS, referenciado em muitos trabalhos quando
se tem essa preocupação especı́fica.
• [Agrawal and Biswas, 2003] - A idéia central do AKS surgiu desse artigo,
em que o Lema 2.3.1 aparece pela primeira vez, como base para um teste
probabilı́stico de primalidade.
• [Barendregt and Geuvers, 2001] - Uma introdução ao uso de assistentes de
prova, com foco na utilização da teoria de tipos para formalizar propriedades
matemáticas.
Livros
• [Coutinho, 2004] - Pensando em explicar o algoritmo AKS, bem como todos
os fundamentos algébricos relacionados, Coutinho publicou esse livro que,
em grande parte, foi base para nosso trabalho. Sua única falha do livro,
segundo o próprio autor, é não possuir uma implementação do algoritmo.
• [Ribenboim, 2004] - Uma grande referência, citada em vários trabalhos
quando o assunto se trata dos números primos. Ribenboim nos apresenta
83
tudo que se possa pensar sobre os primos, de uma forma descontraı́da e até
bem humorada.
• [Cormen et al., 2001] - Um bom livro para estudantes que queiram compreender melhor a complexidade de algoritmos, que está diretamente ligada à
importância do algoritmo AKS.
• [Bertot and Castéran, 2004] - Primeiro livro sobre o assistente de prova Coq
e sua teoria do cálculo de construções indutivas. Importante para uma boa
compreensão do assistente, que inclui exemplos de estrutura, bem como sua
explicação formal.
• [Friedman, 2006] - A verificação matemática e sua importância são tratadas
neste trabalho, que as defende com argumentos lógicos e de forma apaixonada.
84
Apêndice A
Princı́pio da Indução Matemática
O Princı́pio da Indução Matemática, também conhecido como Princı́pio da
Indução Finita, é uma ferramenta útil para demonstrar propriedades e teoremas
que envolvem os números inteiros.
Teorema A.0.1 (Princı́pio da Indução Matemática). Seja P (n) uma sentença aberta no conjunto {n ≥ n0 | n, n0 ∈ Z} tal que:
(i) P (n0 ) é verdadeira;
(ii) para todo n ≥ n0 , P (n) é verdadeira implica que P (n + 1) é verdadeira.
Então, P (n) é verdadeira para todo n ≥ n0 .
Prova. Seja S = {n ∈ Z | n ≥ n0 e P (n) é falsa}. De acordo com o teorema,
o conjunto S é vazio. Vamos supor, por absurdo, que S 6= ∅. Neste caso, S é
um conjunto de inteiros limitado inferiormente por algum b ≥ n0 . De (i), n0 ∈
/ S,
logo b > n0 . Então, (b − 1) ≥ n0 . Como b é o menor elemento de S, sabemos que
(b − 1) ∈
/ S. Portanto, P (b − 1) é verdadeira. Logo, de (ii), P (b) é verdadeira.
Assim, b ∈
/ S, o que é uma contradição à nossa hipótese.
Para utilizarmos o Princı́pio da Indução Matemática na demonstração de alguma proposição que envolva números inteiros, temos que checar a propriedade
(i), chamada base de indução, e a propriedade (ii), chamada passo indutivo.
Exemplo A.0.2.
12 + 22 + 32 + 42 + ... + n2 =
n3 n2 n
+
+ .
3
2
6
Prova. Vamos dividir a prova em duas partes:
(i) Base de indução
Podemos verificar que a equação (A.1) é válida para n = 1:
12 =
13 12 1
+
+ = 1.
3
2
6
85
(A.1)
(ii) Passo indutivo
Se, para qualquer n, temos
12 + 22 + ... + n2 =
n3 n2 n
+
+ ,
3
2
6
então, adicionando (n + 1)2 , teremos
n3 n2 n
+
+ + (n + 1)2 .
3
2
6
(A.2)
(n + 1)3 (n + 1)2 n + 1
+
+
.
3
2
6
(A.3)
12 + 22 + ... + n2 + (n + 1)2 =
Mas, de acordo com (A.1),
12 + 22 + ... + n2 + (n + 1)2 =
Então, temos que verificar se (A.2) e (A.3) são iguais:
(n + 1)3 (n + 1)2 n + 1
n3 + 3n2 + 3n + 1 n2 + 2n + 1 n + 1
+
+
=
+
+
3
2
6
3
2
6
2
3
1 n
1
1
n
+ n2 + n + +
+n+ +n+
=
3
3
2
2
6
n3 n2 n 1 1 1
=
+
+ + + + + n2 + 2n
3
2
6 3 2 6
3
2
n
n
n
=
+
+ + n2 + 2n + 1
3
2
6
n3 n2 n
+
+ + (n + 1)2 .
=
3
2
6
Exemplo A.0.3.
1 + 2 + 3 + 4 + ... + n =
n(n + 1)
.
2
Prova.
(i) Base de indução
Podemos verificar que a equação (A.4) é válida para n = 1:
1=
1.2
= 1.
2
(ii) Passo indutivo
Se, para qualquer n, temos
1 + 2 + ... + n =
86
n(n + 1)
,
2
(A.4)
então, adicionando (n + 1), teremos
1 + 2 + ... + n + (n + 1) =
n(n + 1)
+ (n + 1).
2
(A.5)
(n + 1)(n + 2)
.
2
(A.6)
Mas, de acordo com (A.4),
1 + 2 + ... + n + (n + 1) =
Então, temos que verificar se (A.5) e (A.6) são iguais:
n(n + 1)
n(n + 1) 2n + 2
+n+1 =
+
2
2
2
2
n + n + 2n + 2
=
2
n2 + 3n + 2
=
2
(n + 1)(n + 2)
=
.
2
Para explicações adicionais, veja [Monteiro, 1978] e [Hefez, 2002].
87
Apêndice B
Teorema de Lagrange
Sejam n ≥ 2 ∈ Z, r um primo positivo, S o conjunto {1, 2, ..., r} e U (r) o grupo
abeliano dos elementos inversı́veis de Zr . Podemos construir o grupo quociente
U (r)/hn̄, p̄i e chamemos de d sua ordem (sua quantidade de elementos). Para
entendermos a estrutura desse grupo quociente, veja o seguinte
Exemplo B.0.4. Suponha r = 13, n = 12 e p = 3.
¯ 11,
¯ 12}.
¯
Neste caso, Zr = Z13 = {0̄, 1̄, 2̄, 3̄, 4̄, 5̄, 6̄, 7̄, 8̄, 9̄, 10,
O conjunto das
classes inversı́veis, isto é, que possuem inverso multiplicativo, de Z13 é U (13) =
¯ 11,
¯ 12}.
¯ As classes n̄ e p̄ correspondem a 12
¯ e 3̄, respecti{1̄, 2̄, 3̄, 4̄, 5̄, 6̄, 7̄, 8̄, 9̄, 10,
vamente. A classe 3̄ tem ordem 3, pois 3 é o menor expoente positivo k de 3̄, tal
¯ é 2 (12
¯ 2 = 144
¯ = 1̄). O subgrupo hn̄, p̄i passa a ser
que 3̄k = 1̄. Já a ordem de 12
¯ 3̄i (gerado pelas classes 12
¯ e 3̄, e corresponde às multiplicações das potências
h12,
¯
¯ 3̄i = {1̄, 3̄, 4̄, 9̄, 10,
¯ 12},
¯ um subgrupo de U (13),
de 12 e 3̄ em Z13 ). Ou seja, h12,
conforme a Tabela B.1. Veja que não precisamos multiplicar as potências com
expoente acima da ordem das classes, pois voltaremos a ter os mesmos valores.
Tabela Multiplicativa das Potências
¯0
¯1
×
12
12
¯
¯
3̄0 1̄ × 1̄ = 1̄ 1̄ × 12
= 12
1
¯
¯
¯
3̄ 3̄ × 1̄ = 3̄ 3̄ × 12 = 36
= 10
2
¯ = 108
¯
3̄ 9̄ × 1̄ = 9̄ 9̄ × 12
=
4̄
¯ 3̄i
Tabela B.1: Elementos do conjunto h12,
¯ 3̄i é o conjunto dos elementos de U (13) separaO grupo quociente U (13)/h12,
¯ 3̄i. Em outras palavras,
dos por classes de restos pelos elementos do subgrupo h12,
¯ 3̄i} para cada
é o conjunto de todos os elementos x̂ = {ȳ ∈ U (13) : ȳ ≡ x̄ mod h12,
x̄ ∈ U (13). Podemos determinar esses elementos fazendo, para todo x̄ ∈ U (13),
¯ 3̄i}. Assim, fica evidente que 1̂ é igual a h12,
¯ 3̄i. Como a ordem
x̄ · h̄, h̄ ∈ h12,
(número de elementos) de U (13) = 12, vemos que U (13) tem 6 elementos fora
¯ 3̄i deve possuir pelo menos mais uma classe de equivalênde 1̂, então U (13)/h12,
¯ 3̄i, vamos começar por multiplicar 2̄
cias além de 1̂. Como 2̄ não está em h12,
¯
¯
¯ = 7̄, 24
¯ = 11}.
¯
por h12, 3̄i. Assim, obtemos {2̄, 6̄, 8̄, 18 = 5̄, 20
Ordenando, te¯ justamente as 6 classes que faltavam para completar U (13).
mos {2̄, 5̄, 6̄, 7̄, 8̄, 11},
88
Qualquer outra multiplicação de elementos de U (13) por elementos do seu sub¯ 3̄i resultará em um desses conjuntos de classes. Assim, o grupo quogrupo h12,
¯ 3̄i tem apenas 2 elementos, as classes 1̂ e 2̂, que representam
ciente U (13)/h12,
¯ 3̄i. Portanto, a
uma relação de equivalência dos elementos de U (13) módulo h12,
¯
ordem d de U (13)/h12, 3̄i é 2.
¯ 3̄i gera conjuntos disjuntos
De fato, isso era esperado, pois o subgrupo h12,
das classes de equivalência de U (13). Cada conjunto tem, obviamente, o mesmo
¯ 3̄i, devido à forma que são gerados (multiplicando os
número de elementos de h12,
¯
elementos de h12, 3̄i pelos de U (13)). Como são disjuntos, ou seja, não possuem
elementos em comum, o número total de conjuntos de classes distintas de U (13)
¯ 3̄i, isto é, a ordem do grupo quociente U (13)/h12,
¯ 3̄i, será igual ao
módulo h12,
¯ 3̄i. No
número de elementos de U (13) dividido pelo número de elementos de h12,
nosso caso, 12/6 = 2. Isso será usado para provar o
Teorema B.0.5 (Teorema de Lagrange). Em um grupo finito, a ordem de
qualquer subgrupo divide a ordem do grupo.
Prova. Sejam (G, ?) um grupo finito e H um subgrupo de G. Mas G é a união
das classes de equivalência distintas em relação a congruência módulo H. Além
disso, duas classes de equivalência distintas são disjuntas. Ou seja, considerando
C1 , C2 , · · · Ct todas as classes de equivalências distintas, temos
G = C1 ∪ C2 ∪ · · · ∪ Ct , onde Ci ∩ Cj = ∅.
Mas isso quer dizer que
|G| = |C1 | + |C2 | + · · · + |Ct |.
(B.1)
Seja e o elemento neutro de G. Então, ē é uma das classes de G/H e coincide
com H, pois ē = {e ? x : x ∈ H}.
Em particular, para cada elemento a ∈ G temos ā = {a ? x : x ∈ H}. Assim, ā
não pode ter mais elementos que H. E, para que tenha menos elementos, terı́amos
que ter a ? x1 = a ? x2 para ao menos dois elementos x1 e x2 distintos em H. Mas,
se isso fosse possı́vel, multiplicando a?x1 = a?x2 pelo inverso de a em G, terı́amos
que x1 = x2 em H, contrariando o fato de que seriam distintos. Logo, cada classe
ā possui a mesma quantidade de elementos de H.
Assim, de (B.1), temos:
|G| = |H| + |H| + · · · + |H|
|G| = t|H|.
Portanto, a ordem de G é múltipla da ordem de H, completando a prova.
Corolário B.0.6. A ordem de um elemento inversı́vel de um grupo divide a
ordem do grupo.
Prova. Sejam (G, ?) um grupo finito, a um elemento inversı́vel de G e k a
ordem de a em G, ou seja, o menor expoente positivo tal que ak = e, onde e é o
89
elemento neutro de G. Neste caso, o subconjunto hai, gerado pelas potências de
a, é {e, a, a2 , ..., ak−1 }. Potências a partir de k serão repetidas em hai. Logo, hai
tem k elementos distintos (sua ordem é k). Além disso, hai é um subgrupo de G,
pois e ∈ hai, ar ? as = ar+s ∈ hai e (as )−1 = a−s ∈ hai. Assim, a ordem k de
a em G, que é igual ordem de hai, divide a ordem de G, como conseqüência do
Teorema de Lagrange.
90
Referências
[Agrawal and Biswas, 2003] Agrawal, M. and Biswas, S. (2003). Primality and
Identity Testing via Chinese Remaindering. Journal of the ACM, 50(3):429–
443.
[Agrawal et al., 2004] Agrawal, M., Kayal, N., and Saxena, N. (2004). PRIMES
is in P. Annals of Mathematics, 160(2):781–793.
[Almeida and Thery, 1999] Almeida, J. C. and Thery, L. (1999). Correctness of
RSA algorithm.
http://coq.inria.fr/contribs/RSA.html.
[Bach and Shallit, 1996] Bach, E. and Shallit, J. (1996). Algorithmic Number
Theory. MIT Press.
[Barendregt and Geuvers, 2001] Barendregt, H. and Geuvers, H. (2001). Proofassistants using Dependent Type Systems. In Handbook of Automated
Reasoning, pages 1149–1238.
http://citeseer.ist.psu.edu/article/barendregt99proofassistant.html.
[Barendregt, 1992] Barendregt, H. P. (1992). λ-Calculi with Types. Handbook
of Logic in Computer Science, II.
[Bernstein, 2003] Bernstein, D. J. (2003).
Kayal-Sexena.
http://cr.yp.to/papers/aks.pdf.
Proving Primality After Agrawal-
[Bernstein, 2004] Bernstein, D. J. (2004). Proving Primality in Essentially Quartic Random Time.
http://cr.yp.to/primetests/quartic-20060914-ams.pdf.
[Bertot and Castéran, 2004] Bertot, Y. and Castéran, P. (2004). Interactive
Theorem Proving and Program Development. Springer, Sophia Antipolis.
[Campello and Leal, 2007] Campello, A. C. and Leal, I. (2007). Teoria Aritmética
dos Números e Criptografia RSA.
http://www.ime.unicamp.br/∼ftorres/ENSINO/MONOGRAFIAS/antonio RSA .pdf.
[Cormen et al., 2001] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein,
C. (2001). Introduction to Algorithms. MIT Press, Cambridge, MA.
91
[Coutinho, 2004] Coutinho, S. C. (2004). Primalidade em Tempo Polinomial.
Coleção Iniciação Cientı́fica. SBM, Rio de Janeiro.
[Crandall and Papadopoulos, 2003] Crandall, R. and Papadopoulos, J. (2003).
On the implementation of AKS-class primality tests.
http://developer.apple.com/hardware/ve/pdf/aks3.pdf.
[de Moura and Peixoto, 2008] de Moura, F. L. C. and Peixoto, R. (2008). A Verificação Formal do Algoritmo AKS em Coq. Site do Professor Flávio Leonardo
Cavalcanti de Moura - CIC/UnB.
http://www.cic.unb.br/∼flavio/AKS.
[Friedman, 2006] Friedman, H. M. (2006). Adventures in the Verification of
Mathematics. In Computer Science Colloquium. Ohio State University.
[Hefez, 2002] Hefez, A. (2002).
Curso de Álgebra, volume 1 of Coleção
Matemática Universitária. IMPA, Rio de Janeiro, 3 edition.
[Hopcroft et al., 2001] Hopcroft, J. E., Motwani, R., and Ullman, J. D. (2001).
Introduction to Automata Theory, Languages and Computation. AddisonWesley, 2 edition.
[INRIA, 2008] INRIA (2008). Coq Contribs: Project Info.
http://gforge.inria.fr/projects/coq-contribs.
[Knuth, 1968] Knuth, D. E. (1968). Seminumerical Algorithms, volume 1 of The
Art Of Computer Programming. Addison-Wesley, Reading.
[López-Ortiz, 1997] López-Ortiz, A. (1997). Frequently Asked Questions in
Mathematics.
http://www.cs.uwaterloo.ca/∼alopez-o/math-faq/math-faq.html.
[Monteiro, 1978] Monteiro, L. H. J. (1978). Elementos de Álgebra. Livros Técnicos e Cientı́ficos, Rio de Janeiro, 2 edition.
[Paulson and Nipkow, 2008] Paulson, L. and Nipkow, T. (2008). Isabelle Home
Page. University of Cambridge and Technical University of Munich.
http://isabelle.in.tum.de/.
[Research Triangle Institute, 2002] Research Triangle Institute (2002). The Economic Impacts of Inadequate Infrastructure for Software Testing. Sponsored
by the Department of Commerce’s National Institute of Standards and Technology.
[Ribenboim, 1995] Ribenboim, P. (1995).
Records. Springer, New York, NY.
The New Book of Prime Number
[Ribenboim, 2004] Ribenboim, P. (2004). The Little Book of Bigger Primes.
Springer, New York, NY, 3 edition.
92
[Santos et al., 2002] Santos, P., Neto, R. X., and Enoque, T. (2002). Uma tentativa de implementação do algoritmo de primalidade “AKS”. Site do Professor
Pedro Rezende, CIC-UnB.
http://www.cic.unb.br/docentes/pedro/trabs/primal.htm.
[Schoof, 2003] Schoof, R. (2003). Agrawal-Kayal-Saxena primality test.
http://www.mat.uniroma2.it/∼schoof/agrawalma.pdf.
[SRI International, 2008] SRI International (2008). PVS Specification and Verification System.
http://pvs.csl.sri.com/index.shtml.
[The Coq Development Team, 2008a] The Coq Development Team (2008a). The
Coq Distribution. INRIA-Rocquencourt.
http://coq.inria.fr/distrib-eng.html.
[The Coq Development Team, 2008b] The Coq Development Team (2008b). The
Coq Proof Assistant. INRIA-Rocquencourt.
http://coq.inria.fr.
[The Coq Development Team, 2008c] The Coq Development Team (2008c).
The Coq Proof Assistant Documentation. INRIA-Rocquencourt.
http://coq.inria.fr/doc-eng.html.
[The Coq Development Team, 2008d] The Coq Development Team (2008d).
The Coq Proof Assistant Reference Manual. INRIA-Rocquencourt.
http://coq.inria.fr/V8.1pl3/refman/index.html.
[The Coq Development Team, 2008e] The Coq Development Team (2008e). The
Coq Proof Assistant Related Tools. INRIA-Rocquencourt.
http://coq.inria.fr/tools-eng.html.
[The Coq Development Team, 2008f] The Coq Development Team (2008f). The
Coq Standard Library. INRIA-Rocquencourt.
http://coq.inria.fr/library-eng.html.
[The Coq Development Team, 2008g] The Coq Development Team (2008g). The
Coq User Contributions. INRIA-Rocquencourt.
http://coq.inria.fr/contribs-eng.html.
[Thery, 2004] Thery, L. (2004). Numbers equal to the sum of two square numbers.
http://coq.inria.fr/contribs/SumOfTwoSquare.html.
[Thery and Boldo, 2001] Thery, L. and Boldo, S. (2001). Library for floating
point numbers.
http://coq.inria.fr/contribs/Float.html.
[Tou and Alexander, 2005] Tou, C.-S. and Alexander, T. (2005). AKS Algorithm.
http://padic.mathstat.uottawa.ca/∼MAT3166/reports/AKS.pdf.
93
[Wiedijk, 2008] Wiedijk, F. (2008). Formalizing 100 Theorems.
http://www.cs.ru.nl/∼freek/100/index.html.
94

ver/abrir - Repositório do Departamento de Ciência da Computação

Transcrição

Documentos relacionados

Estruturas - Nicolau Corção Saldanha

Teorema de Ptolomeu

SHELLAC 78`

Solução 2ª Eliminatória

Gabarito

A Semente de Discrepância

Jovens criam micro satélite que permite estudar a radiação solar

Senhor Presidente O Hospital das Bonecas foi criado pela família

Equipa açoriana vence concurso nacional de micro satélites

Maior substring em comum