计算离散对数

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

没有已知的有效算法。也就是说,如果n表示m中的位数,则所有已知算法都在o(2^(n^c))中运行,其中c>0。

从%运算符,我假设您正在处理整数。

你在努力解决 the Discrete Logarithm 问题。合理的算法是 Baby step, giant step 虽然还有很多其他的,但都不是特别快。

很难找到离散对数问题的快速解决方案,这是一些流行的密码算法的一个基本部分,所以如果你找到一个比维基百科上任何一个更好的解决方案,请告诉我!

Discrete logarithm 是个难题

计算离散对数被认为是困难的。不 计算离散对数的有效通用方法 传统的计算机是众所周知的。

我将在这里添加一个简单的Bruteforce算法,它尝试来自 1 到 m 如果找到了,输出一个解决方案。请注意,问题可能有多个解决方案,或者根本没有解决方案。此算法将返回尽可能小的值或 -1 如果它不存在。

def bruteLog(b, c, m):
    s = 1
    for i in xrange(m):
        s = (s * b) % m
        if s == c:
            return i + 1
    return -1

print bruteLog(5, 8, 13)

在这里你可以看到 3 实际上是解决方案:

print 5**3 % 13

有一个更好的算法,但是因为它经常被要求在编程比赛中实现,我只给你一个链接 explanation .

由于在python标签下提出了这个问题的副本,下面是baby-step的python实现,正如@markbeyers指出的那样,biggant-step是一种合理的方法(只要模数不太大):

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"

在上面的实现中,一个显式的 N 即使在 p 是密码学上的大。只要指数小于 N**2 . 什么时候? n 如果省略,则始终会找到指数,但不一定在您的生命周期中或在您的计算机内存中找到,如果 磷 太大了。

例如,如果

p = 70606432933607
a = 100001
b = 54696545758787

然后“pow(a,b,p)”计算为67385023448517

和

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

这在我的机器上花了大约5秒钟。对于这些尺寸的指数和模量,我估计(基于定时实验)蛮力可能需要几个月。

如前所述,一般问题很难解决。然而,如果且仅当您知道e将很小时(就像在您的示例中一样),找到e的一种精确方法就是尝试1中的每个e。

btw e==3是示例的第一个解决方案,显然,与求解非离散版本相比,您可以在3个步骤中发现这一点,并天真地寻找整数解,即。

e=log(c+n*m)/log(b),其中n为非负整数

在9个步骤中发现e==3