Baby-Step Giant-Step
Der BSGS-Algorithmus zerlegt den diskreten Logarithmus x=im+j (mit m=ceil(√n)) in zwei Schritte: g^j vorberechnen (Baby-Steps), dann h*(g^(-m))^i suchen (Giant-Steps).
Zweck
Diskrete Logarithmen mit einem Zeit-Raum-Kompromiss in O(√n)-Komplexität lösen.
Mechanismus
Sei m=ceil(√n). Baby-Steps: {g^j : 0≤j<m} berechnen und speichern. Giant-Steps: für i=0,1,... h*g^(-im) berechnen und in der Tabelle nachschlagen; bei Übereinstimmung ist x=im+j. Zeit O(√n), Raum O(√n).
Anwendungsfälle
- Lösung diskreter Logarithmen
- Kryptoanalyse
- Zahlentheoretische Algorithmen