大步小步算法

佇群論內底，大步小步算法（英語：baby-step giant-step）是丹尼爾・尚克斯發明的一種中途相拄算法，用佇計算離散對數或者是有限阿貝爾群的階。其中離散對數問題佇咧公鎖加密領域有非常重要的地位。

濟濟用的加密系統攏因為離散對數極難計算這一假設—— 算是愈困難，這寡系統提供的數據傳輸就愈安全。增加離散對數計算難度的一種方法，是共密碼系統建立佇閣較大群頂懸。

理論

這是一種空間換時間的算法，實質上是求解離散對數的素質算法（枚舉並試乘）伊的一个足簡單的改進。

共出一个 $ n $ 階循環群 $ G $、該群的一个生成元 $ \ alpha $ 佮一个元素 $ \ beta $。試揣著一个整數 $ x $ 滿足

$ \ alpha ^ { x }=\ beta \ , . $

大步小步算法共 $ x $ 代換做：

$ x=im + j $

$ m=\ left \ lceil { \ sqrt { n } } \ right \ rceil $

$ 零 \ leq i < m $

$ 零 \ leq j < m $

所以有：

$ \ alpha ^ { x }=\ beta \ , $

$ \ alpha ^ { im + j }=\ beta \ , $

$ \ alpha ^ { j }=\ beta \ left ( \ alpha ^ {-m } \ right ) ^ { i } \ , $

該算法先對 $ j $ 的無仝取值計算出 $ \ alpha ^ { j } $ 的值，然後固定一个 $ m $，並著 $ i $ 試看覓仔無仝款的價值，帶入去頂懸仝款的正爿，看是毋是佮某一个（已經預先算出的）仝款倒爿的值相匹配。

給出 C + + 十七版本的代碼：

H . Cohen , A course in computational algebraic number theory , Springer , 九百九十六 .
D . Shanks , Class number , a theory of factorization and genera . In Proc . Symp . Pure Math . 二十 , pages 四仔十五—四仔四仔 . AMS , Providence , R . I . , 一千九百七十一 .
A . Stein and E . Teske , Optimized baby step-giant step methods , Journal of the Ramanujan Mathematical Society 二十 ( 兩千空五 ) , no . 一 , 一–三十二 .
A . V . Sutherland , Order computations in generic groups , PhD thesis , M . I . T . , 兩千空七 .
D . C . Terr , A modification of Shanks』baby-step giant-step algorithm , Mathematics of Computation 六十九 ( 兩千 ) , 七仔六十七–七仔七十三 . doi : 十二一空九空 / S 二十五孵五千七百十八孵九十九尻川一千一百四十一孵二