Baby-step giant-step

In crittografia e in teoria dei gruppi, l'algoritmo Baby-step giant-step (Template:Lett) è un algoritmo meet-in-the-middle che consente di calcolare il logaritmo discreto o l'ordine di un elemento in un gruppo abeliano finito. Questo metodo fu pubblicato per la prima volta da Daniel Shanks nel 1971, ma era probabilmente noto già ad Aleksandr Osipovič Gel'fond nel 1962.

Descrizione

Sia $𝔾$ un gruppo ciclico di ordine $n$, sia $g$ un generatore di $𝔾$ e sia $y=g^x$. Inoltre, sia $m=\lceil n\rceil$ e sia $h=g^{-m}$.

L'algoritmo Baby-step giant-step permettere di calcolare $x$, ovvero il logaritmo discreto di $y$ in base $g$, come segue.

* Passo 0 (Inizializzazione): Si crea una tabella $T$ con le coppie $(j,g^j)$ per ogni $j\in [0,m]$. Si pone $s=y$ e $i=0$
* Passo 1: Si determina se esiste $j$ tale che $(j,s)\in T$. In caso affermativo si restituisce $i\cdot m+j$
* Passo 2: Si pone $s=s\cdot h$, $i=i+1$ e si torna al passo 1

Si noti che il modo migliore per implementare la tabella $T$ è quello di usare una tabella hash, in modo che la ricerca effettuata al Passo 1 richieda tempo costante $O(1)$. L'algoritmo ha complessità temporale e spaziale pari a $O(\sqrt{n})$.

Bibliografia

• Template:Cita libro
• Template:Cita pubblicazione