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

Re: [obm-l] N�MEROS PRIMOS E O CAOS. SER�?????



Acho que voc� n�o sabe do que est� falando...
Que hist�ria � essa dos indianos descobrirem como fatorar inteiros de 
forma eficiente?? Eles descobriram um algoritmo polinomial 
determin�stico para determinar se um n�mero � primo. Isso � diferente de 
FATORAR um n�mero inteiro, que � realmente a base do RSA.

Aqui cabe uma observa��o: apesar de ser um grande feito do ponto de 
vista de teoria da computa��o, o algoritmo AKS n�o causa grande impacto 
pr�tico j� que os algoritmos probabil�sticos s�o muito r�pidos e 
determinam com alt�ssima probabilidade quando um n�mero � primo. � bem 
prov�vel que por muitos anos esses sejam os algoritmos realmente utilizados.

Para o problema de determinar um primo entre dois inteiros tamb�m n�o se 
conhece solu��o eficiente.

Agora, pelo que entendi, voc� alega que descobriu uma maneira de 
determinar o n-�simo primo atrav�s de sistemas lineares... t�, essa eu 
quero ver.

flw
=========================================================================
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
=========================================================================