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

Question

9 = 2 ^ X mod 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

显然，如果模数很大，这将花费很长时间。

有关离散对数页面的更多信息。注意：

  

没有有效的经典算法   计算一般离散对数   logbg是众所周知的。天真的算法是   把b提升到越来越高的权力   k直到找到所需的g;这个   有时被称为审判   乘法。这个算法   要求运行时间线性   因此，G组的大小   指数的位数   小组的大小。

如果很容易颠倒模块化指数，那么它就不是一个好的加密原语。

Answer 2

显然，2 ^ n mod 11的序列将是循环的。

2 ^ 0 mod 11 = 1
2 ^ 1 mod 11 = 2
2 ^ 2 mod 11 = 4
2 ^ 3 mod 11 = 8
2 ^ 4 mod 11 = 5
2 ^ 5 mod 11 = 10
2 ^ 6 mod 11 = 9
2 ^ 7 mod 11 = 7
2 ^ 8 mod 11 = 3
2 ^ 9 mod 11 = 6
2 ^ 10 mod 11 = 1
2 ^ 11 mod 11 = 2

因此，周期长度为10.

对于n = 6 + 10 * m，

2 ^ n mod 11 = 9，其中m是整数

Answer 3

我认为可以使用模运算来解决。另一种方法是在F ₁₁ （Z / 11Z）中计算9 = 2 ^ X，但这也是模运算的一部分。

另一个解决方案（你只能找到一个解决方案）是用数字方式求解方程式，这在C程序中可能更容易。