算法中的模块化反演
modular inversion in algorithms
我正在阅读 Sanjoy das gupta 的算法书中的扩展欧几里得算法，链接如下第 33 页
http://www.cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf
假设我们希望计算 11^-1 mod 25。
使用扩展 Euclid 算法，我们发现 15 * 25 - 34 * 11 = 1。减少两边 modulo 25，我们有 -34 * 11 全等等于 1 mod 25。所以 -34 全等等于 16 mod 25 是 11 mod 25 的倒数.
我的问题是作者如何得出结论“-34 全等等于 16 mod 25 是 11 mod 25 的倒数。”来自之前的声明。
因为 15 * 25 - 34 * 11 = 1 你有 15 * 25 - 34 * 11 = 1 mod 25 导致 -34 * 11 = 1 mod 25.
如果你有 a * b = 1，那么 a 是 b 的乘法逆元，不管 a 和 b 是矩阵、字段元素还是元素残差 class 环。
当您将 -34 规范化到 0 到 24 之间的范围时，您会得到结果 16：16 = 2 * 25 - 34，因此 16 * 11 = 1 mod 25。注意：在 0 到 24 之间，只有一个自然 k 和 k * 25 - 34，在这种情况下是 2。
我正在阅读 Sanjoy das gupta 的算法书中的扩展欧几里得算法，链接如下第 33 页
http://www.cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf
假设我们希望计算 11^-1 mod 25。
使用扩展 Euclid 算法，我们发现 15 * 25 - 34 * 11 = 1。减少两边 modulo 25，我们有 -34 * 11 全等等于 1 mod 25。所以 -34 全等等于 16 mod 25 是 11 mod 25 的倒数.
我的问题是作者如何得出结论“-34 全等等于 16 mod 25 是 11 mod 25 的倒数。”来自之前的声明。
因为 15 * 25 - 34 * 11 = 1 你有 15 * 25 - 34 * 11 = 1 mod 25 导致 -34 * 11 = 1 mod 25.
如果你有 a * b = 1，那么 a 是 b 的乘法逆元，不管 a 和 b 是矩阵、字段元素还是元素残差 class 环。
当您将 -34 规范化到 0 到 24 之间的范围时，您会得到结果 16：16 = 2 * 25 - 34，因此 16 * 11 = 1 mod 25。注意：在 0 到 24 之间，只有一个自然 k 和 k * 25 - 34，在这种情况下是 2。