Baby-Step Giant-Step
El algoritmo BSGS descompone el logaritmo discreto x=im+j (con m=ceil(√n)) en dos pasos: precalcular g^j (pasos bebé) y luego buscar h*(g^(-m))^i (pasos gigante).
Propósito
Resolver logaritmos discretos con un intercambio tiempo-espacio en complejidad O(√n).
Mecanismo
Sea m=ceil(√n). Pasos bebé: calcular y almacenar {g^j : 0≤j<m}. Pasos gigante: para i=0,1,... calcular h*g^(-im) y buscarlo en la tabla; al coincidir, x=im+j. Tiempo O(√n), espacio O(√n).
Casos de uso
- Resolución de logaritmos discretos
- Criptoanálisis
- Algoritmos de teoría de números