知识卡片

普通读书笔记卡 · 3699.b

贝祖系数构造模方程初始解

理解等级:中级

扩展欧几里得给出d=gcd(a,n)=ax′+ny′。若d整除b,则x₀=x′(b/d) mod n满足ax₀≡b(mod n);先检查整除条件,再用同一组贝祖系数构造一个解。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第31章 数论算法 · 查看原书依据

      Theorem 31.23 Let d = gcd(a, n), and suppose that d = ax′ + ny′ for some integers x′ and y′ (for example, as computed by EXTENDED-EUCLID). If d | b, then the equation ax = b (mod n) has as one of its solutions the value x0, where x0 = x′(b/d) mod n. Proof We have ax0 = ax′(b/d) (mod n) = d(b/d)

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[40000,45000))。 - 结论依据:原文对逆元、欧拉函数、子群阶与模线性方程的定理及证明;公式图已核对。 - 原始内容:Theorem 31.23 Let d = gcd( a , n ), and suppose that d = ax ′ + ny ′ for some integers x ′ and y ′ (for example, as computed by E XTENDED -E UCLID ). If d | b , then the equation ax = b (mod n ) has as one of its solutions the value x 0 , where x 0 = x ′( b / d ) mod n . Proof We have ax 0 = ax ′( b / d ) (mod n ) = d ( b / d )