热门标签
更多>
搜索结果
查询Tags标签： BSGS，共有 3条记录-
Baby_Step_Gaint_Step(BSGS) 算法
\(BSGS\) 算法，又称 “北（\(B\)）上（\(S\)）广（\(G\)）深（\(S\)）” 算法，“拔山盖世”算法，可以在 \(O(\sqrt{n})\) 的复杂度内求解离散对数问题。题目描述： 给定质数 \(p\) 和整数 \(a, n\)，求最小的非负整数 \(m\) ，满足 \(a^m \equiv n(mod\ \ p)\) 。 算法…
2022/7/21 1:23:35 人评论 次浏览 -
【学习笔记】BSGS 算法
引入 BSGS（baby-step giant-step），即大步小步算法，常用于求解离散对数问题。该算法可以在 \(O(\sqrt p)\) 的时间复杂度内求解 \[a^x \equiv b \pmod p \]第一部分：\(a \perp p\) 我们将求解的答案 \(x\) 设为 \(km-c \ (c < m)\) 的形式，即 \[a^{km-c} \equiv b…
2022/3/5 22:15:11 人评论 次浏览 -
扩展 BSGS
首先你要知道什么是 BSGS。 BSGS 用于求解形如 \(a^x\equiv b\pmod p\) 的高次同余方程，其中保证 \(p\) 为质数。 根据费马小定理定理，当 \(p\) 为质数时，\(a^{p-1}\equiv 1\pmod p\)。 所以当 \(x\) 有解 \(>p-1\) 时，也必然有 \(y=x-(p-1)\) 为方程的解，换言之，…
2021/6/1 10:20:59 人评论 次浏览
