大步小步算法

給定a,b,c，a與c互質，求解ax≡b(mod c)的最小非負整數解。可能無解。

基本介紹

• 中文名：大步小步算法
• 外文名：BSGS(Baby　Step　Giant　Step)
• 所屬學科：數論、計算機算法

定義

求一種特殊同餘方程，A^x≡B(mod　C)的最小整數解，其中A　C互質 的一種算法

原理

給定a,b,c，a與c互質，求解a^x≡b(mod c)的最小非負整數解。可能無解。

a與c互質,根據歐拉定理有a^φ(c)≡1(mod c),如果有解就一定在0 到φ(c)-1內,否則無解,根據這樣的定理即使這樣,直接從小到大枚舉x會逾時。

Baby step giant step算法步驟和要點如下：

1. 把0到c-1按m= (上取整)分塊
2. 把a0,a1,...,ammod c的值存到hash表中(或者存起來排好序)
3. 如果x有解,x一定可以表示成i*m+j(0≤i,j≤m-1),從小到大枚舉i,ai*m+j=(am)i*aj,(am)i的值易求,(am)i*aj≡b(mod c)中aj mod c的值v可以用擴展歐幾里得來求,也可以根據歐拉定理得v=aφ(c)-i*m*b mod c,因為a與c互質,v的值只有一個
4. 接著在hash表中(或有序數組中二分)找出最小的j使得aj mod c=v,如果找到則答案為i*m+j否則無解。

特點介紹

時間複雜度為O(clogc)，對於求極大數時耗費時間相比暴力更少