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 José Aluizio Ferreira Lima - Licenciando em Matemática 2 Orientador

2

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

3

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

4

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

5

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.

6

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 co-primos, 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.

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.

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 ABa =1 e

2aCD = , onde, é claro, CDAB > . Então o primeiro passo é subtrair repetidamente 2a de 1a , até encontrar um novo número (resto) 3a ( AF ) menor que 2a . Algebricamente, na notação de hoje, fica assim: 3211 aama += , onde 1m é o número de vezes que o 2a foi subtraído de 1a . Este passo subtraí repetidamente 3a de 2a deixando um resto 4a (CG ): 4322 aama += , etc. Pela hipótese desta proposição, o algoritmo para quando a sobra é 1 (unidade no sentido de Euclides): 111 += −− nnn ama . No caso AH que coincide com E dado como a unidade. Nesta prova de Euclides a unidade (1) é o 5a . 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.

7

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

8

é 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.”

9

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.

10

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 PERÍODO TRABALHOS REALIZADOS

Fermat, P. 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 , )(mod paa 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

11

primos, utilizados em larga escala na computação e criptografia.

Mersenne 1588-1648

Conjecturou que todo número da forma 12 −= pM é 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.

Goldbach 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.

Euler 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: 1)( −maϕ é 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:

� ∏∞

= −==

11

1

11)(

n ps

s

pn

sζ , onde o segundo membro é tomado para p primo e

1>s é 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, )(mod1)!1( pp −≡− .

Legendre 1752-1833

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,

utilizando como notação o conhecido símbolo de Legendre: 1±=���

����

�

qp

, se o inteiro

p co-primo com q seja (no caso positivo) ou não (no caso negativo) o resto

quadrático da congruência )(mod2 qpx ≡ . Legendre também estabeleceu uma

conjectura sobre a distribuição dos números primos: )08366,1/(ln)( −= nnnπ 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 é

assintoticamente igual ao inverso do logaritmo de n . Isto é: )ln(

1)()(

nnn

nD ≅= π.

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

12

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.

13

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. Um número inteiro a é divisível por b quando mba = , sendo m um inteiro;

ii. Um número inteiro a é composto quando ele é divisível por outro inteiro diferente de 1 e dele mesmo;

iii. 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

14

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.

15

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;

16

ii. 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;

iii. Estudaram profundamente a função zeta de Riemann; iv. Realizaram estudos avançados referentes à demonstração da Hipótese de Riemann,

com exceção de André Wiles e Paulo Ribenboin; v. Alguns escreveram obras de divulgação sobre números primos; e,

vi. Com exceção de Wiles e Ribenboin, todos os outros transformaram a Hipótese de Riemann no “Santo Graal” da matemática.

vii. 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.

17

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 1>p é 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 1>p 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.

18

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 )(mod paa p ≡ . Em particular, se p não divide a , então )(mod11 pa 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 1>p é um número primo, se e somente se

)(mod1)!1( pp −≡− .

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 )(mod1)1(21 111 pp ppp −≡−+++ −−−

� para p primo. Então ele perguntou se a recíproca é verdadeira, isto é, para 1>n , e se n divide a expressão

1)1(21 111 +−+++ −−− nnn p� , então n é primo? Para Ribenboin é fácil ver que o natural n

satisfaz a propriedade se, e somente se, )1(2 −pp divide pn − 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 1)( −= ppϕ . Lehmer conjecturou que se fosse dado um número composto n , não haveria nenhum n , tal que )(nϕ , dividisse 1−n . 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 é.

19

5a Caracterização – Teorema de Manindra Agrawal – Neeraj Kayal - Nitin Saxena: Para um dado inteiro 2≥n , seja r um inteiro positivo menor que n , para o qual n tem ordem menor que

2)(log n 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 ; • )1,(mod)( 22 −+≡+ rxnaxax para cada inteiro a , nra log1 ≤≤ .

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) Levam o nome do autor(res) ou da instituição que os desenvolveram; b) É resultado de melhoria de testes anteriores; c) São a mistura de vários resultados ou testes anteriores; d) São executados em tempo polinomial ou exponencial; e) São determinísticos ou probabilísticos; f) São aplicados a números genéricos ou a números de forma específica; g) São baseados em teoremas ou em conjecturas; h) São baseados em congruências ou não; i) São executados em um computador ou exigem computadores em rede; j) São executados em computadores convencionais ou necessitam um novo tipo de

computador.

20

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 ))((22 yxyxyxn +−=−= ; c) Então os fatores de n são )( yxa −= e )( yxb += .

Então, fazendo n n nxy −= , inicia-se ][nx = , onde ][n é a parte inteira de n ; este valor é

tomado porque pelo menos um dos fatores, no caso nyx ≤− )( ; então x é incrementado de 1

em 1, até que seja encontrado um valor inteiro para y; logo nyx += 2 ; então são encontrados

21

os valores dos fatores a e b . Quando um valor inteiro para y não é encontrado, o número é

primo, e o algoritmo, neste caso, é finalizado para 2

1+= nx .

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, 2≥n e 1),( =namdc . Então n é primo se, e somente se, )(mod)( naxax nn +≡+ . 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. É

),1(mod)( nxaxax rnn −+≡+ para um pequeno r apropriadamente escolhido. O r é tal que nnor

2log)( > , onde )(nor é a ordem de n módulo r , como já foi definido anteriormente. Trocando em miúdos é o seguinte: o

valor de r será adequado se 1−r , contiver um fator primo maior ou igual a σ+

21

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 n , e se

),1(mod)( nxaxax rnn −+≡+ , então n é primo ou )(mod12 rn ≡ .

22

Se tivessem provado esta conjectura para todos os pares ),( rn , 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 1),( =aNmdc e

2)(log21 Na << , 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 )(mod11 Na 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 2)(log70 Na < 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 1−N ou de 1+N . (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 )(Nt é quase um polinômio; mais precisamente, existem constantes efetivamente calculáveis, CC <′<0 , tais que

23

NCNC NNtN loglogloglogloglog )(log)()(log ≤≤′ 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

)(nf , de tal modo que ∏−

>)(|1 nfq

nq onde q é primo. Os fatores primos de )(nf são ditos

primos iniciais, e os primos q , com )(|1 nfq − , 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 nr ≤ . 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 ]1,2[ −n . Escolhido um número a neste intervalo, é verificado se ele é testemunha de n :

i. )(mod11 Na n ≡/− ;

ii. Calcula-se o valor ),1( 21

Namdcd kN

−=−

para um determinado valor de k ; iii. Verifica-se se Nd <<1 .

Se a é aprovado então ele é uma testemunha de N , e N é composto. Se a não for testemunha

de N , então N tem probabilidade de 21

de ser primo. O item (i) é o Pequeno Teorema de

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

Np1 2

1)(

σσ ,

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:

000.109921

1281

641

321

161

81

41

21

)( ≅++++++=Np

Então a probabilidade de N ser primo é de aproximadamente 99,21 %.

24

É 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. Gera uma base de dados com Números de Mersenne; ii. Emprega um “mix” de provas de primalidade e busca fatores para 1+n e 1−n ;

iii. 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

25

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:

26

Definição. O valor r é definido como a ordem de x , módulo n . Então r é o período da função )(mod)( nxaf a≡ que define a seqüência

�� ),(mod,),(mod),(mod),(mod 210 nxnxnxnx a

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 )(af , com alta probabilidade de acerto. Proposição A. Sendo r o menor valor de 0>a , tal que )(mod1 nx a ≡ e se para r par,

)(mod12 nxr

−≡/ , então ),1( 2 nxmdcdr

−= , é um fator de n . Lembrando que o valor provável de a foi encontrado utilizando a TDF.

Proposição B. A probabilidade p de que r seja par e )(mod12 nxr

±≡/ , é dada por

121

1 −−≥k

p , onde k o número de fatores primos de n .

Um exemplo pode ajudar no entendimento do algoritmo. Seja o número, pequeno é claro, 15=n . Seus fatores são 3 e 5, é claro.

1º. Passo: escolher aleatoriamente valores de y tais que 151 ≤≤ y até encontrar y tal que 1)15,(),( == ymdcnymdc . Esta probabilidade é maior ou igual a

37,015log

1log

1 ==n

. Na realidade é preciso escolher um número do conjunto

{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 11=y , o 1)15,11( =mdc . A

ordem de r , para 11=y é dada por: 11)15(mod11)1( 1 =≡f , 1)15(mod11)2( 2 =≡f , 11)15(mod11)3( 3 =≡f , 1)15(mod11)4( 4 =≡f .

Então a ordem de r é dada pela seqüência: },1,11,1,11,1,11{ � . Logo 2=r .

30. Passo: Fazendo 111122

2 ===r

yx . Calculando o )15,1( ±xmdc fica: 5)15,10( =mdc e 3)15,12( =mdc . Então 3 e 5 são os dois fatores de 15.

Calculando a ordem de todos os elementos de {2,4,7,8,11,13,14}, fica, respectivamente, {4, 2, 4, 4, 2, 4, 2}.

27

Por curiosidade, seja 14=y , então 1414 22

2 ===r

yx . Mas, )15(mod114 −≡ . 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;

28

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!!

29

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://www-history.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 (aluiziodf@hotmail.com) Curso de Matemática, Universidade Católica de Brasília EPCT – QS 07 – Lote 01 – Águas Claras – Taguatinga – CEP.: 72966-700