<p>由于这个问题的副本是在Python标签下提出的,这里有一个baby step,giant step的Python实现,正如@MarkBeyers指出的,这是一个合理的方法(只要模不太大):</p>
<pre><code>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"
</code></pre>
<p>在上面的实现中,即使<code>p</code>是密码学上大的,显式<code>N</code>也可以传递给fish以获得小指数。只要指数小于<code>N**2</code>,它就会找到指数。当省略<code>N</code>时,将始终找到指数,但如果<code>p</code>太大,则不一定在您的生命周期或计算机内存中找到指数。</p>
<p>例如,如果</p>
<pre><code>p = 70606432933607
a = 100001
b = 54696545758787
</code></pre>
<p>然后“pow(a,b,p)”计算为67385023448517</p>
<p>以及</p>
<pre><code>>>> baby_steps_giant_steps(a,67385023448517,p)
54696545758787
</code></pre>
<p>这在我的机器上花了5秒钟。对于这些尺寸的指数和模数,我估计(基于计时实验)蛮力可能需要几个月的时间。</p>