如何在没有循环的情况下求解公式 (y*known_number)%145 = 81 中的 y

Question

是否可以不用循环求解此方程中的 y？

known_number = 7
(y * known_number) % 145 == 81

我正在使用循环，但我在想，因为它是简单的乘法，所以可能有一个公式可以不用循环来解决它，或者有吗？

这是我用来解决它的代码：

known_number = 7
for y in range(145):
   if (y * known_number) % 145 == 81:
       print(y)  # -> 53

Answer 1

还有一个方法，不过仔细看是另一种循环。。反正可以这样解决：

y*known_number ≡ 81 (mod 145)
y ≡ 81 * known_number ^ -1 (mod 145)

当且仅当 known_number 确实有一个 modular multiplicative inverse 模 145，当已知数和模数之间的 GCD 为 1（gcd(7, 145) = 1 所以在这种情况下它会起作用）。这里的倒数是 83，所以我们计算 y = 81 * 83 % 145 = 53.

一般来说，您可能会通过扩展欧几里德算法找到逆函数，但也可以通过各种其他方法找到逆函数，例如 pow(known_number, 111, 145)，其中 111 是 totient(145) - 1。计算一个 totient 并不容易，除非你有数字的质因数分解。 pow 函数隐藏了一个循环，但比暴力破解方程要短得多。

如何在没有循环的情况下求解公式 (y*known_number)%145 = 81 中的 y

How to solve for y in formula (y*known_number)%145 = 81 without a loop

python

math

mod