大步小步算法

大步小步算法（也称为香克斯离散对数算法）计算循环群中元素的离散对数。 虽然该算法优于在运行时天真地尝试所有可能性，但对于非常大的群体来说，它实际上仍然不可行。

我们正在寻找离散对数 x := log g ⁡ a  阶的有限循环群并且 a = g x 一个组元素。

通过除以余数，唯一表示 x = i m + j 。 这里， m ∈ Θ ( n )通常被选择（见朗道符号）来限制 i 和 j 大小相似。 因为 a = g x = g i m + j ，这个表示产生了算法 g j = a g − i m 。

该算法通过首先创建一个婴儿步骤表 ( j , g j ) 来寻找满足此属性的一对 ( i , j ) . 然后，为了增加 i，连续计算“巨大的步骤” a ( g − m ) i并检查是否与一个值相等在表格中。 如果有这样的碰撞，这就是我们正在寻找的对，并且输出对数 i m + j  。

输入：有限循环群 G ，生成器 g ，群元素 a

输出： x := log g ⁡ a  其中 g x = a

• 计算 n := | 格 | , m := ⌈ n ⌉与舍入函数 ⌈ ⋅ ⌉ .
• 对于所有 j ∈  ：计算 g j并存储 ( j , g j ) 在表格中。
• 对于所有 i ∈  ：计算 a ( g − m ) i 并在表的第二列中查找它。 如果找到，输出 i m + j 。

因为 a ( g − m ) i = a ( g − m ) i − 1 g − m 最后一步中的组元素可以很容易地从上一次迭代的组元素中计算出来。