用來求解如下同余方程x的最小正整數解：

? ? ? ? ? ? ? ? ? ? ? ? ?

p為質數，a、b、p已知，且 (如果a、b大于p，則對他們取模)

模板：（p為素數）

/*********************解法***********************///BSGS算法//求 a^x === b(mod p) 中的x值-----------當前p為素數//實際運用中用自己的hash表代替map可防TLE /*********************解法***********************/LLLL BSGS(LL a, LL b, LL p){a %= p; b %= p;map<LL, LL>h;LL m = ceil(sqrt(p)), x, y, d, t = 1, v = 1;for(LL i = 0; i < m; i++){if(h,count(t)) h[t] = min(h[t], i);else h[t] = i;t = (t * a) % p;}for(LL i = 0; i < m; i++){d = exgcd(v, p, x, y);x = (x * b/d % p + p) % p;if(h.count(x)) return i * m + h[x];v = (v * t) % p;}return -1; }

擴展（p為非素數）

模板：

/*********************解法***********************///BSGS算法//求 a^x === b(mod p) 中的x值-----------當前p為合數//注意：a，b，p分別為1，1，1時，結果x為1而非0 /*********************解法***********************/LL exBSGS(LL a, LL b, LL ){a %= p; b %= p;LL res = 1;for(LL i = 0; i <= 50; i++){if(res == b) return i;res = (res * a) % p;} //枚舉比較小的LL x, y, d, , v = 1, cnt = 0;while(d = gcd(a, p) != 1){if(b % d) return -1;b /= d, p /= d;v = (v * (a/d)) % p;cnt++;} //約分直到(a,p) == 1;map<LL, LL> h;LL m = ceil(sqrt(p)), t = 1;for(LL i = 0; i < m; i++){if(h.count(t)) h[t] = min(h[t], i);else h[t] = i;t = (t * a) % p;}for(LL i = 0; i < m; i++){d = exgcd(v, p, x, y);x = ((x * (b/d)) % p + p) % p;if(h.count(x)) return i * m + h[x] + cnt;v = (v * t) % p;}return -1; }

?

總結

以上是生活随笔為你收集整理的离散对数（同余理论-BSGS算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。