给定正整数b, c, m,(b < m) is True可以找到一个正整数e,使得
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
这根本不是一个简单的问题。这称为计算离散对数,它是模幂的逆运算。
没有有效的算法。也就是说,如果N表示以m为单位的位数,则所有已知算法都以O(2 ^(N ^ C))的形式运行,其中C> 0。