[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] O que � mais f�cil????




 

Existem basicamente dois tipos de testes para n�meros primos: determin�sticos e n�o-determin�sticos. Os determin�sticos como os crivos aritm�ticos, em especial o de Erat�stenes, fazem um trabalho de for�a bruta sofisticada, mas mesmo assim s�o bem demorados para primos gigantes. Por�m, os testes n�o-determin�sticos, tamb�m conhecidos como testes estat�sticos s�o frutos de v�rios trabalhos que estudam a profunda e enigm�tica distribui��o n�o-linear dos primos.
 
Matem�ticos como Riemman, Carmichael, Lucas, Lehmer, entre outros, travaram guerras �picas para desenvolver m�todos pr�ticos, r�pidos e eficientes para identificar primos de forma n�o-linear. Enfim, tais testes n�o-determin�sticos s�o extremamente velozes em compara��o aos determin�sticos e conseguem determinar com uma precis�o impressionante com mais de 99% de certeza se uma dado n�mero � primo. Os n�meros que passam nesse teste ou s�o realmente primos ou s�o pseudoprimos
 
Se um n�mero passar no teste estat�stico, s� ent�o vai para o teste determin�stico.
Com esse teste  se verificam n�meros de Mersenne primos gigantes. S�o r�pidos e pr�ticos. 
Pergunta: � mais f�cil  verificar primalidade  do que fatorar n�meros gigantes????
 
[[ ]]'s


Copa 2006: Sabe como se diz �p�nalti� em alem�o? Clique aqui: ========================================================================= 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 =========================================================================