计算离散对数

Question

给定正整数b, c, m,(b < m) is True找到一个正整数e,这样

(b**e % m == c) is True

其中**是取幂(例如在Ruby,Python或^中的某些其他语言中),%是模运算.什么是最有效的算法(具有最低的大O复杂度)来解决它？

例:

给定b = 5; C = 8; m = 13该算法必须找到e = 7,因为5**7%13 = 8

Answer 1

从%运算符我假设你正在使用整数.

您正在尝试解决离散对数问题.一个合理的算法是Baby步骤,巨大的一步,虽然还有很多其他的,但没有一个特别快.

找到离散对数问题的快速解决方案的难度是一些流行的加密算法的基本部分,所以如果你找到比维基百科上任何一个更好的解决方案,请告诉我!

Answer 2

这根本不是一个简单的问题.它被称为计算离散对数,它是模幂指数的逆运算.

没有已知的有效算法.也就是说,如果N表示m中的比特数,则所有已知算法在O(2 ^(N ^ C))中运行,其中C> 0.

Answer 3

Python 3 解决方案：

值得庆幸的是，SymPy已经为您实现了这一点！

SymPy 是一个用于符号数学的 Python 库。它的目标是成为一个功能齐全的计算机代数系统（CAS），同时保持代码尽可能简单，以便易于理解和扩展。SymPy 完全用 Python 编写。

这是该函数的文档discrete_log。使用它来导入它：

from sympy.ntheory import discrete_log

他们的例子计算\log_7(15) (mod 41)：

>>> discrete_log(41, 15, 7)
3

由于它采用了（请注意，最先进的）算法来解决这个问题，因此您将获得O(\sqrt{n})尝试的大多数输入。p - 1当你的素数模数具有分解许多小素数的属性时，速度会快得多。

考虑 100 位数量级的素数：(~ 2^{100})。复杂度为 \sqrt{n} 时，仍然需要 2^{50} 次迭代。话虽如此，不要重新发明轮子。这做得非常好。MultiplicativeOrder我还可以补充一点，当我运行较大的输入（44 MiB 与 173 MiB）时，它的内存效率几乎是 Mathematica 函数的 4 倍。