Re: Re: scusate......

Nail wrote:
> 
> 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.
> Rimane il fatto che il test di miller-rabin verifica la primalita' di un
> numero con probabilita' di errore 2^-s in O(slgn).

O(s lg^3 n) e (sotto ipoteesi realistiche) O(log^5 n)

E gli indiani haano una congettura (non dimostrata) che porta  (log^3 n)

Sala Massimiliano wrote:
> 


> Per cui qualunque succeda sui test per verificare se un numero e' primo o
> no, cio' non intacca di una virgola il problema della fattorizzazione e
> quindi la sicurezza di RSA.


Concordo

RSA invece e` stato condannato a morte giocando intelligentemente sulla
costante della complessita`: l'ultima macchina di Shamir richiede di
darsi da fare a trovare una diversa alternativa.

Teo

________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List