algorithm - 计算离散对数

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

根据 % 运算符，我假设您正在使用整数。

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

寻找离散对数问题的快速解决方案的难度是一些流行密码算法的基本部分，因此如果您找到比维基百科上的任何解决方案更好的解决方案，请告诉我!