math - 如何在 MOD 表达式中找到变量值？

Question

9 = 2^X 模 11

什么是 X，你如何找到 X？

它与在 RSA 算法中查找纯文本有关，我正在为它编写一个 C 程序。

Answer 1

对于任何整数 i，答案都是 6 + 10i。

获得小模数的解决方案的一种简单方法是遍历 x 的所有值。如果存在任何解决方案，您只需检查 0 到 10 (= 11 - 1) 之间的值即可找到第一个解决方案。

x = 0
while x < 50:
    if 9 == 2**x % 11:
         print x
    x += 1

输出:

6
16
26
36
46

如果模数很大，显然这将需要很长时间。

更多信息请访问 Discrete Logarithm页。注意:

No efficient classical algorithm for computing general discrete logarithms logbg is known. The naive algorithm is to raise b to higher and higher powers k until the desired g is found; this is sometimes called trial multiplication. This algorithm requires running time linear in the size of the group G and thus exponential in the number of digits in the size of the group.

如果模幂求逆很容易，那它就不是一个好的密码原语了。