algorithm - 数的模逆

Question

N最近我阅读了扩展的euclid算法，MOD该算法用于找出一个数的模逆gcd(N,MOD)=1。

但是我对如何找到数字的模逆有疑问 if gcd(N,MOD)!=1？

Answer 1

如果gcd(N,MOD)!=1N 的模逆不存在。

但是，在某些情况下，您仍然可以除以 N，即找到一个 X，使得 A = N * X (mod MOD)。当 gcd(N,MOD) 除以 gcd(A,MOD) 时，这是可能的。要找到这样的 X，只需将 A、N 和 MOD 除以 gcd(N,MOD)，然后照常进行（gcd(N', MOD') 为 1）。