计算离散对数

• Z时代
• 2024-01-10
• 分类：问答

给定正整数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。

以上是 计算离散对数 的全部内容， 来源链接： utcz.com/qa/416112.html