著者: eflags 日付: 題目: [Hackmeeting] messa in sicurezza servers A/I
On Tue, Jul 05, 2005 at 03:22:55PM +0200, P@sKy wrote:
[snip] > Spero di essermi spiegato, poi non dimentichiamoci che
> tutta la bella crittografia e' basata sulla scomposizione
> di fattori primi o meglio sulla difficolta' di scomporre
> in tempi "umani" in fattori primi un numero compreso tra
> 0 e 2^1024 per chiavi di 1024bit come esempio, ma vi sono
> fior fior di studi che sostengono di aver trovato un algoritmo
> che individua con certezza se un numero sia primo o meno.
>
> Ricordo di aver postato tempo fa in lista cyber-rights uno
> studio di Manindra Agrawal dal titolo "PRIMES is in P." dove
> Manindra sosteneva, con una bella dimostrazione matematica,
> quindi non basata sul sesso degli angeli, di aver scoperto un
> metodo, cioe' un algoritmo, che dato qualsiasi numero
> si puo' sapere con certezza se e' un numero primo o meno,
> mentre gli attuali algoritmi non sono in grado di sostenere
> con certezza che dato un numero sia primo o meno ma danno
> solo un approssimazione.
[Nota: faccio matematica, ma non ho seguito corsi sulla
crittografia... magari potrebbe parlare qualcuno che ne sa di più
:)) ]
"PRIMES is in P" vuol dire che il problema di sapere se un numero
è primo (soprannominato PRIMES) è di classe P, ovvero
"deterministic polynomial time".
Prima si pensava che fosse di classe NP ("non deterministic
polynomial time") ovvero gli algoritmi facevano un certo numero
di scelte "casuali" per non incappare nel caso peggiore... come
quando ordini con il quicksort e scegli il pivot a caso.
Questo non vuol dire che il risultato non fosse attendibile :)
in effetti comunque a volte si usano algoritmi "quasi giusti" che
impiegano meno tempo.
Attualmente l'algoritmo deterministico è mediamente più lento di
quello NP, ma è di classe P :) e questo è un bel risultato
_teorico_
Un'ultima cosa: il tempo per stabilire se un numero è primo è
polinomiale nel senso che è un polinomio del numero di cifre (o
di bit, che è esattamente la stessa cosa).
