Re: scusate......

Nail writes:
 > 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)

sull'ultimo numero di "Lettera Matematica PRISTEM", una rivista
pubblicata da Springer-Verlag Italia, c'è un interessante articolo [*]
dedicato ai numeri primi e ai metodi per verificare la primalità, tra
cui AKS. In particolare gli autori dimostrano che:

«la stima asintotica della complessità di AKS è Õ(log^10.5 N) (e
dunque polinomiale di grado al più 11 rispetto alla lunghezza
dell'input).»

Õ coinvolge effettivamente un polinomio di log log N:

«Si afferma invece che il tempo è Õ(log^d N) se è O(log^d N), a meno di
un ulteriore fattore polinomiale nel logaritmo del logaritmo di N (il
che specifica ancora meglio il numero dei passi della sua attuazione,
ma lo mantiene ad un livello polinomiale rispetto al parametro
decisivo, cioè il logaritmo di N).»



[*] Stefano Leonesi, Sonia L'Innocente, Marika Marconi, Carlo
    Toffalori - "Primi e segreti" - Lettera Matematica PRISTEM 52,
    giugno 2004, pp. 10-20
________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List