16 Sep 2004 11:42
Re: scusate......
On Wed, Apr 09, 2003 at 12:55:40AM +0200, Marco Marabelli wrote: > mi riferisco all'ultimo msg postato ... ma nessuno ha da dire qualcosa al > riguardo? > (mi riferisco al paper di quei ricercatori indiani che sembra abbiano > trovato un modo per dedurre se un numero e' primo o no, senza passare per > tentativi.....) > Non ne sento parlare da nessuna parte, non e' una bufala (qualcosa si trova > su Internet), e il fatto che non si sia fatto clamore mi sembra > _per_lo_meno_ abbastanza singolare. > Mi e' quasi venuto in mente che ci sia dietro qualche interesse commerciale > ... > ma probabilmente e' una stupidata ;oP > > Cosa ne pensate? > Un motivo della poca notorieta' della cosa a mio parere e' dato dal fatto che il metodo e' si, certo, ma ha anche solo una complessita' computazionale teorica che lo rende poco utilizzabile, per ora. Non l'ho qui sottomano, ma se non ricordo male il test richiede O(lg^6 n f(lg lg n)) con f(x) polinomiale (per essere rigorosi sarebbe 12 e non 6 ma quasi tutti prendono per buona l'assunzione che serve per abbassare l'esponente) Facendo 2 conti, con 1024 bit di numero, si hanno circa 2^60 passi. Infattibile per un oggetto che deve TAROVARE numeri primi tirandoli a caso. Questa e' piu' o meno la stessa complessita' del metodo a curve ellittiche, anch'esso non proprio diffusissimo, con l'unica differenza che non e' randomizzato.(Continue reading)
RSS Feed