Algoritmo Baby-step/Giant-Step
Buonasera a tutti! Sul testo "Introduction To Cryptography" di Johannes A. Buchmann a pag. 186 ho trovato una trattazione abbastanza esauriente dell'algoritmo Baby-Step Giant-Step per il calcolo del logaritmo discreto, il punto che mi è oscuro riguarda un teorema enunciato (e non dimostrato) poche pagine dopo
dove la lettera $G$ denota un generico gruppo ciclico finito.
Non ho ben chiaro il discorso della complessità computazionale legata agli algoritmi; qualcuno può gentilmente indirizzarmi verso letture che chiariscano questo mio problema in modo tale che io possa capire, ad esempio, il teorema prima enunciato.
Vi ringrazio in anticipo per eventuali suggerimenti!
"The baby-step giant-step algorithm requires $O(\sqrt{|G|})$ multiplications and comparisons in $G$. It needs storage for $O(\sqrt{|G|})$"
dove la lettera $G$ denota un generico gruppo ciclico finito.
Non ho ben chiaro il discorso della complessità computazionale legata agli algoritmi; qualcuno può gentilmente indirizzarmi verso letture che chiariscano questo mio problema in modo tale che io possa capire, ad esempio, il teorema prima enunciato.
Vi ringrazio in anticipo per eventuali suggerimenti!
Risposte
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo