Baby-step giant-step

Baby-step giant-step
Classe	Logaritmo discreto
Struttura dati	Hash table
Caso peggiore temporalmente	${\displaystyle O({\sqrt {n}})}$
Caso peggiore spazialmente	${\displaystyle O({\sqrt {n}})}$

In crittografia e in teoria dei gruppi, l'algoritmo Baby-step giant-step (lett. "Passi-nani e passi-giganti"^[1]) è 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^[2].

Descrizione

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

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

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

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

Note

1. Venturi, pp. 486-7.
2. Nechaev, p. 165.

Bibliografia

• Daniele Venturi, Crittografia nel Paese delle Meraviglie, collana UNITEXT, Springer Milan, 2012, DOI:10.1007/978-88-470-2481-6, ISBN 978-88-470-2480-9.
• (EN) V. I. Nechaev, Complexity of a determinate algorithm for the discrete logarithm, in Mathematical Notes, vol. 55, n. 2, 1994, pp. 165-172, DOI:10.1007/bf02113297.