计算离散对数

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

由于这个问题的副本是在Python标签下提出的，这里有一个baby step，giant step的Python实现，正如@MarkBeyers指出的，这是一个合理的方法（只要模不太大）：

def baby_steps_giant_steps(a,b,p,N = None):
    if not N: N = 1 + int(math.sqrt(p))

    #initialize baby_steps table
    baby_steps = {}
    baby_step = 1
    for r in range(N+1):
        baby_steps[baby_step] = r
        baby_step = baby_step * a % p

    #now take the giant steps
    giant_stride = pow(a,(p-2)*N,p)
    giant_step = b
    for q in range(N+1):
        if giant_step in baby_steps:
            return q*N + baby_steps[giant_step]
        else:
            giant_step = giant_step * giant_stride % p
    return "No Match"

在上面的实现中，即使p是密码学上大的，显式N也可以传递给fish以获得小指数。只要指数小于N**2，它就会找到指数。当省略N时，将始终找到指数，但如果p太大，则不一定在您的生命周期或计算机内存中找到指数。

例如，如果

p = 70606432933607
a = 100001
b = 54696545758787

然后“pow（a，b，p）”计算为67385023448517

以及

>>> baby_steps_giant_steps(a,67385023448517,p)
54696545758787

这在我的机器上花了5秒钟。对于这些尺寸的指数和模数，我估计（基于计时实验）蛮力可能需要几个月的时间。

Answer 2

从%运算符中，我假设您使用的是整数。

你在试图解决the Discrete Logarithm问题。一个合理的算法是Baby step, giant step，尽管还有许多其他算法，但都不是特别快。

找到离散对数问题的快速解决方案的困难是一些流行的密码算法的一个基本部分，所以如果你找到比维基百科上的任何一个更好的解决方案，请让我知道！

Answer 3

这根本不是一个简单的问题。它被称为计算discrete logarithm，它是modular exponentation的逆运算。

目前还没有有效的算法。也就是说，如果N表示m中的位数，则所有已知算法都在O（2^（N^C））中运行，其中C>；0。