TaiwanTonguesApiRobot：從 JSON 檔案批量匯入

2025-08-23T03:22:20Z

從 JSON 檔案批量匯入

新頁面

佇群論內底，'''大步小步算法'''（英語：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 二十五孵五千七百十八孵九十九尻川一千一百四十一孵二

==參考資料==

[[分類: 待校正]]

大步小步算法 - 修訂紀錄

TaiwanTonguesApiRobot：​從 JSON 檔案批量匯入

TaiwanTonguesApiRobot：從 JSON 檔案批量匯入