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

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

更多信息在离散对数页面上。笔记：

没有已知的用于计算一般离散对数 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 模 11 = 7
2^8 模 11 = 3
2^9 模 11 = 6
2^10 模 11 = 1
2^11 模 11 = 2

因此，周期长度为 10。

2^n mod 11 = 9 for n=6+10*m 其中 m 是整数

Answer 3

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

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