知识卡片
扩展欧几里得可求模逆元
若gcd(a,n)=1,扩展欧几里得给出整数x、y满足ax+ny=1,于是ax≡1(mod n),x取模n就是a的乘法逆元。
若最大公约数不为1,这种逆元不存在;模除法只能在可逆元素上做。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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