如何找到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 模 11 = 1
2^1 模 11 = 2
2^2 模 11 = 4
2^3 模 11 = 8
2^4 模 11 = 5
2^5 模 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 mod 11 = 2

因此，循环长度为 10。

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

Answer 3

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

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