Chapter 2 

Discrete Logarithms and Diffie–Hellman

2.7 A Collision Algorithm for the DLP

在本节中，我们将介绍 Shanks 提出的一种离散对数算法，是一种碰撞或中间相遇算法。这类算法将在第 5.4, 5.5 节中进行更详细的讨论。5.4和5.5。该算法适用于任何群体，而不仅仅是  。对于任意群来说，证明该算法的正确有效性也并不困难，所以我们证明它的一般形式。

我们首先回顾求解DLP的普通蛮力算法的运行时间。

命题 2.19 （DLP 的平凡界）假设我们有群 ，  为  中一个具有阶  的元素（即不存在比  小的正整数  满足  。那么离散对数问题

通过占用  的内存，在   步内将被解决。其中，每一步包含了一次  的乘法运算。

证明：在普通蛮力算法中，我们只需要不断地计算  所有的值都是连续的，每一个值都可以由前一个值生成，所以我们一次只需要存储两个值。如果  存在，那么  将在  次运算内出现。

注 2.20 如果我们在  内进行运算，那么每次计算  将需要  次计算机运算，其中常数  和隐含在  内的常数取决于计算机和用于模乘的算法。那么对于计算机来说，该算法的running time 为  。

接下来介绍的碰撞算法背后的思想其实就是构造两个列表，找到其中在两个表都出现过的元素。对于命题 2.19 中的离散对数问题，碰撞算法的 running time 大约为 ，当  很大的时候，对比  ， 将节省很大的运算开支。

命题 2.21 （Shanks’s Babystep-Giantstep Algorithm，BSGS) 假设我们有群 ，  为  中一个具有阶 的元素。下述算法将使用  内存，在  运行步骤内解决 DLP。

1. 设 
2. 构造两个列表（List 1 中不断地乘以  被称作 “baby step”，List2 中不断地乘以  ，被称作 “giant step”。）

3. 在两个列表中找到相同的值，设 
4. 那么  即为  的解。

证明：首先，我们看到 List2，我们先计算 ，然后计算  完成 List2 的构造。所以两个 List 的构造大约需要  次乘法运算。然后，假设碰撞存在，那么我们用标准的排序和搜索算法可以在大约  的一个小倍数的步骤内找到这个碰撞。所以步骤 3 需要  步，所以算法的总running time 是 。

最后，在步骤 2 中一个列表的长度是 ，所以算法需要  的内存用于列表的存储。

为了证明这个算法是有效的，我们需要证明碰撞总是存在的。为此，我们假设  为  的解，我们将 写为

我们知道 ，所以

所以我们可以将  表示为

显然 ，所以 List1 和 List2 肯定会有相同的元素。

例 2.22 我们将使用下述例子来具体描述 BSGS 的算法流程。

其中  的阶为 ，根据算法，我们设 ，并且计算 ，表 2.4 列出了  的一些值

在表中我们可以找到

因为 ，代入上式

即  为  的解。