Testes de Primalidade

Prévia do material em texto

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 nosElementos 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 sendoum 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: 
� ∏∞
=
−
==
1
11
11)(
n p
s
s
p
n
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±=��
�
�
��
�
�
q
p
, 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)( −= nnnpi para 
n crescendo indefinidamente. A função )(npi é 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)()(
nn
n
nD ≅= pi . 
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 Gaussquem 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 teoriados 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+
=
n
x . 
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 
σ+
2
1
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 ≤ . Adificuldade 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( 2
1
Namdcd k
N
−=
−
 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 
2
1
 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
Np
1 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.10
9921
128
1
64
1
32
1
16
1
8
1
4
1
2
1)( ≅++++++=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 nx
r
−≡/ , então ),1( 2 nxmdcd
r
−= , é 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 nx
r
±≡/ , é dada por 
12
11
−
−≥ kp , 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,0
15log
1
log
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 11112
2
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 2
2
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. Adicionadose 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