Nosso objetivo nestas notas é apresentar um importante resultado de complexidade computacional descoberto em meados do primeiro semestre de 2002 pelos indianos Manindra Agrawal, Neeraj Kayal e Nitin Saxena. Muita coisa tem sido comentada sobre esse resultado que está relacionado a códigos criptográficos (ver RPM 12/01) de segurança usados em comunicações por computadores, levantando grande preocupação por parte dos usuários desses códigos. A verdade é que essa descoberta não afeta imediatamente essa segurança: os algoritmos de criptografia não dependem apenas de saber se um número é primo, mas do conhecimento dos fatores primos de números muito grandes, o que é um problema bem mais complicado.

Tentaremos mostrar algumas idéias elementares sobre o resultado dos matemáticos indianos. Para isso apresentamos algumas preliminares:

O nome complexidade computacional indica a disciplina que se preocupa, entre outras coisas, com o tempo gasto por um computador teórico para executar uma tarefa (algoritmo). Apesar de ser teórico, tal computador modela muito bem o que um computador real faz. De certo modo, as contas que fazemos à mão podem modelar esse computador.

Por exemplo, quando somamos dois números no papel, escrevemo-los um abaixo do outro e somamos algarismo por algarismo.

O leitor pode tentar calcular o tempo (em número de passos) gasto em várias operações com números. Considera-se um passo: soma de dois algarismos; subtração de dois algarismos; produto de dois algarismos. Também na comparação de dois números (maior, menor, igual, diferente), feita algarismo por algarismo, cada comparação é um passo.

O computador também trabalha assim e a complexidade de algum algoritmo (ou programa) é função do tamanho, em algarismos ou letras, dos dados de entrada. Como existem passos iniciais irrelevantes para a análise, essa função descreve o comportamento assintótico do algoritmo, ou seja, quanto tempo ele gasta, aproximadamente, quando os dados de entrada são muito grandes.

Os algoritmos considerados mais práticos são os que terminam depois de no máximo P(m) passos, sendo P(x) um polinômio (de grau baixo) e m é o número de símbolos (algarismos) usados para representar os dados do número de entrada.

Um problema computacional, que sempre foi muito importante, é decidir se um número é primo ou não e o algoritmo mais antigo para isso é o chamado de crivo de Erastótenes, que lista todos os números de 1 até N e vai eliminando da lista os múltiplos de cada um deles (ou pelo menos de todos os números até ). Esse é um algoritmo muito lento (imagine decidir se um número de 40 algarismos é primo ou não assim!) e, com o desenvolvimento da Teoria dos Números, foram sendo descobertos outros, mas nenhum deles demorava um tempo polinomial na quantidade de algarismos do número.

O algoritmo descoberto pelos matemáticos indianos faz exatamente isso: decide se um número N é primo ou não em tempo polinomial no tamanho do número em algarismos, isto é, com um número de passos que pode ser estimado calculando-se o valor de um polinômio P(m), m sendo o número de algarismos do número  N.  O algoritmo ainda não está numa forma extremamente eficiente, pois o polinômio que determina seu tempo de execução é de grau muito alto (pelo menos 12). Agora é uma questão de tempo para se chegar a algoritmos cada vez mais eficientes.

Os leitores interessados em ler o artigo original podem buscá-lo no sítio http://www.cse.iitk.ac.in/news/primality.html  e também consultar http://fatphil.org/maths/AKS/  para análises e detalhes sobre esse resultado e outros correlatos.  

Existem infinitos números primos?

A resposta SIM já foi dada por Euclides, com sua magnífica demonstração, publicada várias vezes pela RPM (veja, por exemplo, RPM 11,   p. 5, ou RPM 47, p. 36). Apresentaremos aqui uma outra demonstração bastante interessante, embora muito mais complicada que a de têm, na sua decomposição em primos, apenas o primo 2, é convergente.  Conseqüentemente, se

termos positivos, podem-se agrupar parcelas ou trocar a sua ordem à vontade, sem que isso altere a sua convergência ou divergência, ou o seu valor, caso seja convergente.

Continuando com o processo, obtemos que a série dos inversos dos naturais,  n,  que contém em sua decomposição em primos apenas os  m  primeiros primos  2, 3, 5, ,  é convergente.

Se existisse apenas um número finito de primos, 2, 3, 5, ,  qualquer natural  n  se n,  que contém em sua decomposição em primos apenas os  m  primeiros primos 2, 3, 5, ;  logo, seria convergente. Como chegamos a uma contradição, o número de primos não pode ser finito.

Agora, falando sério: o argumento anterior, que é de Euler (cerca de 1748), deu início à chamada “Teoria Analítica dos Números”, onde a aplicação de argumentos de Análise a questões de Aritmética (envolvendo apenas números inteiros) revelou resultados profundos, como, por exemplo, o fato de que a probabilidade de encontrar um número primo entre 1