知识卡片
模方程全部解按固定步长枚举
已知ax≡b(mod n)的一个解x₀和d=gcd(a,n)后,全部d个不同解为xᵢ=x₀+i(n/d) mod n,i从0到d−1。
求解器先算最大公约数和一个解,再按此步长枚举;输出d个解本身需至少d次操作。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第31章 数论算法 · 查看原书依据
Theorem 31.24 Suppose that the equation ax = b (mod n) is solvable (that is, d | b, where d = gcd(a, n)) and that x0 is any solution to this equation. Then, this equation has exactly d distinct solutions, modulo n, given by xi = x0 + i(n/d) for i = 0, 1,
参考来源
- 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[40000,45000))。
- 结论依据:原文对逆元、欧拉函数、子群阶与模线性方程的定理及证明;公式图已核对。
- 原始内容:Theorem 31.24 Suppose that the equation ax = b (mod n ) is solvable (that is, d | b , where d = gcd( a , n )) and that x 0 is any solution to this equation. Then, this equation has exactly d distinct solutions, modulo n , given by x i = x 0 + i ( n / d ) for i = 0, 1, …, d – 1. Proof Because n / d > 0 and 0 ≤ i ( n / d ) < n for i = 0, 1, …, d – 1, the values x 0 , x 1 , …, x