知识卡片

普通读书笔记卡 · 3699.b.1

模方程全部解按固定步长枚举

理解等级:中级

已知ax≡b(mod n)的一个解x₀和d=gcd(a,n)后,全部d个不同解为xᵢ=x₀+i(n/d) mod n,i从0到d−1。

求解器先算最大公约数和一个解,再按此步长枚举;输出d个解本身需至少d次操作。

这张卡片看不懂?

已有反馈 · 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