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.
Rimane il fatto che il test di miller-rabin verifica la primalita' di un
numero con probabilita' di errore 2^-s in O(slgn).
Per di piu' piu' e' grande il numero meno diventa cruciale la scelta di s.
Molto piu' pratico.

Proprio per questo l'interesse commerciale lo lascerei fuori dai motivi.
Piuttosto, mi aspetterei che gli indiani fossero chiusi ora come ora in
una stanza con l'idea di poter utilizzare questa cosa per FATTORIZZARE
numeri.
E li' io mio nasconderei (w i signori della truffa).

Ovviamente il tutto dipende da "cosa ci devo fare" e tutto cio' che
vi siete appena letti e' I.M.H.O. :)
Cmq, si trova proprio tutto su internet.
Il paper: http://www.utm.edu/research/primes/references/refs.cgi/AKS2002

Bye
	Nail

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