Testes de Primalidade: Uma Visão Computacional

Quem me acompanha de perto sabe que no último dia 14 de dezembro apresentei meu Trabalho de Graduação (TG), a última etapa para a conclusão do curso. Como gosto muito de teoria e já havia feito uma Iniciação Científica estudando testes de primalidade, resolvi explorar este tema no TG. No trabalho, dou uma “pincelada” em vários testes que foram utilizados ao longo da história, e finalmente chego no AKS e suas melhorias. Para quem não está acostumado com o tema, o AKS é o primeiro teste de primalidade determinístico e de tempo polinomial, desenvolvido por pesquisadores indianos em 2001.

Ele disse provavelmente!

Ah, qual é? Teoria pode ser legal!

Não irei neste post escrever sobre os testes, para isso, quem tiver interesse, pode ler meu trabalho. Aqui irei apenas descrever sobre o que falei no trabalho e fazer uma pequena propaganda da simples ferramenta que desenvolvi e disponibilizei online com código-aberto, e que procuro colaboradores com interesse na área.

O documento que pode ser acessado pelo link acima, inicia-se com uma introdução ao conceito dos números primos e também um breve histórico do tema. Depois, apresento noções básicas de alguns tópicos necessários para a compreensão do trabalho, como aritmética modular e complexidade computacional.

Com o leitor preparado, inicio a exposição dos testes de primalidade. Escolhi a ordem cronológica para organizar os testes, assim, comecei da simples divisão por tentativa, que aprendemos ainda no ensino fundamental (tentar dividir o número sendo testado até encontrar um divisor. Se não encontrarmos um divisor, então o número é primo), até o AKS. Os testes abordados no trabalho são:

  • Divisão por Tentativa
  • Crivo de Eratóstenes
  • Teste de Primalidade de Fermat
  • Teste de Lucas-Lehmer
  • Teste de Solovay-Strassen
  • Teste de Miller-Rabin
  • Teste de Baillie, Pomerance, Selfridge e Wagstaff (Baillie-PSW ou B-PSW)
  • Teste de Adleman-Pomerance-Rumely (APR)
  • Elliptic Curve Primality Proving (ECPP)
  • Algoritmo AKS

Com exceção de APR e ECPP, sobre os quais escrevi muito pouco, todos os outros testes são descritos em suas seções através de uma visão geral de seu funcionamento seguidos de informações sobre sua complexidade computacional. O AKS recebeu um capítulo inteiro, que trata em detalhes do algoritmo e de seu custo, além da descrição de algumas das melhorias propostas desde sua divulgação.

Tela de Resultados da Ferramenta de Comparação. Teste para um número não muito grande (2345678917), mostrando como a Divisão por Tentativa é demorada em relação a outros testes.

Por fim, escrevi uma pequena ferramenta, hospedada no CodePlex, com a implementação de vários testes. Desenvolvida em C#, ela permite ao usuário executar diferentes testes de primalidade e comparar sua performance através de um gráfico. A ferramenta pode ser útil para facilitar o entendimento de alunos em assuntos da Matemática Discreta e da Complexidade Computacional.

Minha intenção com esta ferramenta é o uso puramente didático. Performance decididamente não é o objetivo, pois desejo manter o código limpo, de fácil leitura para alunos com pouco conhecimento de programação, provavelmente ainda no primeiro ano de graduação.

Utilizei alguns padrões de projeto como Template Method, também de forma que o código ficasse limpo, isolando bem o que é realmente a implementação do algoritmo de outras operações realizadas para o funcionamento do programa.

Por enquanto, a ferramenta ainda tem muito o que melhorar. Pretendo mudar a maneira pela qual os testes são chamados, para evitar que um resultado em cache influencie no tempo de cálculo de outro resultado. Irei também dar a opção de uso de threads, para evitar que o programa pareça travado enquanto um teste mais longo é executado (Isto ainda não foi incluido pois, apesar de interessante para o usuário, o tempo de execução dos testes pode ser influenciado ao utilizar threads). Pretendo incluir ainda outros testes, inclusive versões que façam uso de multiprocessamento quando possível (o comando for paralelo do .NET Framework 4 vai ser uma mão na roda quando eu for fazer isso!).

É isso… apresentei o TG, acabei o curso! Que venha o mestrado!

Leu o documento e achou um erro? Tem alguma dúvida? Quer colaborar no desenvolvimento da ferramenta? Entre em contato comigo, vou tentar responder o mais rápido que puder.

Anúncios

One Response to Testes de Primalidade: Uma Visão Computacional

  1. len disse:

    Saudações de um matemático diletante

    Amirton, gostei mt do seu post e do seu blog; então te pergunto: vc sabe de algum outro teste de primalidade que tenha surgido recentemente, +/- depois do desenvolvimento do Teste de primalidade AKS ???? Também, usando técnicas de Aritmética Modular ??????

    Desde já grato pelo retorno …

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: