Re: [obm-l] O que é mais fácil????

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Wed, Feb 15, 2006 at 10:38:24AM +0000, Rhilbert Rivera wrote:

   Existem   basicamente  dois  tipos  de  testes  para  nmros  primos:
   determinsicos  e  nodeterminsicos.  Os  determinsicos  como os
   crivos aritmtcos, em especial o de Eratsenes, fazem um trabalho de
   forabruta sofisticada, mas mesmo assim sobem demorados para primos
   gigantes. Porm os testes nodeterminsicos, tambmconhecidos como
   testes  estatsicos  so frutos  de  vros  trabalhos que estudam a
   profunda e enigmtca distribuionolinear dos primos.

Isto ja nao e mais bem verdade. Em 2002 Agrawal, Kayal e Saxena encontraram
um algoritmo deterministico de tempo polinomial para testar primalidade.
Ainda e verdade que os testes nao deterministicos sao bem mais rapidos
(ou seja, tambem sao de tempo polinomial, mas o grau do polinomio e bem menor).

   Matemtcos  como  Riemman,  Carmichael,  Lucas, Lehmer, entre outros,
   travaram  guerras  pcas para desenvolver mtdos prtcos, rpdos e
   eficientes  para  identificar  primos de forma nolinear. Enfim, tais
   testes  nodeterminsicos soextremamente velozes em comparaoaos
   determinsicos e conseguem determinar com uma precisoimpressionante
   com  mais de 99% de certeza se uma dado nmro  rimo. Os nmros que
   passam nesse teste ou sorealmente primos ou sopseudoprimos.

   Se  um  nmro  passar no teste estatsico, s ntovai para o teste
   determinsico.
   Com  esse teste  se verificam nmros de Mersenne primos gigantes. So   rpdos e
   Pergunta:     mais  fcl   verificar  primalidade   do  que fatorar
   nmros gigantes????

Eh um problema em aberto decidir se existe um algoritmo de tempo polinomial
para fatorar inteiros. O certo eh que nenhum tal algoritmo eh conhecido
ate hoje.  Parece seguro apostar, entretanto, que mesmo se tal algoritmo
existir, fatorar sempre serah mais dificil do que testar primalidade.

Veja muito mais sobre este assunto em 
http://primes.utm.edu

O livro meu e do Gugu tambem pode ser do seu interesse.
Ha uma versao nao atualizada na minha home page:
www.mat.puc-rio.br/~nicolau/papers/mersenne/index.html
ou compre o livro (de papel) no Impa.

[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================