PRIMALIDADE: FUNDAMENTOS, TESTES E PERSPECTIVAS
José Aluízio Ferreira Lima1
Sinval Braga de Freitas2
RESUMO
Neste trabalho procuramos mostrar a evolução histórica e a situação atual relativa a testes de primalidade, seus
fundamentos teóricos, os caminhos trilhados e perspectivas sobre o assunto.
Palavras-chave: primalidade, testes, história.
1. INTRODUÇÃO
O artigo trata sobre testes de primalidade. É uma área da matemática pura, mais especificamente
vinculado a Teoria dos Números e a teoria Analítica dos Números. Envolve também a
Matemática Computacional. Na realidade é um assunto transversal que faz um corte nos três
campos do conhecimento matemático. Mais especificamente o artigo tem em vista mostrar a
situação atual relativa a testes de primalidade, seus fundamentos teóricos, os caminhos trilhados e
perspectivas sobre o assunto. O desenho do artigo é assim caracterizado: focaliza os estudos
sobre testes da primalidade, fundamentos teóricos e algoritmos; busca levantar o “estado da arte”
sobre o assunto; visa mostrar caminhos e perspectivas para estudo sobre testes de primalidade; e
aborda a idéia de que estamos vivendo um grande momento da matemática em relação à Teoria
dos Números Primos e que em função das demandas atuais novos testes de primalidade surgirão.
O que justifica este artigo são sua oportunidade e relevância: a) os sistemas de criptografia atuais
demandam a utilização de grandes números primos e o levantamento sobre a situação atual sobre
testes de primalidade, seus fundamentos teóricos e perspectivas de desenvolvimento podem ser
apropriados; b) é relevante, pois o surgimento da necessidade de confirmação da primalidade de
um número inteiro para sua utilização nos sistemas de criptografia atuais está na pauta do dia; c)
um trabalho organizado e sistematizado sobre tentativas, resultados obtidos e perspectivas sobre
testes de primalidade pode contribuir para a própria Teoria dos Números.
A primeira parte estabelece as categorias de análise do artigo: avanço conceitual, técnico e
tecnológico. O avanço conceitual será muitas vezes chamado de salto conceitual, revolução
conceitual, grande momento dos números primos, dentre outros; fala ainda de algoritmos P e NP.
A segunda parte trata de uma breve história dos números primos, segundo as categorias
anteriormente definidas. A terceira cuida da análise dos fundamentos teóricos de alguns
importantes testes de primalidade, utilizando, principalmente, as categorias já mencionadas. É
finalizado com uma conclusão que mostra os resultados e perspectivas atuais sobre o assunto.
Ao finalizar esta introdução é preciso destacar a importância dos números primos, que vai muito
além das suas aplicações práticas em computação e criptografia, como muitos pensam hoje em
1
2
José Aluizio Ferreira Lima - Licenciando em Matemática
Orientador
dia. Não existiria a Teoria dos Números sem os primos, sem seu conceito e propriedades
decorrentes. As obras de Legendre e Gauss mostram isso.
2. CATEGORIAS DE ANÁLISE
O referencial teórico para estudo está caracterizado pelas seguintes categorias de análise: avanço
conceitual, avanço técnico e avanço tecnológico.
2.1 Avanço Conceitual
Ao realizar uma leitura atenta sobre a história matemática e da biografia de grandes matemáticos
é fácil identificar, implicitamente, o processo de criação na matemática e os caminhos seguidos
para o desenvolvimento de determinadas teorias ou ramos matemáticos. Isto é muito importante,
porque permite explicitar a realidade subjacente ao processo desenvolvimento da matemática,
com base nos procedimentos de descoberta dos fatos matemáticos, que se inicia com um
problema prático ou teórico, uma intuição e o conseqüente processo de experimentação em torno
do assunto ou problema, passando por um momento heurístico até a formalização final e a
conseqüente exploração das aplicações.
O fato histórico matemático relevante ou grandes momentos da matemática, que aparecem sob a
forma de uma descoberta importante, só ocorre depois de um período de maturação que
desemboca em uma solução mais geral e inovadora. É quando ocorre um avanço conceitual
significativo ou revolucionário.
2.2 Avanço Técnico
O avanço técnico ocorre, em matemática, quando realizado um salto conceitual significativo, um
grupo de matemáticos explora o novo caminho, descobrindo novos métodos e técnicas que
facilitam o desenvolvimento teórico e prático do assunto. Por exemplo, após os avanços
conceituais realizados por Cauchy e Riemann em relação ao Cálculo Diferencial e Integral, um
novo conjunto fundamental de teoremas, métodos e técnicas referentes ao cálculo foi
desenvolvido. Foram avanços técnicos importantes, mas não foram avanços conceituais. O
avanço técnico em matemática sempre ocorre em torno de um conceito já anteriormente
desenvolvido. É importante na matemática, mas não tem o potencial de transformação do avanço
conceitual.
2.3 Avanço Tecnológico
Para definir o conceito de avanço tecnológico em matemática é apresentado um exemplo dado
por (John J O'Connor e Edmund Robertson F, 2008), em uma tradução livre:
Um desafio. Se você acha que os conceitos matemáticos são de fácil descoberta, então lanço aqui
é um desafio para fazer você pensar. Napier e Briggs e outros introduziram no mundo os
logaritmos à quase 400 anos atrás. Estes foram utilizados por 350 anos, como a principal
ferramenta de cálculo científico, financeiro e aritmético. Uma espantosa quantidade de trabalho e
2
esforço foi evitada usando logaritmos. Como poderiam ter sido realizados os pesados e volumosos
cálculos necessários nas ciências sem a existência dos logaritmos?
Então, o mundo mudou. A calculadora de bolso apareceu. O logaritmo continua a ser uma
importante função matemática, mas a sua utilização no cálculo foi embora para sempre.
Aqui está o desafio. O que irá substituir a calculadora de bolso? Você poderá dizer que esta é uma
pergunta injusta. Entretanto deixe-me lembrá-lo de que Napier inventou os conceitos básicos de
um computador mecânico, ao mesmo tempo do que os logaritmos e as respectivas tabelas. As
idéias básicas que levarão à substituição da calculadora de bolso estão com certeza nas coisas que
nos rodeiam...
Podemos pensar em calculadoras mais rápidas, calculadoras menores, calculadoras melhores, mas
eu estou pedindo algo tão diferente da calculadora como a calculadora é em si diferente da tabela
de logaritmos. Tenho uma resposta à minha pergunta, mas ela iria estragar o meu ponto de desafio
se eu disser aqui qual ela é. Pense sobre isso pois sabemos quão difícil foi inventar a geometria não
euclidiana, os grupos, relatividade geral, teoria dos conjuntos...
Pelo exemplo acima fica evidente o conceito de avanço tecnológico. No caso temos em relação
às tabelas de logaritmo e às calculadoras de bolso, um avanço tecnológico precedido de avanços
conceituais. Isto quase sempre acontece.
3. BREVE HISTÓRIA CONCEITUAL DOS NÚMEROS PRIMOS
Uma breve resenha histórica do estudo dos números primos, começando pelos gregos até o
advento do algoritmo AKS, mostra alguns momentos com características próprias muito
específicas. Estes momentos serão chamados de “momentos significativos para os números
primos”. São períodos históricos, longos ou curtos, quando os números primos receberam
tratamento diferenciado e com especificidade própria, além de sua importante utilização na teoria
dos números. Estes momentos significativos são essencialmente marcados por avanços
conceituais e técnicos.
3.1 Período Grego
Este período vai de 300 a.C., com o desenvolvimento axiomático da geometria e da teoria dos
números (aritmética para os gregos), registrados nos Elementos de Euclides, até 194 a.C. com a
morte de Erastóstenes, criador do “primeiro teste de primalidade” (Eves, 2004).
É quando surge a idéia de número principal (primo) e secundário (composto). Para o Grego, os
primos são blocos a partir dos quais os números são construídos. Euclides define o conceito de
número primo, demonstra que o conjunto dos primos é infinito e apresenta o principio parcial da
fatoração única de um número composto; desenvolve o "algoritmo de Euclides", para determinar
o máximo divisor comum entre dois números – utilizado com a finalidade encontrar um
segmento de reta que cuja medida fosse comum a vários outros segmentos; estabelece
proposições sobre o menor múltiplo comum; define o conceito de co-primos. Estes conceitos não
são gratuitos, pois surgiram de necessidades de medidas geométricas. Erastóstenes cria o método
de peneirar a seqüência dos naturais - o Crivo de Erastóstenes - recolhendo os primos da série.
Conhecida a seqüência dos primos era possível identificar as “medidas” - números - que
3
compunham um segmento de reta, uma figura plana ou um sólido, pelo processo de divisão dos
segmentos em fatores primos. Estes resultados eram utilizados, principalmente na teoria das
proporções.
Para analisar este momento, não podemos esquecer o período que antecedeu Euclides, com Tales
de Mileto (585 a. C), como representante do início da geometria dedutiva, passando pela
aritmética e geometria Pitagóricas. Com base num conjunto de conhecimento acumulados por
seus antecessores, Euclides consolida um avanço conceitual brilhante e revolucionário com a
“publicação” de seus Elementos de Geometria, que pela primeira vez apresenta a Matemática
como um corpo de conhecimento organizado e sistematizado. Esta forma de organização
condiciona o desenvolvimento da matemática até os dias de hoje. Ele lança as bases do Método
Dedutivo de forma definitiva. Isto representa um avanço conceitual difícil de ser igualado.
É por meio dos livros VII e IX de seus Elementos que ele estabelece os fundamentos da Teoria
dos Números. Define número e pela primeira vez, de forma sistematizada, conceitua número
primo e composto. É no seu tratado que o houve um avanço conceitual significativo do conceito
de número, que passou da representação de quantidades e medidas, para um nível de abstração
mais alto, representado por unidades em forma de segmentos de reta. Não tínhamos mais uma,
duas ou três maçãs, ou 10 estádios, mas um segmento abstrato qualquer representando a unidade.
E uma quantidade de unidades representando número. É esta definição muito mais abstrata de
número que permite estabelecer novas definições, constituir e provar proposições. De qualquer
modo, número era ainda era uma medida definida por uma unidade qualquer. Porém é a primeira
definição de número que permite um desenvolvimento axiomático da teoria dos números por
meio de definições e proposições. Este conceito de número, apesar do baixo nível de abstração,
foi um avanço revolucionário para a época. A unidade não era número.
Então, é interessante verificar como Euclides procedeu, estabelecendo conceitos que irão
influenciar a Teoria dos Números por séculos. As imagens foram retiradas de (D.E.Joyce, 1997).
Este é um resumo, onde estão abordados somente os aspectos assenciais para análise. A
numeração é a adotada na obra de Euclides, Livros VII e IX.
3.1.1 Definição de Número
Definição VII-1. A unidade é aquela que em virtude do qual cada uma das coisas que existe é
chamado um.
Definição VII-2. Um número é composto por uma multiplicidade de unidades.
As definições 1 e 2 têm então a seguinte representação
u
Figura 1
4
Neste caso, se A é a unidade então o segmento BE é o número 3. O importante é que só porque
ele representa os números por segmentos não significa que eles são segmentos, e ele nunca
chama os números de segmentos.
3.1.2 Número Primo, Composto e Co-Primos
Aqui são apresentados os conceitos fundamentais que orientaram ao longo do tempo (séculos) o
desenvolvimento da Teoria dos Números.
Definição VII-11. Um número primo é aquele que é medido somente pela unidade.
Definição VII-12. Números relativamente primos são aqueles que têm somente a unidade como
medida comum.
Definição VII-13. Um número composto é aquele que é medido por algum número.
Os números primos passam a formar um conjunto muito importante na Teoria dos Números.
Grande parte desta teoria é dedicada à análise dos mesmos.
Figura 2
Afigura (4) mostra muito bem o conceito de número primo. Pois o número três só pode ser
medido pela unidade A. Qualquer outro segmento tomado em BE é parte de BE, mas não mede
BE. Ao contrário, número composto é aquele que pode ser medido por algum número diferente
da unidade. Assim na figura 5, o número dois, representado pelo segmento AB, mede o número
seis, representado pelo segmento CF. Isto ocorre também com o número três.
Figura 3
Este é um momento próprio para melhorar o entendimento sobre o significado de avanço
conceitual. Basta comparar a definição de Euclides e a definição atual utilizada em Teoria dos
Números.
Para Euclides, número é uma multiplicidade que está associada a um segmento de reta unitário e
número primo é aquele que só pode ser medido pela unidade; atualmente o conceito de número já
está abstraído de qualquer relação com uma unidade de medida, seja ela qual for. E o conceito de
numero primo esta vinculada ao conceito de divisor próprio de um número, quando define que
número primo é aquele que só é divisível por si mesmo ou por 1. Esta definição representa um
salto conceitual significativo. É também um progresso técnico importante, pois é muito mais
operacional, facilitando definir axiomas, demonstrar proposições e desenvolver algoritmos.
5
3.1.3 O Algoritmo de Euclides
Originalmente esta primeira proposição apresenta um algoritmo para determinar se dois números
distintos são relativamente primos. A demonstração apresentada por Euclides é até certo ponto
simples. Mas carece de uma interpretação adequada. É claro que quando os números não são coprimos, o resultado leva a encontrar o maior número que “mede” os dois números dados. Isto é, o
algoritmo permite encontrar o máximo divisor comum (mdc) entre dois números distintos. Se o
mdc for a unidade, os números são relativamente primos. Se for uma medida diferente da
unidade, este é o maior número (ou medida) que mede os dois números dados. A seguir a
proposição e a interpretação de sua demonstração em linguagem atual.
Proposição IX-1. Dados dois números diferentes, se o menor é continuamente subtraído do
maior e se o número que sobra nunca mede o anterior, até sobrar uma unidade, então os
números originais são primos entre si.
Demonstração. Começando com dois números, onde o menor é subtraído do
maior tantas vezes que for possível. Para facilitar, vamos designar a1 = AB e
CD = a 2 , onde, é claro, AB > CD . Então o primeiro passo é subtrair
repetidamente a 2 de a1 , até encontrar um novo número (resto) a3 ( AF ) menor
que a 2 . Algebricamente, na notação de hoje, fica assim: a1 = m1a 2 + a3 , onde m1
é o número de vezes que o a 2 foi subtraído de a1 . Este passo subtraí
repetidamente a3 de a 2 deixando um resto a 4 ( CG ): a 2 = m2 a3 + a 4 , etc. Pela
hipótese desta proposição, o algoritmo para quando a sobra é 1 (unidade no
sentido de Euclides): a n −1 = mn−1a n + 1 .
No caso AH que coincide com E dado como a unidade. Nesta prova de
Euclides a unidade (1) é o a5 . Uma vez que não existe nenhum número (onde
número é necessariamente uma multiplicidade de unidades) maior do que a
unidade que divide 1 (a unidade de Euclides), não existe nenhum número que
divide os dois números dados. Logo eles são co-primos.
Figura 4
Nesta explicação partimos do princípio de que a unidade (1) é o resultado de um processo
interativo. Este processo é uma prévia ao chamado Algoritmo de Euclides, fundamental no
Desenvolvimento da Teoria dos Números.
Proposição IX-2. Encontrar a maior medida comum entre dois números que não sejam
relativamente primos.
Aqui está o Algoritmo de Euclides em todo o seu esplendor e a demonstração é essencialmente a
mesma da proposição 1, quando o algoritmo pára em um “número” que não é a unidade. Este
número mede os “números dados”, e hoje é chamado mdc.
6
Para o que interessa a este artigo serão apresentadas mais três proposições referentes a aspectos
fundamentais para os números primos, pois mostra avanços conceituais importantes para a Teoria
dos Números: a proposição que afirma que qualquer número composto tem um fator primo, uma
versão fraca do Teorema Fundamental da Aritmética e a Infinitude da Seqüência dos Primos.
Antes de passar às explicações é importante ressaltar a última proposição – O Conjunto dos
Números Primos é Infinito – embora demonstrada pelo próprio Euclides, é o fato matemático
referente aos primos que causa o maior impacto até hoje.
Proposição IX-31. Um número composto é medido por algum número primo.
Figura 5
Esta proposição apresenta um avanço conceitual é um técnico. O conceitual mostra que os primos
estão na base de construção do conjunto Z e outros. O técnico refere-se à utilização da
demonstração por recorrência, até onde se saiba, pela primeira vez na matemática. Assim fez
Euclides:
Passo 1. Seja 27 = A (onde A representa qualquer número, no caso 27). Encontre o maior
número que mede 27. É o 9 = B.
Passo 2. Subtraia 9 de 27. 27 – 9 = 18.
Passo 3. Qual o maior número que mede 18. É o 9.
Passo 4. Subtraia 9 de 18. 18 – 9 = 9.
Passo 5. Qual é o maior número que mede 9. É o 3.
Passo 6. Subtraia 3 de 9. Então 9 - 3 = 6.
Passo 7. Qual o maior número que mede 6. É o 3.
Passo 8. Subtraia 3 de 6. 6 – 3 = 3.
Passo 9. Agora é perguntado: qual o maior número que mede 3. Não existe, pois 3 é
medido somente pela unidade, no sentido de Euclides. Logo pela definição de números primos, 3
= C é primo.
Devido a importância do tema é interessante ver com Euclides realizou a sua demonstração.
Euclides procedeu mais ou menos assim, utilizando a figura acima.
Demonstração. “Seja A um número composto. Eu digo que ele é medido por algum número
primo. Pela definição de número composto, eu sei que se A é composto, então ele é medido por
algum número B. Agora, se B é primo, a demonstração está feita. Mas, se B um número
composto, então algum número mede ele. Seja então o número C que mede ele. Então, se C mede
B e B mede A, portanto C também mede A. E, se C é primo, a proposição fica demonstrada. Mas
se ele é composto, então algum número mede C. Mas, se o processo é continuado até o fim, então
algum número primo é encontrado, o qual mede o número anterior e, portanto mede A. Se ele não
7
é encontrado, então existe uma seqüência infinita de números que mede o número A, cada qual é
menor que o outro anterior. O que é impossível dentro dos números. (É evidente que Euclides se
refere ao conjunto dos números naturais). Portanto, se algum número primo é encontrado e ele
mede o número anterior, então ele também mede A. Portanto, qualquer número composto é
medido por algum número primo.”
Esta uma das mais elegantes, simples e inovadoras demonstrações de Euclides. Ele inova de três
maneiras: a) realiza um avanço conceitual significativo quando demonstra que os números
primos estão na base da Teoria dos Números e indica o caminho para o Teorema Fundamental da
Aritmética; b) inova nas técnicas de demonstração, introduzindo a demonstração por recorrência
e c) mostra por exclusão que o processo de recorrência não poderia continuar indefinidamente,
pois se estava operando dentro dos números naturais.
Proposição IX-14. Se um número é o menor número que é medido por números primos, então ele
não é medido por qualquer outro número primo, exceto aqueles que inicialmente o mediam.
Figura 6
Na verdade o que esta proposição afirma é que se um número composto é o menor (mínimo)
múltiplo comum (mmc) de vários números primos, onde o mmc de primos, como se sabe, é o
produto destes números primos, então é evidente que ele será medido somente por seus fatores
primos. É uma prova simples e utiliza de proposição anterior (proposiçãoVII-30) que afirma: se
um primo mede um produto, então ele mede um dos fatores.
É a primeira aproximação do Teorema Fundamental da Aritmética, posteriormente demonstrado
por Gauss. Isto evidentemente se estende a qualquer número composto que tenha fatores primos
repetidos, por exemplo, 12 = 2 x 2 x 3. Neste exemplo somente os primos 2 e 3 medem 12 e, é
claro, nenhum outro primo. Observando a figura siga a demonstração dada à época.
Demonstração. “Seja A o menor número composto que é medido pelos primos B, C e D. Eu digo
que ele não é medido por qualquer outro número primo exceto B, C e D. Suponha que A pode ser
medido pelo número primo E, sendo E diferente de B, C e D. Agora, suponha que E mede A,
sendo que ele mede A conforme F, portanto F multiplicado por E é igual a A. E A é medido por
B, C e D. Mas, se dois números, multiplicados por um outro dá algum número, e se algum
número primo mede o produto, então ele mede um do números originais. Portanto cada número
primo B, C e D mede um dos números E e F. Agora eles não podem medir E, pois E é primo e
não é o mesmo que os números B, C e D. Portanto eles medem F, o qual é menor do que A, o que
é impossível, pois A é por hipótese o menor número medido por B, C e D. Portanto nenhum
número primo divide A, exceto B, C e D.”
8
Parece desnecessário insistir analisando as definições e proposições de Euclides. Mas o fato é que
pela primeira vez na história da matemática, são encontrados registros significativos sobre os
avanços conceituais e técnicos. Aqui Euclides avança a “idéia” que qualquer número pode ser
decomposto em fatores primos. Faz também um avanço técnico fundamental ao apresentar uma
demonstração por absurdo. Isto é avanço conceitual e técnico.
Proposição IX-20. Os números primos são mais do que qualquer número atribuído à imensidão
dos números primos.
Figura 7
Esta proposição demonstra que o conjunto dos primos é infinito e avança um tipo de
demonstração muito importante. É uma demonstração elegante e simples.
Demonstração. “Sejam dados os seguintes números primos A, B e C. Eu digo que há mais
números primos do que A, B, e C. Pegue o menor número DE medido por A, B e C. Adicione a
unidade DF a DE. Então EF pode ser primo ou não. Primeiro, seja ele primo. Então. Então, os
números primos A, B, C e EF, foram encontrados os quais são em maior quantidade do que A, B e
C. Segundo, seja EF não primo. Portanto ele é medido por algum primo. Seja ele medido por
algum número primo G. Eu digo que G não é nenhum dos números primos A, B e C. Vamos
supor que ele seja um destes números. Agora A, B e C medem DE, portanto G também mede DE.
Mas ele também mede EF. Portanto, G sendo um número, mede o restante, a unidade DF, o que é
absurdo. Entretanto, G não é o mesmo que qualquer um dos primos A, B e C. E pela hipótese ele
é primo. Portanto, os números primos A, B, C e G foram encontrados os quais são mais que a
quantidade dada inicialmente na multiplicidade dos primos.”
Esta é uma demonstração bela e elegante que aplica avanços conceituais anteriormente
consolidados, e utiliza a técnica de demonstração “por absurdo”. Utilizando uma linguagem atual
podemos supor que o plano da demonstração de Euclides era o seguinte: dada uma seqüência de
números primos, tão grande quanto se deseje, é possível construir o menor número composto que
é dividido por cada um dos números da seqüência inicial. Este número é o mmc de todos os
números primos da seqüência (como se sabe, é o produto deles). O passo seguinte é mostrar que
existe um novo número primo que não divide o menor número encontrado a partir de seqüência
inicial. Então existirá um novo número primo diferente de todos os anteriores. Na sua
demonstração Euclides usou apenas três numero primos, mas isto foi mais que suficiente.
9
Para encerrar o período grego da pequena história conceitual dos primos é preciso falar de
Erastóstenes que viveu em torno de 230 a. C.. Com base nos avanços conceituais conquistados
desde a época de Euclides, ele realizou um avanço técnico surpreendente para a aquele período.
Utilizando uma linguagem poética, se pode afirmar que ele se transformou em um pescador de
primos, pescando com sua rede - O Crivo de Erastóstenes - no caudaloso rio dos números
naturais, os cada vez mais raros números primos. Sem romantismo, seja o que interessa: qual a
preocupação de Erastóstenes em criar um método que permitisse separar os números primos
dentre o conjunto dos naturais? A resposta é: em primeiro lugar a teoria das proporções,
fundamental para a geometria grega. Em seguida o trabalho com os números planos, sólidos e
outras aplicações da época que obrigava a fatoração de números compostos em primos. Ver os
livros, VII e IX de Euclides (Euclides, 1944).
Ao terminar este período histórico é preciso deixar claro que o que mais importa são os avanços
conceituais, verdadeiras revoluções, que mudam a face da matemática e perduram.
3.2 Período Europeu
Após um longo interstício, isto referente ao tratamento específico dado aos números primos, a
preocupação com estes números é retomada, muitas vezes de forma indireta. Este período começa
com Fermat, Pierre de Fermat. (1601 - 1665), historicamente considerado por muitos o fundador
da Moderna Teoria dos Números e termina com Riemann, Georg Friedrich Bernhard Riemann
(1826 - 1866). Como na parte relativa aos gregos a preocupação neste tópico continua sendo a
identificação de desenvolvimentos conceituais e técnicos. Esta evolução dos conceitos em geral
jaz subjacente ao fato histórico. Então é preciso encontrá-la.
Foi neste período que teve início a preocupação com o problema que realmente importa neste
artigo: a determinação se um número dado é primo ou não. Ou, é possível determinar um método,
diferente do Crivo de Erastóstenes, capaz de gerar a seqüência dos números primos? Qual a
distribuição dos primos dentro do conjunto dos inteiros? Quais as diferentes formas que pode ser
caracterizado um número primo?
Se no período grego a Teoria dos Números estava praticamente concentrada em Euclides, no
momento Europeu, as coisas começaram a dispersar. Vamos inicialmente fazer uma cronologia
envolvendo os matemáticos que se empenharam com a Teoria dos Números e números primos
para posteriormente analisar os avanços conceituais e técnicos.
CRONOLOGIA DO PERÍODO EUROPEU PARA OS NÚMEROS PRIMOS
MATEMÁTICO
Fermat, P.
PERÍODO
TRABALHOS REALIZADOS
1601-1665
Fermat é considerado o fundador da moderna Teoria dos Números; Conjecturou o
chamado Pequeno Teorema de Fermat. Em linguagem matemática atual fica assim:
se p é um número primo, então para um natural a , a p ≡ a (mod p ) . Esta conjectura
foi provada por Euler em 1736. Atualmente este teorema é a base de muitos
resultados da Teoria dos Números e de métodos para a determinação de números
10
primos, utilizados em larga escala na computação e criptografia.
Mersenne
Goldbach
Euler
1588-1648
Conjecturou que todo número da forma M = 2 p − 1 é primo para p também primo.
A conjectura revelou-se falsa para vários valores de p . Até hoje os números de
Mersenne são usados para a busca de grandes números primos. Correspondente de
Fermat e outros matemáticos da época ele caracterizou-se por ser um grande
divulgador de achados matemáticos.
1690-1769
Foi correspondente de Euler é também grande divulgador das descobertas
matemáticas em sua época. É autor da conjectura, até hoje não demonstrada, que leva
o seu nome: todo inteiro par maior do que 2 é a soma de dois primos. Cálculos
computacionais indicam que a conjectura parece ser verdadeira.
1707-1783
Euler foi outro matemático que deu grandes contribuições à Teoria dos Números,
embora não tenha publicado nenhum tratado sobre o assunto, divulgando os seus
resultados por cartas ou artigos. Demonstrou o ”Pequeno Teorema de Fermat”
utilizando indução matemática e recursos elementares. Até hoje a sua função
chamada de “função
de Euler” é importantíssima na Teoria dos Números. O
seguinte resultado, uma simples generalização do Pequeno Teorema de Fermat, foi
demonstrada por ele: aϕ ( m) − 1 é divisível por m se a é co-primo com m .
Estabeleceu uma relação definitiva entre a análise e a teoria dos números por meio de
sua função zeta:
ζ (s) =
∞
n =1
1
n
s
=
∏ 1−
p
1
1
, onde o segundo membro é tomado para p primo e
ps
s > 1 é um número real.
Lagrange
1736-1813
Lagrange também deu grande importância a Teoria dos Números. Entre tantas outras
descobertas, provou o atualmente chamado Teorema de Wilson: p é um número
primo se, e somente se, ( p − 1)! ≡ −1 (mod p) .
Publicou em 1797-1798 a primeira abordagem exclusiva sobre a Teoria dos Números
em Essai sur la Théorie des Nombres. Tentou algumas demonstrações para o Último
Teorema de Fermat e iniciou o estudo da Lei da Reciprocidade Quadrática,
p
utilizando como notação o conhecido símbolo de Legendre:
= ±1 , se o inteiro
q
p co-primo com q seja (no caso positivo) ou não (no caso negativo) o resto
Legendre
1752-1833
quadrático da congruência x 2 ≡ p (mod q ) . Legendre também estabeleceu uma
conjectura sobre a distribuição dos números primos: π ( n) = n /(ln n − 1,08366 ) para
n crescendo indefinidamente. A função π (n ) é a função contagem dos números
primos até um número natural n . Demonstrou ainda que não existe função algébrica
racional que fornece sempre números primos. É com Euler, Lagrange e Legendre
que se inicia a Teoria Analítica dos Números e que tomou forma no decorrer dos
tempos.
Gauss
1777-1855
Logo no início de sua carreira Gauss estabeleceu a conjectura sobre a distribuição
dos números primos, que se tornou posteriormente o conhecido Teorema dos
Números Primos. A conjectura diz que a densidade da distribuição dos primos é
π ( n)
1
assintoticamente igual ao inverso do logaritmo de n . Isto é: D(n) =
≅
.
n
ln(n)
Foi ele que deu um formato definitivo à Teoria dos Números a partir de seu tratado
Disquisitiones Arithmeticae, obra publicada em 1801. Promoveu avanços conceituais
importantes. Antes da publicação do seu tratado a teoria dos números consistia em
11
um com junto isolado de teoremas e conjecturas. Gauss organizou o trabalho de seus
antecessores, preencheu lacunas, corrigiu demonstrações, incluiu idéias
extremamente inovadoras e deu uma estrutura sistemática para a Teoria dos
Números. A estrutura lógica do seu livro serviu de modelo para inúmeros
matemáticos que o seguiram. Foi Gauss quem deu a primeira demonstração completa
do Teorema Fundamental da Aritmética. É considerado por muitos historiadores
como o fundador da moderna teoria dos números.
Riemann
1826-1866
Função Zeta de Riemann e Hipótese de Riemann.
Hadamas
1865-1963
Prova do Teorema dos Números Primos – 1896.
Vallée-Poussin
1866-1962
Idem
Lobachevsky
1792-1856
Aproximação do Teorema dos Números Primos.
Tabela 1
Porém, antes de entrar na análise deste momento histórico, é necessário verificar os seus
antecedentes. Antes de Fermat, alguns avanços conceituais e técnicos, importantes para a teoria
dos números já haviam acontecido. É preciso situar de onde Fermat, Euler e outros começaram.
Identificar quais foram as suas bases conceituais e técnicas.
Para esta identificação - bases técnicas e conceituais - é necessário numa regressão histórica que
remonta ao início do segundo milênio d. C. na Europa, quando foi introduzido o sistema de
numeração hindu-arábico e as respectivas técnicas operatórias. O continente europeu só tomou
conhecimento formal deste sistema de numeração e suas técnicas, com um milênio de atraso em
relação aos árabes, com a obra Liber Abaci de Leonardo de Pisa, Leonardo de Pisa, (1170 - 1250)
também conhecido como Fibonacci. É provavelmente a partir daí que a cultura matemática
européia incorpora definitivamente o sistema hindu-arábico de numeração.
Este advento foi uma verdadeira iluminação para a matemática na Europa, pois trouxe consigo
avanços conceituais e técnicos extremamente relevantes ou até mesmo indispensáveis para o
futuro da matemática:
i. O conceito abstrato de número, desvinculado das operações de contagem e
medida;
ii. Numeração decimal de posição;
iii. O zero;
iv. E os métodos algoritmos de cálculo que substituíram o abacismo.
Este revolucionário “salto qualitativo”, em termos conceituais e técnicos, trouxe infinitas
possibilidades, sendo alguma delas a melhor visibilidade dos conjuntos numéricos e de sua
infinitude e a abstração que desvincula definitivamente estes conjuntos de processos de medida e
contagem.
Pela época de Fermat um novo avanço técnico e três conceituais já estavam se consolidando: a
notação matemática, o conceito de divisibilidade, os números negativos e a caracterização de
números primos e compostos.
12
O avanço técnico estava ocorrendo na notação matemática que passava gradativamente da forma
discursiva ou semidiscursiva para a literal (simbólica). Isto facilitava a visão do conteúdo
matemático, a sua expressão universal e as operações algébricas. A notação literal foi de fato um
avanço técnico considerável.
Quanto aos números negativos, o seu conceito demorou a ser introduzido na Europa. O certo é
que pela época de Fermat e Euler o conceito de número negativo como um número menor que
zero ainda estava sendo consolidado, embora fosse usado segundo regras operatórias bem
definidas, pois como diz Boyer (Boyer, 1974 p. 337): “A maior parte dos autores achava
necessário demorar-se longamente sobre as regras que governam a multiplicação de números
negativos, e alguns rejeitavam categoricamente a possibilidade de multiplicar dois números
negativos”.
É inequívoco que o conceito e as regras operatórias para números negativos e positivos, bem ou
mal, estavam estabelecidos e Euler as utilizava na forma instituída por ele, sem nenhuma
demonstração. Isto foi outro avanço conceitual e técnico considerável.
Na época de Euclides o conceito de número ainda não tinha sido abstraído da idéia de medida,
essencialmente medida geométrica, tanto que ele conceitua número composto com aquele que
pode ser medido por outro número e número primo como o que só pode ser medido pela unidade.
Pode-se supor, com certa certeza histórica, que a idéia atual de divisibilidade já estivesse presente
na primeira metade do século VII, embora só tenha sido formalizada a partir de Gauss. O
surgimento do que pode ser chamado de “conceito operacional” para divisibilidade, números
compostos e primos é fundamental para a nova teoria dos números. A partir desses conceitos é
possível testar pela divisão se um número inteiro é composto ou primo. A partir da idéia de
divisibilidade puderam ser concebidos os seguintes perfis operacionais para divisibilidade,
número inteiro composto e primo. Em linguagem atual o delineamento provavelmente seria:
i.
ii.
iii.
Um número inteiro a é divisível por b quando a = mb , sendo m um inteiro;
Um número inteiro a é composto quando ele é divisível por outro inteiro diferente
de 1 e dele mesmo;
Um inteiro positivo p, diferente de 1, é primo, se e somente se, 1 e p são os seus
únicos divisores.
É a partir destas concepções já postas que a teoria dos números pôde avançar, bastando para
confirmar esta idéia citar o decorrente Teorema Fundamental da Aritmética. É tendo como
fundamento este conjunto de idéias, que passaram a fazer parte da cultura matemática do período,
que Fermat, Euler, Gauss e tantos outros, puderam avançar celeremente rumo à Teoria dos
Números.
Prosseguindo a análise desse período é preciso identificar o legado de cada um em termos de
contribuição para o progresso conceitual e técnico em relação aos números primos. Para isto será
utilizada uma classificação de caráter meramente didático. A) Temos os exploradores e
aventureiros que por meio de experimentação e manipulações do conjunto dos inteiros, muitas
13
vezes sem nenhuma ou pouca preocupação com o rigor lógico, abrem caminhos e mostram
rumos. Nesta categoria estão Fermat e Euler; B) Noutra categoria, a dos formuladores e criadores
de paradigmas, está Gauss, Legendre e Riemann; C) Em uma terceira, a dos engenheiros que
buscam com base em conhecimento já estabelecido, demonstrar fatos ainda não consolidados,
erigindo um edifício lógico para formulações anteriores. Neste grupo estão Lagrange, Poussin e
Hadamas; D) Por fim, temos os divulgadores e correspondentes como Mersenne e Goldbach, que
à época realizaram o papel que hoje é feito pelos periódicos especializados e pela internet.
3.3 Período Intermediário
Este momento começa logo após Riemann, Hadamard e Vallée-Poussin e termina na década de
sessenta - setenta com a introdução da computação eletrônica digital (Lehmer). Muitos
matemáticos importantes pertencem a este período, e a maioria é desconhecida do grande
público, e mesmo de especialistas em matemática. A característica deste tempo são os avanços
conceituais referentes à linguagem matemática, atingindo níveis mais altos de abstração, técnicos
pela utilização de novas conquista da análise e tecnológico com o início da utilização de
computadores digitais em matemática. Ele é caracterizado por: a) aprofundamento da Teoria dos
Números e Teoria Analítica dos Números (Landau) em um corpo teórico organizado e
sistematizado, com a publicação de importantes obras e artigos; b) introdução de uma nova
linguagem algébrica, no caso, a linguagem da álgebra abstrata com as suas notações e os
conceitos de grupo, anel, ideal, corpo, etc.; c) tentativas de demonstrar a Hipótese de Riemann
que, embora nem sempre bem sucedidas, trouxeram progressos importantes para a teoria analítica
dos números; d) início da preocupação com algoritmos de fatoração e testes de primalidade para
serem utilizados em grandes números (Lehmer); e) início da busca por grandes números primos
utilizando computação. Cabe ressaltar que o maior número primo encontrado antes do surgimento
da computação eletrônica foi realizado pelo matemático francês Édouard Lucas, em 1876.
,é
Utilizando um método desenvolvido por ele, confirmou que o número de Mersenne
primo. Este número possui 39 algarismos (Sautoy, 2007. p. 220).
Os matemáticos que se dedicaram aos números nesse tempo são relativamente poucos: Edmund
Georg Hermann Landau (1877 - 1938), Godfrey Harold Hardy (1877 - 1947), John Edensor
Littlewood (1885 - 1977), Srinivasa Aiyangar Ramanujan (1887 – 1920), André Weil (1906 1998), Alan Mathison Turing (1912 - 1954) e Derrick Henry Lehmer (1905 - 1991). Ainda
podem se destacados os seguintes matemáticos que, de maneira própria, trabalharam com
números primos: Frank Nelson Cole, (1861 - 1926); Ernst Eduard Kummer (1810 - 1893) e
Helmut Hasse (1898 - 1979),
3.4 Período Atual
Após a segunda metade do século XIX até o início do último quarto do século XX, houve um
relativamente longo interstício, quando os primos continuaram a receber o tratamento usual
dentro da Teoria dos Números, sem trabalhos significativos sobre primalidade e fatoração de
inteiros.
14
Sobre este período Coutinho (Coutinho, 2001) faz algumas importantes constatações: a) todos os
fundamentos matemáticos utilizados para a definição de algoritmos atuais e sua demonstração já
eram conhecidas desde o século XIX; as inovações são devidas a trabalhos sobre o custo de um
algoritmo, distribuição dos primos em um intervalo e nas aplicações que em grande maioria tem
menos de vinte anos. Os avanços conceituais e técnicos desse período foram o nível de abstração
sobre o conceito de número, linguagem matemática, notação, método e aplicações na área de
computação.
Por conveniência, o momento atual fica definido como o período que começa na década de 70 do
século passado, até o surgimento do Algoritmo AKS no início deste século.
Uma simples revisão histórica sobre o século XX mostra que os primos e os estudos sobre
primalidade continuaram sendo um item de menor importância em matemática.
As coisas só mudaram a partir de década de 70 do século passado, com o surgimento dos
avançados sistemas de computação digital e a criação dos sistemas complexos de criptografia e
chave pública, na década de 80, que passaram a exigir a utilização de grandes números primos.
O surgimento dos sofisticados sistemas de criptografia trouxe um imperativo de ordem prática
para a retomada das pesquisas sobre números primos.
Surgiu a questão P e NP sobre o custo (tempo) de implementação computacional de algoritmos
para teste de primalidade ou geração de séries de primos.
O final deste momento é caracterizado pelo surgimento do algoritmo AKS que tem tudo para ser
um paradigma sobre algoritmos de primalidade e não necessariamente um novo paradigma
relativo aos primos. Só novos desenvolvimentos e pesquisa sobre o assunto poderá dizer se
estamos realmente em um novo momento significativo relativo aos números primos.
Os especialistas envolvidos com pesquisas sobre números primos, no momento atual, podem ser
divididos em dois grupos: matemáticos e cientistas da computação, ou “computer scientist” como
dizem os americanos. A linha que divide estes grupos é muito tênue, pois a maioria deles transita
nas duas áreas. A separação é apenas uma questão de ênfase em relação ao trabalho de cada um.
Outra dificuldade para analisar este período é que ainda não existe o distanciamento histórico
necessário.
3.4.1 Matemáticos
Victor S. Miller - Alan baker - Bryan John Birch - Enrico Bombieri - Paul Cohen - Alain Connes
- Paul Erd s - Martin Gardner - Alexander Grothendieck - Norman Levisohn - Carl Pomerance Paulo Ribenboin - Atle Salberg – Andrew Wiles –Peter Sarnak – Nick Katz
Estes matemáticos têm entre si algumas características em comum:
i. Foram pesquisadores da teoria dos números e da teoria analítica dos números e em
certos momentos de sua carreira estiveram profundamente envolvidos com os
números primos;
15
ii.
iii.
iv.
v.
vi.
vii.
Promoveram avanços técnicos e conceituais importantes, e até mesmo
revolucionários, em relação à linguagem matemática, metodologia e técnicas em
grandes áreas da matemática e teoria dos números;
Estudaram profundamente a função zeta de Riemann;
Realizaram estudos avançados referentes à demonstração da Hipótese de Riemann,
com exceção de André Wiles e Paulo Ribenboin;
Alguns escreveram obras de divulgação sobre números primos; e,
Com exceção de Wiles e Ribenboin, todos os outros transformaram a Hipótese de
Riemann no “Santo Graal” da matemática.
Martin Gardner e Paulo Ribenboin foram também dois excelentes divulgadores de
resultados sobre números primos, o primeiro de forma mais popular e o segundo
utilizando uma matemática mais sofisticada.
3.4.2 Cientistas da Computação
Depois de Turing e von Newman, deve-se a grupos como esses o desenvolvimento do que hoje é
chamado de Matemática Computacional e Ciência da Computação. Mostraram novos rumos e
abriram novos campos de trabalho. São eles por grupos de interesse: Gary L. Miller - Michael
Oser Rabin; Manindra Agrawal – Neeraj Kayal - Nitin Saxena; Ron Rivest – Adi Shamir – Len
Adleman; Victor S. Miller – Neal Koblitz.
3.5 Encerramento dos Períodos Históricos
Esta breve e incompleta história dos números primos tem uma finalidade: analisar o ocorrido e
explorar o futuro.
Além do proselitismo esporádico sobre o assunto, historicamente os números primos têm sido
tratados como simples curiosidades matemática, a não ser em períodos específicos quando
receberam tratamento adequado ao assunto estudado.
Foi assim com os gregos, como instrumento para fatorar medidas geométricas; ocorreu no
momento de Gauss quando foram utilizados apenas como instrumento para avanços na Teoria
dos Números e para a nova Teoria Analítica dos Números; ocorre no momento atual quando
estão sendo utilizados como partes de complexos sistemas de criptografia. Acontece também
com o novíssimo algoritmo AKS. Isto quer dizer que as pesquisas sobre números primos só
conseguem avanços quando demandadas para novas aplicações. Este é o caso do momento atual
com os grandes progressos da computação, digital ou quântica.
Em uma visão histórica do desenvolvimento da matemática, podemos identificar certa
regularidade de fatos quanto ao crescimento da produção em determinadas épocas e áreas. É o
princípio do desenvolvimento e da produção matemática: o desenvolvimento da matemática é
estimulado pela presença de problemas desafiadores, com caráter teórico ou prático, ainda não
solucionados.
16
Com certeza estamos vivendo um desses momentos. Com as precauções necessárias quando se
fala do futuro, talvez possa ser avançada a seguinte conclusão: com o advento do algoritmo AKS
e dos grandes sistemas de computação (inclusive a computação quântica): estamos vivendo um
grande momento da matemática em relação aos números primos. Uma revolução científica no
sentido de T. Khun (Khun, 1982). O prelúdio para o surgimento de novos paradigmas. Estamos
vivendo um novo momento significativo para os números primos.
4. NÚMEROS PRIMOS – EVOLUÇÃO DO CONCEITO
Ao invés de falar sobre conceito ou definição de número primos, talvez seja melhor adotar a idéia
de caracterização de um número primo. Isto é, quando um número primo está bem caracterizado,
dentro de qualquer contexto matemático. Neste sentido a caracterização pode ser feita por uma
definição ou conceito, por uma proposição ou teorema.
Primeira caracterização formal de número natural primo é dada por Euclides, logo no início do
Livro VII dos Elementos. Após definir número, ele introduz o conceito de número composto e
primo. Para Euclides número “composto é aquele que pode ser medido por outro número” e
número primo é “o número que só pode ser medido pela unidade”. O fato é que à época a idéia
de número primo e composto está muito mais ligada ao conceito de múltiplo do que ao conceito
de divisor próprio de um número. Esta pequena distinção é importante como veremos a seguir.
A segunda caracterização para número primo aparece incorporada à cultura matemática européia
já pela época de Fermat. Foi uma evolução conceitual importante, provavelmente devida aos
árabes. Embora de certa forma equivalente ao conceito de Euclides, esta nova caracterização é
muito mais operacional, facilitando operações, experimentações e demonstrações. Ela está
fundamentada na idéia de divisor e divisor próprio de um número. A divisibilidade é a
contrapartida para a multiplicidade utilizada por Euclides. O novo conceito de número primo, até
onde se conseguiu pesquisar, é então utilizado por Fermat, Euler, Legendre, Gauss e outros sem
nenhuma caracterização formal do que seja número primo. É possível inferir, por suas
proposições e conjecturas, que eles já utilizavam a definição forte de número primo como é dada
na atualidade em alguns manuais de teoria dos números:
Um inteiro positivo p > 1 é um número primo, se e somente se, 1 e p são os seus únicos
divisores positivos.
Esta caracterização bi-condicional é fundamental para o desenvolvimento e demonstração de
qualquer proposição sobre números primos, ao contrário da caracterização fraca, muito utilizada
em bons manuais:
Um número inteiro p > 1 possuindo somente dois divisores positivos 1 e p é chamado de primo.
Na época de Fermat, Euler, etc. já era utilizada a caracterização forte para número primo, pois
suas pesquisas e demonstrações exigiam o seguinte: a) dado um número primo p é sabido que
ele tem somente dois divisores positivos, 1 e p ; b) dado um número inteiro n se ele tiver apenas
dois divisores inteiros positivos, 1 e n , então ele é primo.
17
O fato que até hoje não surgiu uma nova caracterização de número primo que pudesse indicar um
progresso teórico e conceitual subvertedor da ordem estabelecida.
Os únicos autores, até onde as pesquisas puderam mostrar, e que se preocuparam indiretamente
com a caracterização para primos foram Ribenboin (Ribenboin, 2001) e Granville (Granville,
2004). A seguir algumas proposições que “em tese“ poderiam dar uma nova caracterização para
um número primo:
1a Caracterização – O Pequeno Teorema de Fermat: Se p é um primo se a é um numero
natural, então a p ≡ a (mod p ) . Em particular, se p não divide a , então a p −1 ≡ 1 (mod p) .
Este teorema seria então uma excelente caracterização de um número primo se sua recíproca
fosse sempre verdadeira. Mas isto não é verdade. Então temos uma caracterização fraca para um
número primo.
2a Caracterização – Teorema de Wilson: Um inteiro p > 1 é um número primo, se e somente se
( p − 1)! ≡ −1 (mod p ) .
Embora este teorema possa caracterizar muito bem um número primo, ele não é utilitário. Devido
à expansão fatorial ele não é prático para testar primalidade ou ser utilizado em processos de
fatoração.
Outra caracterização é sugerida por Ribenboin, mas ele mesmo se pergunta se esta propriedade
realmente caracteriza um número primo.
3a Caracterização – Propriedade de Giuca: Ele parte do Teorema de Fermat e chega, de maneira
fácil como afirma Ribenboin, que 1 p −1 + 2 p −1 + + ( p − 1) p −1 ≡ −1 (mod p) para p primo. Então
ele perguntou se a recíproca é verdadeira, isto é, para n > 1 , e se n divide a expressão
1n−1 + 2 n −1 + + ( p − 1) n−1 + 1 , então n é primo? Para Ribenboin é fácil ver que o natural n
satisfaz a propriedade se, e somente se, p 2 ( p − 1) divide n − p para cada número p dividindo
n . É realmente complicado caracterizar um número primo dessa forma.
4a Caracterização – Função
de Euler: Sabe-se que para p primo ϕ ( p ) = p − 1 . Lehmer
conjecturou que se fosse dado um número composto n , não haveria nenhum n , tal que ϕ (n) ,
dividisse n − 1 .
Esta hipótese ainda não foi demonstrada, e caso seja será uma excelente caracterização de
números primos, totalmente operacional.
Em um de seus artigos Granville (Granville, 2004 p. 4) sugere que o Teorema de Manindra
Agrawal – Neeraj Kayal - Nitin Saxena, que fundamenta o algoritmo AKS, é uma excelente
caracterização (o que não é verdade) para os números primos, afirmando que ela, embora a
primeira vista pareça complicada, na realidade não é.
18
5a Caracterização – Teorema de Manindra Agrawal – Neeraj Kayal - Nitin Saxena: Para um
dado inteiro n ≥ 2 , seja r um inteiro positivo menor que n , para o qual n tem ordem menor que
(log n) 2 modulo r . Então n é primo se, e somente se:
• n não é uma potência perfeita de algum número inteiro;
• n não tem algum fator primo menor ou igual a r ;
• ( x + a ) 2 ≡ x 2 + a (mod n, x r − 1) para cada inteiro a , 1 ≤ a ≤ r log n .
Todas estas caracterizações têm um furo na origem, pois elas utilizam o conceito de primo já
anteriormente definido.
Em termos de uma evolução conceitual revolucionária para os números primos o que é necessário
é uma nova caracterização para números primos, mais abrangente, consistente e operacional. Pois
o fato é que existe um impasse, parecido com o que aconteceu no desenvolvimento histórico da
matemática, forçando o surgimento dos irracionais, dos números negativos e complexos. Desde
Euclides e Fermat não houve nenhum avanço na caracterização dos primos. Nenhuma corrente
matemática ou grupo se preocupou com este aspecto. Uma caracterização avançada de número
primo teria que passar pelo seguinte teste: é de fácil entendimento e operacional; garante as bases
teóricas da teoria dos números; pode ser utilizada para demonstrar o Teorema Fundamental da
Aritmética; melhora o entendimento sobre a distribuição dos primos; pode ser utilizada para
demonstrar conjecturas até hoje não provadas. Mas a questão que antecede é: essa caracterização
existe? A resposta é: ainda não!
5. PRIMALIDADE: TESTES E FUNDAMENTOS
Atualmente existe mais de uma centena de testes de primalidade, cada um deles com uma
fundamentação teórica diferente. São testes determinísticos ou probabilísticos, executados em
tempo polinomial ou tempo exponencial, fundamentados em teoremas ou conjecturas. E assim
por diante. Talvez então seja conveniente tentar estabelecer algum tipo de classificação, por mais
inadequada que ela seja. Só assim é possível estabelecer uma visão mais ordenada sobre o
emaranhado dos testes de primalidade. Uma descrição simples para os testes pode dar uma idéia
da complexidade do assunto. Assim existem testes que:
a)
b)
c)
d)
e)
f)
g)
h)
i)
j)
Levam o nome do autor(res) ou da instituição que os desenvolveram;
É resultado de melhoria de testes anteriores;
São a mistura de vários resultados ou testes anteriores;
São executados em tempo polinomial ou exponencial;
São determinísticos ou probabilísticos;
São aplicados a números genéricos ou a números de forma específica;
São baseados em teoremas ou em conjecturas;
São baseados em congruências ou não;
São executados em um computador ou exigem computadores em rede;
São executados em computadores convencionais ou necessitam um novo tipo de
computador.
19
O campo dos testes de primalidade está ficando cada vez mais amplo e complexo. Talvez fosse
melhor dizer caótico. A título de curiosidade, poderia ser sugerido um sistema mnemônico de
classificação que levasse em conta estas dez categorias.
Na era da matemática computacional, será adotado como principal critério de classificação o
tempo de execução: se tempo polinomial, exponencial ou semi-polinomial. Este critério é
fundamental, pois para testes de grandes números a execução de determinados algoritmos em
tempo exponencial, como por exemplo, um algoritmo fundamentado no teorema de Wilson,
levaria um tempo além de qualquer imaginação ou desejo.
Serão apresentados alguns testes de primalidade mais representativos de sua categoria, conforme
os critérios anteriores. Estes testes podem mostrar que tipo de desenvolvimento conceitual,
técnico ou tecnológico está envolvido em sua concepção. E este é o objetivo. Cabe ressaltar que
os resultados importantes aconteceram na aplicação prática da teoria dos números, e não no
desenvolvimento da teoria. Esta constatação é fundamental para as conclusões que serão obtidas
sobre primalidade.
Na descrição e análise dos testes, a apresentação será na forma: nome do teste, descrição e
fundamentação teórica básica. A preocupação é com a matemática envolvida na fundamentação
dos algoritmos e não no detalhamento e sua demonstração.
5.1 Algoritmo de Fermat
Este exemplo está vinculado à necessidade de Fermat encontrar um processo para fatorar
números relativamente grandes, para a época é claro, ou mostrar sua primalidade. Fermat
desenvolveu dois algoritmos. Um para fatorar um número inteiro qualquer e outro específico para
números de Mersenne. Estes resultados mostram o seu engenho na manipulação dos números.
Segundo Coutinho (Coutinho, 2001 p. 40 e 157), o primeiro método consistia em fatorar um
número utilizando um algoritmo mais ou menos como o descrito em continuação.
Com base em resultados anteriormente estabelecidos ele desenvolveu o processo supondo
inicialmente que:
a) O número n é um inteiro positivo impar, pois se for par tem 2 como fator;
b) Sendo n ímpar podemos notar que pelo teorema anterior n = x 2 − y 2 = ( x − y )( x + y ) ;
c) Então os fatores de n são a = ( x − y ) e b = ( x + y ) .
Então, fazendo y = n x n − n , inicia-se x = [n] , onde [n] é a parte inteira de
n ; este valor é
tomado porque pelo menos um dos fatores, no caso ( x − y ) ≤ n ; então x é incrementado de 1
em 1, até que seja encontrado um valor inteiro para y; logo x =
y 2 + n ; então são encontrados
20
os valores dos fatores a e b . Quando um valor inteiro para y não é encontrado, o número é
n +1
primo, e o algoritmo, neste caso, é finalizado para x =
.
2
Embora não seja, segundo os critérios atuais, um processo em tempo polinomial, era um
algoritmo extremamente forte para as necessidades e possibilidades computacionais daquele
tempo. Cabe ressaltar também que este deve ser o primeiro algoritmo criado para fatorar um
número inteiro ou testar a sua primalidade, além do costumeiro processo da divisão. Novamente
Fermat inovou tecnicamente
5.2 Algoritmo AKS
O algoritmo AKS foi desenvolvido em 2002 por Manindra Agrawal – Neeraj Kayal - Nitin
Saxena. É um teste original e determinístico que exige somente tempo polinomial. Está
fundamentado no pequeno teorema de Fermat e em uma das suas generalizações. Utiliza
congruência entre polinômios e é aplicado a números inteiros genéricos. Pode ser rodado em
computadores comuns com memória suficiente.
O teste está fundamentado na seguinte congruência entre polinômios: Seja a um inteiro e n um
natural, n ≥ 2 e mdc ( a, n) = 1 . Então n é primo se, e somente se, ( x + a) n ≡ x n + a (mod n) .
Como dizem os autores (Manindra Agrawal, Neeraj Kayal e Nitin Saxena, 2002), a identidade
anterior sugere um teste simples de primalidade. Basta testar a congruência para todo o a que não
divide n. Isto leva tempo, pois para n muito grande será necessário testar todo o conjunto cujos
elementos são todos os inteiros a que são relativamente primos com n .
Então a questão é contornar a situação, transformando-a de exponencial em polinomial.
Parafraseando Ribenboin, é fato que técnicos brilhantes inventam artimanhas para abreviarem
etapas. Isto é realizado utilizando o seguinte artifício, que contorna mais ou menos o problema. É
( x + a ) n ≡ x n + a (mod x r − 1, n)
para um pequeno r apropriadamente escolhido. O r é tal que or (n) > log 2 n , onde or (n) é a
ordem de n módulo r , como já foi definido anteriormente. Trocando em miúdos é o seguinte: o
1
+σ
2
valor de r será adequado se r − 1 , contiver um fator primo maior ou igual a r para σ > 0 . O
fato testada a congruência anterior da seguinte forma:é que mesmo que seja encontrada uma
ordem adequada de r a congruência é ainda satisfeita para alguns n compostos com certos
valores de a e r . Isto leva à necessidade de testar vários valores de a .
Sem qualquer desmerecimento ao avanço técnico considerável alcançado com o AKS, o fato é
que ele não trouxe nenhum progresso conceitual. Toda a matemática necessária, linguagem e
notação já estavam desenvolvidas desde o século XIX.
Existe uma conjectura que diz que: Seja r primo que não divide
( x + a ) n ≡ x n + a (mod x r − 1, n) , então n é primo ou n 2 ≡ 1 (mod r ) .
n , e se
21
Se tivessem provado esta conjectura para todos os pares ( n, r ) , o algoritmo seria um salto
conceitual fundamental. Porém existem trabalhos que levantam a hipótese da conjectura ser falsa.
5.3 Teste de Miller
Desenvolvido em 1976, por Gary l. Miller, o teste original é determinístico e executado em
tempo polinomial. É aplicado a qualquer inteiro e está fundamenta na hipótese de Riemann e
pode ser executado em qualquer computador. Em uma de suas formas está baseado em
congruências que definem o conceito de testemunha para um número composto, desenvolvido
por M. Rabin. E para certos números pode ser realizado com uma calculadora.
Teste: “Seja N um inteiro ímpar. Se existir um inteiro a , com mdc ( N , a ) = 1 e
1 < a < 2(log N ) 2 , tal que a seja testemunha para N , então N é composto. Caso contrário N
é primo”.
Um número a a é uma testemunha para N , se satisfizer a condição a N −1 ≡/ 1 (mod N ) .
Logo, se N tem uma testemunha, N é composto.
É difícil ver onde a hipótese de Riemann entra nesta história. Mas, neste caso, é preciso aceitar a
afirmação de Ribenboin (Ribenboin, 2001 p. 102) sobre o assunto. Na realidade Miller mostrou
que qualquer número composto N tem uma testemunha a < 70(log N ) 2 considerando a Hipótese
de Riemann verdadeira. Este algoritmo está fundamentado em conquistas técnicas mais recentes
sobre a hipótese de Riemann. Se provada essa hipótese, então Miller terá conseguido um passo
gigantesco para testes de primalidade.
5.4 O Teste APR
É o teste desenvolvido por Adleman, Pomerance e Rumely em 1983. É resultado de melhoria de
testes como o de Lucas-Lehmer. É considerado um teste inovador que abriu novos caminhos para
testes de primalidade. É determinístico, genérico e executado em tempo semi-polinomial, está
fundamentado em teoremas e congruências e pode ser executado em computadores de velocidade
considerada média. Sobre o algoritmo Ribenboin (Ribenboin, 2001 pp. 102-103) tece as seguintes
considerações:
Com efeito:
(i)
Pode ser aplicado a números naturais N arbitrários, sem necessidade de conhecer os
fatores primos de N − 1 ou de N + 1 .
(ii)
O teste é rigorosamente justificado e, para isso, foi necessário, pela primeira vez nesse
domínio, apelar para resultados difíceis da teoria dos números algébricos; há necessidade
de intervenção de cálculos com as raízes da unidade e da lei de reciprocidade geral do
símbolo de restos de potências. (Notou você que nunca explicamos o significado dessas
noções? A razão é que elas estão muito além do que pretendíamos escrever neste livro!)
(iii)
Seu tempo de execução t ( N ) é quase um polinômio; mais precisamente, existem
constantes efetivamente calculáveis, 0 < C ′ < C , tais que
22
(log N ) C ′ log log log N ≤ t ( N ) ≤ (log N ) C log log log N
O tempo de execução do teste APR deteve o recorde para os testes de primalidade
determinísticos.
É evidente que esta consideração final foi feita antes da chegada do algoritmo AKS.
Pomerance dá uma descrição compreensível (Pomerance, 1981 p. 102), do teste: Seja n número
inteiro que se quer testar a primalidade. Então são calculados os menores quadrados inteiros
f (n) , de tal modo que ∏ q > n onde q é primo. Os fatores primos de f (n) são ditos
q −1 | f ( n )
primos iniciais, e os primos q , com q − 1 | f ( n) , são chamados de primos Euclidianos. É então
verificado se n é dividido por primos não iniciais ou Euclidianos. Se n é composto então ele tem
um fator primo r ≤ n . A dificuldade está em encontrar r . Ver Pomerance (Pomerance, 1981 p.
102).
5.5 Teste de Miller – Rabin
Este teste foi desenvolvido por Gary l. Miller e Michael Oser Rabin. Está fundamentado em
congruências e no pequeno teorema de Fermat. É um teste básico que inaugurou a era dos testes
de primalidade probabilísticos. Sua execução se dá em tempo polinomial e pode ser rodado em
qualquer computador. Pode ser utilizado para qualquer tipo de números inteiros. A seguir uma
descrição muito simples do teste. Na realidade o teste dá a probabilidade de um número inteiro
grande n ser primo. Então é escolhido um número a , como base, no intervalo [ 2, n − 1] .
Escolhido um número a neste intervalo, é verificado se ele é testemunha de n :
i.
a n −1 ≡/ 1 (mod N ) ;
ii.
iii.
Calcula-se o valor d = mdc(a
Verifica-se se 1 < d < N .
N −1
2k
− 1, N ) para um determinado valor de k ;
Se a é aprovado então ele é uma testemunha de N , e N é composto. Se a não for testemunha
1
de N , então N tem probabilidade de
de ser primo. O item (i) é o Pequeno Teorema de
2
Fermat; (ii) e (iii) verificam se N tem um divisor comum com outro número no intervalo (1, N ) .
A probabilidade de N ser um inteiro primo é dada, como pode ser facilmente verificado, por:
r
1
,
p( N ) =
σ
σ =1 2
onde r é a quantidade das bases que não passaram no teste. Então para um teste com 7 bases não
aprovadas como testemunhas, seria encontrada a seguinte probabilidade:
1 1 1 1
1
1
1
9921
p( N ) = + + + +
+
+
≅
2 4 8 16 32 64 128 10.000
Então a probabilidade de N ser primo é de aproximadamente 99,21 %.
23
É evidente, que mesmo esta probabilidade alta pode ser enganosa. Seja o número pseudoprimo
forte, nas bases 2, 3, 5 e 7, (3.215.031.751) = (151)(751)(28351). A probabilidade de que ele
fosse primo é de 93,75 %. Há sempre um risco.
Esta probabilidade surge do Pequeno Teorema de Fermat, para o qual não vale à recíproca. Mas
foi um avanço conceitual interessante, pois introduziu a probabilidade na teoria dos números ou
vice-versa.
A partir deste teste surgiram muitos outros não determinísticos. Este modelo iniciou uma nova
classe de provas. As provas probabilísticas de primalidade.
5.6 Gimps
Great Internet Mersenne Prime Search (GIMPS), foi lançada no início de 1996 por George
Woltman. Antes de ser um teste de primalidade, é na realidade uma busca para encontrar grandes
números primos de Mersenne e a fatoração de números de Mersenne em geral. É fundamentado,
basicamente, nas provas de primalidade de Lucas – Lehmer. É evidentemente executado em
tempo exponencial. Usa computação distribuída em rede pela Internet, comandada por um
computador central.
Como já foi dito o teste usa uma associação de provas de primalidade, utilizando a seguinte
estratégia:
i.
ii.
iii.
Gera uma base de dados com Números de Mersenne;
Emprega um “mix” de provas de primalidade e busca fatores para n + 1 e n − 1 ;
Testa a primalidade ou encontra os fatores para um dado número de Mersenne.
Este trabalho não produz nenhum avanço conceitual em termos de números primos. Em relação à
teoria dos números é uma mera curiosidade. Permite, porém uma visão ampla sobre a distribuição
dos números primos em termos dimensionais. Para a computação algébrica é um avanço
considerável, em termos conceituais e técnicos, com a utilização de computação distribuída,
criando e desenvolvendo novas técnicas.
5.7 Ecpp
ECPP significa, em inglês “ellipitc curve primality proving”. Foi desenvolvido por A. O. L.
Atkin e F. Morain em 1993, no artigo Ellipitc Curves and Primality Proving. Teste de
primalidade modelo, criou uma nova classe de avaliação de primalidade de um número.
Totalmente justificado utilizando curvas elípticas sobre corpos finitos. É determinístico, aplicável
a qualquer inteiro e executado em provável tempo polinomial. Pode ser executado em
computadores comuns. Apresenta resultados intermediários cuja lista é chamada de certificado de
primalidade para um determinado número primo testado. A extensão e complexidade técnica do
artigo (Atkin, et al., 1993), impede que seja realizada uma análise resumida e mais acurada do
24
teste de primalidade. Na conclusão do artigo os autores tecem algumas considerações importantes
(Atkin, et al., 1993 pp. 38-39):
i. O algoritmo utiliza a teoria das curvas elípticas com multiplicação sobre corpos
finitos;
ii. O algoritmo tem complexidade polinomial, e possui excelente desempenho
prático, pois demonstra a primalidade de números de 100 a 1.5000 algarismos;
iii. Ele realiza o teste para um número de até 400 dígitos, em poucos dias, utilizando
uma estação de trabalho simples;
iv. Para números de mais de 800 dígitos é utilizado processamento distribuído em dez
estações de trabalho e gasta um tempo real de uma semana;
Assim é sugerida a seguinte estratégia para um computador com uma determinada velocidade
média de processamento:
1. Peneiramento e posterior fatorização dos números de pontos da curva;
2. Utilizar exponenciação módulo p ;
3. Exponenciação de uma curva elíptica módulo p ;
4. Solução de polinômios utilizando congruências módulo p ;
A análise matemática deste teste de primalidade está além das possibilidades deste artigo. A
dificuldade para analisar este tipo de prova é que em sua concepção é utilizada uma linguagem
matemática bastante atual e sofisticada. O grande avanço conceitual e técnico conseguido pelos
autores é a introdução das curvas elípticas no estudo dos números primos e a utilização de
linguagem e resultados mais atuais sobre álgebra abstrata e sua aplicação à teoria dos números. O
ECPP criou uma nova classe de testes de primalidade. As provas de primalidade utilizando
curvas elípticas. Mas não deixou de utilizar congruências.
5.8 Algoritmo de Fatoração de Shor
P. Shor (Shor, 1994) apresentou o seu algoritmo para fatoração em computadores quânticos em
artigo de 1994. É um algoritmo de fatoração e não para testes de primalidade. Foi elaborado para
ser processado em um computador quântico, cujas bases teóricas já estão postas. Trabalha com
complexidade polinomial. Aqui é colocado como uma interessante perspectiva, pois por este
algoritmo qualquer número composto pode ser fatorado dentro de uma probabilidade
suficientemente segura. É então uma metodologia probabilística. A questão do computador
quântico não está só na velocidade de processamento, mas principalmente na forma de processar,
neste caso, chamada de superposição quântica. O passo quântico utilizado no algoritmo é a
realização de uma Transformada Discreta de Fourier. As bases matemáticas do algoritmo são
relativamente simples. Segue a descrição e fundamentos matemáticos do método. Esta análise
está baseada no artigo de Ekert e Jozsa (Ekert, et al., 1996 pp. 740-742;750-751).
Matematicamente o algoritmo está basicamente fundamentado em uma definição e duas
proposições aqui colocadas de forma elementar, onde n é o número impar que se pretende
fatorar:
25
Definição. O valor r é definido como a ordem de x , módulo n . Então r é o período da função
f (a) ≡ x a (mod n) que define a seqüência
x 0 (mod n), x 1 (mod n), x 2 (mod n), , x a (mod n),
O período da função é a parte “quântica” do algoritmo. Ele é encontrado, segundo Ekert, em
tempo polinomial, utilizando uma versão quântica da transformada discreta de Fourier. Aliás, esta
é toda a base do algoritmo, encontrar o período r da função f (a ) , com alta probabilidade de
acerto.
Proposição A. Sendo r o menor valor de a > 0 , tal que x a ≡ 1 (mod n) e se para r par,
r
2
r
2
x ≡/ −1 (mod n) , então d = mdc( x − 1, n) , é um fator de n .
Lembrando que o valor provável de a foi encontrado utilizando a TDF.
r
Proposição B. A probabilidade p de que r seja par e x 2 ≡/ ±1 (mod n) , é dada por
1
p ≥ 1 − k −1 , onde k o número de fatores primos de n .
2
Um exemplo pode ajudar no entendimento do algoritmo. Seja o número, pequeno é claro, n = 15 .
Seus fatores são 3 e 5, é claro.
1º. Passo: escolher aleatoriamente valores de y tais que 1 ≤ y ≤ 15 até encontrar y
tal que mdc ( y, n) = mdc ( y , 15) = 1 . Esta probabilidade é maior ou igual a
1
1
=
= 0,37 . Na realidade é preciso escolher um número do conjunto
log n log 15
{2,4,7,8,11,13,14}. A probabilidade da escolha de um número no conjunto é 0,46.
2º. Passo: Supondo que o valor de y selecionado seja y = 11 , o mdc (11, 15) = 1 . A
ordem de r , para
f (1) ≡ 111 (mod 15) = 11 ,
y = 11 é dada por:
f (2) ≡ 112 (mod 15) = 1 ,
f (3) ≡ 113 (mod 15) = 11 ,
f (4) ≡ 114 (mod 15) = 1 .
Então a ordem de r é dada pela seqüência: {11, 1, 11, 1, 11, 1, } . Logo r = 2 .
30.
r
2
Passo: Fazendo x = y 2 = 11 2 = 11 . Calculando o mdc ( x ± 1, 15)
mdc (10, 15) = 5 e mdc (12, 15) = 3 . Então 3 e 5 são os dois fatores de 15.
fica:
Calculando a ordem de todos os elementos de {2,4,7,8,11,13,14}, fica, respectivamente, {4, 2, 4,
4, 2, 4, 2}.
26
r
2
Por curiosidade, seja y = 14 , então x = y 2 = 14 2 = 14 . Mas, 14 ≡ −1 (mod 15) . Então o teste
falha para 14, mas não falha para as outras bases. A probabilidade do teste não falhar é maior que
0,5. Na realidade é 0,85.
Este é um método de fatoração complexo, mas como afirma o autor, tem tempo polinomial para
um computador quântico. É evidente um processo que exige um computador do tipo especial,
pois conforme os artigos consultados, o cálculo do mdc é feito pelo algoritmo de Euclides. Isto
leva tempo, muito tempo.
Neste tópico foram apresentados vários algoritmos, representantes mais importantes de sua
classe. Na realidade eles representam, sinteticamente, o estado da arte sobre o assunto. Foram
constatados grandes avanços técnicos e tecnológicos, mas poucos avanços conceituais de relevo.
6. CONCLUSÃO
Neste momento é interessante repetir André Weil, quando se referindo à matemática afirma:
“A estratégia, por sua vez, consiste na arte de reconhecer os problemas principais, atacá-los em seus
pontos fracos, e estabelecer linhas-mestras para o avanço posterior. A estratégia matemática lida com
objetivos em longo prazo: requer uma profunda compreensão das tendências mais amplas, e da evolução
nas idéias no decorrer de longos períodos de tempo.”
Então vale o seguinte dito: a matemática de hoje é o que foi a matemática de ontem e o que
pretende ser a matemática do amanhã.
A hipótese inicial deste artigo foi estabelecida da seguinte maneira: é possível estabelecer um
percurso factível de estudo e pesquisa sobre testes de primalidade. A busca por um roteiro foi
procurada de duas maneiras: a) levantando o estado da arte sobre o assunto, ao longo do tempo;
b) fazendo uma verificação sistemática dos avanços conceituais, técnicos e tecnológicos. Então
um programa de estudo e pesquisas sobre o assunto podem contemplar três áreas, já definidas
anteriormente como categorias:
Avanços conceituais
a) Busca por uma nova caracterização para números primos; o desenvolvimento dos
conceitos de número negativo, número irracional e número complexo é uma
comprovação desse tipo de necessidade e mostra a possibilidade; assim a teoria
dos números tomaria novos rumos e muitas conjecturas ainda não demonstradas
seriam provadas; os avanços conceituais sobre o significado de números primos e
composto dentro da Teoria Analítica dos Números e da Análise Complexa, são
caminhos já iniciados por Euler, Gauss e Riemann, e até onde foi possível
verificar, relativamente abandonados (Boyer, 1974). Este parece o caminho mais
promissor, tendo em vista que a Hipótese de Riemann consta como um dos
Problemas do Milênio (Devlin, 2004);
b) Comprovação ou não da hipótese de Riemann;
27
c) Criação de uma classe de algoritmos para prova de primalidade, utilizando uma
caracterização adequada de números primos e compostos, envolvendo métodos e
técnicas matemáticas facilmente computáveis; o algoritmo AKS é uma evidência
dessa possibilidade;
d) Desenvolver métodos de fatoração fundamentados na simplicidade computacional
e não na complexidade matemática, pois hoje a sofisticação da linguagem
matemática está chegando antes da plausibilidade; complexidade de linguagem
não é necessariamente indicativo de profundidade matemática; sofisticação não é
sinônimo de abstração;
Avanços Técnicos
Os avanços técnicos sobre testes de primalidade e fatoração de inteiros, cujas bases já estão
postas, exigindo somente bastante aprofundamento, visão e uma intuição certa, devem
provavelmente acontecer em duas áreas:
i. na matemática, em relação à computação quântica, cuja base teórica está pronta;
em relação a algoritmos de fatoração e testes de primalidade e que pressupõe a
computação quântica como base. São tipos de algoritmos que precisam de uma
atenção maior da matemática, evitando somente o uso da força bruta, por exemplo,
o algoritmo de Shor;
ii. no progresso técnico com base nas estruturas conceituais existentes que tem como
exemplo o Algoritmo AKS. É provavelmente a intuição de Coutinho (Coutinho,
2004) quando especula:
“De fato, a simplicidade deste algoritmo (AKS) traz à tona uma pergunta ainda mais
importante, e que pode ser o prenúncio de grandes resultados que estão por vir. Que outros
algoritmos, igualmente simples, ainda não fomos bastante espertos para descobrir?”
Avanços Tecnológicos
No desenvolvimento da matemática, está comprovado pela história recente, que avanços
tecnológicos importantes conduzem avanços na área, também importantes. Neste caso, antever os
progressos tecnológicos, é uma forma de definir um programa de trabalho na área dos números
primos e metodologias de fatoração de inteiros.
Para encerrar, referindo-se à obra de Laplace, suas posições políticas e ao imediatismo prático na
matemática, Boyer (Boyer, 1974) coloca de forma bela e incontestável o seguinte:
“Uma lição que se pode tirar é que as coisas que realmente contam na matemática e que têm
influência duradoura, não são as que se inspiram em um utilitarismo imediatista. Mesmo em
tempos de crise são as coisas do “espírito” (no sentido francês) que mais contam, e essas são talvez
melhor transmitidas pelos grandes mestres”.
E a luta continua!!
28
REFERÊNCIAS BIBLIOGRÁFICAS
AGRAWAL, Manindra, KAYAL, Neeraj e SAXENA, Nitin. Primes is in P. Disponível em
<http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf> Acesso em: 04 jun. 2008.
ATKIN, A. O. L.; MORAIN F. Elliptic curves and primality proving. Math. Comp. 61, 203, p. 29-68, 1993.
Disponível em < http://www.lix.polytechnique.fr/~morain/Articles/articles.english.html> Acesso em: 7 jun. 2008.
BOMBIERI, Enrico. The Riemann hypoteses. Clay Mathematics Institute: J. Carlson A. Jaffe and A. Wiles., 2000.
Disponível em <http://www.claymath.org/millennium/> Acesso em: 16 maio 2008.
BOYER, Carl B. História da matemática. Tradução: Elza F. Gomide. São Paulo: Edgard Blucher Ltda., 1974. 488
p.
COUTINHO, S. C. Números inteiros e criptografia RSA. 2. ed. Rio de Janeiro: IMPA, 2001. 213 p.
COUTINHO, S. C. Primalidade em tempo polinomial: uma introdução ao algoritmo AKS. Rio de Janeiro:
Sociedade Brasileira de Matemática, 2004. 105 p.
DEVLIN, Keith. Os problemas do milênio. Tradução: Michelle Dysman. Rio de Janeiro: Record, 2004. 308 p.
EKERT, Artur; JOZSA, Richard. Quantum computation and Shor's factoring llgorithm. Reviews of modern
phisics, julho de 1996. Vols. 68, número 3. p. 733-753.
EUCLIDES. Elementos de geometria. Tradução: Frederico Commandino. São Paulo: Edições Cultura, 1944. Vol.
1. Adicionados e ilustrado por Roberto Simsom, professor de Matemática da Academia de Glasgow, Escócia..
EVES, Howard. Introdução à história da matemática. Tradução: Higyno H. Domingues. Campinas: Editora da
UNICAMP, 2004. 844 p.
GRANVILLE, Andrew. It is eeasy to determine whether a given integer. Bulletin (New Series) of the American
Mathematical Society, 2004. 1: Vol. 42. p. 3-38.
IFRAH, Georges. Os números: história de uma grande invenção. Tradução: Stella Maria de Freitas Senra. 2. ed. Rio
de Janeiro: Globo S.A., 1989. 368 p.
JOYCE, D. E. Euclide's elements. Ed. University Dept. Math. & Comp. Sci. Clark. 1997. Disponpivel em
<http://aleph0.clarku.edu/~djoyce/java/elements/elements.html> Acesso em: 6 abr. 2008.
KHUN, Thomas S. A estrutura das revoluções científicas. 3. ed. São Paulo: Perspectiva, 1982. 257 p.
LANDAU,
Edmund.
The
master
rigorist.
Princeton
University.
Disponível
em
<http://press.princeton.edu/books/maor/sidebar_h.pdf> Acesso em: 30 maio 2008.
LEGENDRE, A. M. (Adrien Marie). Essai sur la théorie des nombres. Paris: Duprat Paris [University of California
Libraries]. 1798. Primeira. Vol. 1. Disponível em <http://www.archive.org/details/essaitheorienomb00legerich>
Acesso em: 21 maio 2008.
O'CONNOR, e ROBERTSON, Edmund F. MacTutor history of matemátics archive. School of Mathematics and
Statistics
–
University
of
St
Andrews,
Scotland.
2008.
Disponível
em
<http://wwwhistory.mcs.stAndrews.ac.uk/Indexes/HistoryTopics.html> Acesso em: 7 abr. 2008.
POMERANCE, Carl. Recent developments in primality testing. The Mathematioal Intelligenaer, 1981. Vol. 3. p.
97-105.
RIBENBOIN, Paulo. Números primos: mistérios e recordes. Rio de Janeiro: IMPA, 2001. 280 p.
RIPOLL, Jaime Bruck; RIPOLL, Cydara Cavedon; da SILVEIRA, José Francisco Porto. Números racionais, reais
e complexos. Porto Alegre: Universidade Federal do RGS, 2006. 340 p.
SAUTOY, Marcus du. A música dos números primos: a história de um problema não resolvido na matemática.
Tradução: Diego Alfaro. Rio de Janeiro: Jorge Zahar Editora, 2007. 352 p.
SHOR, P. Algorithms for quantum computation: discrete algarithms and factoring. Anais da 35th Annual
Symposium on Foundations of Computer Science. Santa Fe, USA: IEEE Comput Soc. Press, 1994. p. 124-134.
José Aluizio Ferreira Lima ([email protected])
Curso de Matemática, Universidade Católica de Brasília
EPCT – QS 07 – Lote 01 – Águas Claras – Taguatinga – CEP.: 72966-700
29