Visualizza wikitesto di Baby-step giant-step

{{Algoritmo|tempo=<math>O(\sqrt n)</math>|classe=[[Logaritmo discreto]]|spazio=<math>O(\sqrt n)</math>|struttura dati=[[Hash table]]}}

In [[crittografia]] e in [[teoria dei gruppi]], l'algoritmo '''Baby-step giant-step''' ({{lett|Passi-nani e passi-giganti}}<ref name=":0">{{Cita|Venturi|pp. 486-7}}.</ref>) è un [[algoritmo]] [[meet-in-the-middle]] che consente di calcolare il [[logaritmo discreto]] o l'ordine di un elemento in un [[gruppo abeliano]] [[Gruppo finito|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<ref>{{Cita|Nechaev|p. 165}}.</ref>.

== Descrizione ==
Sia <math>\mathbb G</math> un [[gruppo ciclico]] di ordine <math>n</math>, sia <math>g</math> un generatore di <math>\mathbb G</math> e sia <math>y = g^x</math>. Inoltre, sia <math>m= \lceil n \rceil</math> e sia <math>h = g^{-m} </math>.

L'algoritmo ''Baby-step giant-step'' permettere di calcolare <math>x</math>, ovvero il [[logaritmo discreto]] di <math>y</math> in base <math>g</math>, come segue.
 * '''Passo 0 (Inizializzazione)''': Si crea una tabella <math>T</math> con le coppie <math>(j, g^j)</math> per ogni <math>j \in [0,m]</math>. Si pone <math>s = y</math> e <math>i = 0</math>
 * '''Passo 1''': Si determina se esiste <math>j</math> tale che <math>(j, s) \in  T</math>. In caso affermativo si restituisce <math>i \cdot m + j</math>
 * '''Passo 2''': Si pone <math>s = s \cdot h</math>, <math>i = i+1</math> e si torna al passo 1
Si noti che il modo migliore per implementare la tabella <math>T</math> è quello di usare una [[tabella hash]], in modo che la ricerca effettuata al Passo 1 richieda tempo costante <math>O(1)</math>. L'algoritmo ha [[complessità temporale]] e spaziale pari a <math>O(\sqrt n)</math><ref name=":0"/>.

== Note ==
<references />

== Bibliografia ==
* {{Cita libro|nome=Daniele|cognome=Venturi|titolo=Crittografia nel Paese delle Meraviglie|collana=UNITEXT|data=2012|editore=Springer Milan|cid=Venturi|ISBN=978-88-470-2480-9|DOI=10.1007/978-88-470-2481-6}}
* {{Cita pubblicazione|nome=V. I.|cognome=Nechaev|anno=1994|titolo=Complexity of a determinate algorithm for the discrete logarithm|rivista=Mathematical Notes|volume=55|numero=2|doi=10.1007/bf02113297|pp=165-172|lingua=en|cid=Nechaev}}

{{Portale|crittografia|matematica}}

[[Categoria:Algoritmi crittografici]]
[[Categoria:Teoria dei numeri]]