java - 在java中使用欧几里得算法

Question

如果我有 x= 11 和 y = 6 并且我想计算(w*x)mod(y) = 1。换句话说，我如何计算乘以 11 然后对结果 1 取模 6 的数字。在这种情况下，w 应该等于 5。无论如何我可以在java中使用欧几里德算法计算w？谢谢!

Answer 1

有一个定理说线性同余a * x = b (mod n)，其中a, b, and n 是整数，有一个解决方案当且仅当 gcd(a, n) = 1。

因为 gcd(11,6) = 1，这只是因为 11 是质数，所以你的方程确实是可解的。

要回答这个问题，不，您不能使用欧几里得算法解决线性同余---但是，您可以使用扩展欧几里得算法来解决这个问题---，但您可以使用它来验证方程是否可解。

一旦找到 gcd(a,n)=1，您就可以将解计算为 x = b*r mod n，其中 r = a ^-1 (mod n)。要计算 a 的逆函数(我们在这里表示为 r)，您可以使用扩展欧几里德算法(缩写为 EEA)。

如果 gcd(a,n)=1，则给定 a 和 n，EEA 计算 r 和 s 使得 a*r + n*s = 1。我们声称 r 是 a 模 n 的逆。一旦你有了 r，你就可以计算 x = b * r mod n。

Cormen 等人在算法导论一书中很好地描述了这些算法。