问计算离散对数

EN

这根本不是一个简单的问题。它被称为计算discrete logarithm，它是与modular exponentation相反的操作。

目前还没有已知的有效算法。也就是说，如果N表示m中的位数，则所有已知算法都在O(2^(N^C))中运行，其中C>0。

通过%运算符，我假设您正在处理整数。

您正在尝试解决the Discrete Logarithm问题。一个合理的算法是Baby step, giant step，尽管还有许多其他算法，它们都不是特别快。

寻找离散对数问题的快速解决方案的困难是一些流行密码算法的基本部分，所以如果你在维基百科上找到了比任何一个更好的解决方案，请让我知道！

Python 3解决方案：

值得庆幸的是，SymPy已经为您提供了implemented！

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

这是documentation on the 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}次迭代。话虽如此，但不要重复发明轮子。这项工作做得很好。我还可以补充说，当我使用大容量输入(44 MiB vs. 173 MiB)运行时，它的内存效率几乎是Mathematica的MultiplicativeOrder函数的4倍。