计算离散对数 [英] Calculate discrete logarithm

问题描述

给出正整数b, c, m，其中(b < m) is True是找到正整数e使得

Given positive integers b, c, m where (b < m) is True it is to find a positive integer e such that

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

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

where ** is exponentiation (e.g. in Ruby, Python or ^ in some other languages) and % is modulo operation. What is the most effective algorithm (with the lowest big-O complexity) to solve it?

示例:

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

Given b=5; c=8; m=13 this algorithm must find e=7 because 5**7%13 = 8

推荐答案

这根本不是一个简单的问题.这称为计算离散对数，它是

This isn't a simple problem at all. It is called calculating the discrete logarithm and it is the inverse operation to a modular exponentation.

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

There is no efficient algorithm known. That is, if N denotes the number of bits in m, all known algorithms run in O(2^(N^C)) where C>0.

这篇关于计算离散对数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！