一尘不染

计算离散对数

algorithm

给定正整数b, c, m(b < m) is True可以找到一个正整数e,使得

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

其中**是取幂(例如,在Ruby,Python或某些其他语言中为^),%是取模运算。什么是最有效的算法(具有最低的big-O复杂度)?

例:

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


阅读 495

收藏
2020-07-28

共1个答案

一尘不染

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

没有有效的算法。也就是说,如果N表示以m为单位的位数,则所有已知算法都以O(2 ^(N ^ C))的形式运行,其中C> 0。

2020-07-28