Re: [Hackmeeting] a proposito di: 'Perche' PRIMES e' in P?' …

Purtroppo ho letto solo ora questa mail, ma rispondo lo stesso, a
posteriori.

On Fri, Sep 28, 2007 at 12:14:49AM +0200, Mario Velucchi wrote:
> AKS è un algoritmo che verifica se un numero dato in input è primo in tempo
> polinomiale. Il risultato è uscito nell'articolo "PRIMES is in P" di pochi
> anni fa.
> Come funziona e, soprattutto, perché funziona? Per capirlo scorreremo la
> dimostrazione con una quantità di dettagli sufficiente a capire cosa ci sta
> sotto... ovvero parecchia algebra :)

> spero che l'amico oratore eflags, oltre che spiegare ed usare tanta algebra

L'idea del seminario era proprio quella di far vedere che genere di
ragionamenti ci possono essere dietro un test di primalità, usando
a) qualcosa che ha fatto notizia e di cui si è tanto parlato (anche,
spesso, a sproposito);
b) qualcosa che, almeno in alcuni passaggi, fosse comprensibile -- se
conosci il test ciclotomico sai perfettamente che AKS è, dal punto di
vista degli strumenti necessari, di gran lunga piú semplice.

> enfatizzi il fatto che questo algoritmo non dice nulla di veramente
> interessante...

Voglio ancora vedere un test di primalità che dica delle cose veramente
interessanti, di solito la loro conversazione si limita a "PRIMO" e
"COMPOSTO"; al limite qualche certificato succinto <grin>

Se ti riferisci al fatto che le idee di fondo fossero già state viste in
altri algoritmi, questo è ribadito anche nella premessa all'articolo e
sinceramente non vedo che interesse abbia questo fatto.

> in particolare non serve praticamente a nulla di veramente
> interessante...

Dipende dai tuoi interessi. Questo è ovviamente una risposta alla
domanda se il problema PRIMES è di classe P... può essere o meno
interessante.

Se intendi dire che questo algoritmo non sarà mai utile dal punto di
vista delle applicazioni alla crittografia, non possiamo dirlo. Nella
sua forma attuale è in effetti molto inferiore (dal punto di vista delle
prestazioni) ad altri algoritmi correntemente in uso (e.g.
Miller-Rabin), anche se nulla vieta che in futuro possano esistere delle
varianti dell'algoritmo "competitive"; certo sarà necessaria qualche
idea nuova --perché il lavoro di lima è già stato fatto da varie persone
e ha portato miglioramenti sensibili-- ma perché no?

> eccola mettiamola cosi'!...

Boh, mettila un po' come ti pare. Certo, con un po' di polemica,
aggiungo che è molto piú facile criticare qualcuno ("l'amico oratore
eflags" sa proprio di presa per il culo, eh) perché fa una cosa
inutile invece che mettersi davanti a delle altre persone a cercare di
spiegare loro qualcosa che, visto il contesto non proprio di esperti e
specialisti, è piuttosto complicato.

Poi io come oratore, me ne rendo conto, sono scarso e ho sicuramente
fatto alcune scelte sbagliate -- mi dispiace per quelli che sono morti a
metà del seminario :)

Ad ogni modo succhiamelo e l'anno prossimo fallo tu un seminario, magari
su qualcosa di veramente interessante.

eflags