Re: primalita'

On Sat, Oct 26, 2002 at 01:25:27PM +0000, tho wrote:
> Francesco Trentini wrote:
> > Per gli interessati, un algoritmo deterministico in tempo polinomiale
> > per la primalita'.
> > http://www.cse.iitk.ac.in/users/manindra/
> 
> in particolare si dice che a meno di poter provare la congettura alla sez 6, 
> per il momento l'algoritmo sarebbe impraticabile (500-5000 ore per un primo a 
> 512-bit) contro i 2 minuti o poco piu' di ECPP che pure e' deterministico
> (anche se non polinomiale in senso "stretto")
> 
> t


Per completare: http://cr.yp.to/papers/aks.pdf. D.j. bernstein propone
un metodo per recuperare piu' velocemente i due bound (r ed s) per il check
abbassando il limite superiore (se non ricordo male a O(ln^6+....) invece di
O(ln^12+..)).



-- 
Bye,	
		Alessio

PGP signature