知识卡片

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

扩展欧几里得可求模逆元

理解等级:中级

若gcd(a,n)=1,扩展欧几里得给出整数x、y满足ax+ny=1,于是ax≡1(mod n),x取模n就是a的乘法逆元。

若最大公约数不为1,这种逆元不存在;模除法只能在可逆元素上做。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      To show the existence of inverses, let a be an element of and let (d, x, y) be returned by EXTENDED-EUCLID(a, n). Then we have d = 1, since , and or equivalently, ax = 1 (mod n). Thus [x]n is a multiplicative inverse of [a]n, modulo n. Furthermore, we claim that . To see why, equation (31.20) demonstrates that the smallest positive

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[30000,35000))。 - 结论依据:原文对逆元、欧拉函数、子群阶与模线性方程的定理及证明;公式图已核对。 - 原始内容:To show the existence of inverses, let a be an element of and let ( d , x , y ) be returned by E XTENDED -E UCLID ( a , n ). Then we have d = 1, since , and or equivalently, ax = 1 (mod n ). Thus [ x ] n is a multiplicative inverse of [ a ] n , modulo n . Furthermore, we claim that . To see why, equation (31.20) demonstrates that the smallest positive