离散对数计算的Sherwood 算法

   问题描述:设 a=g^x mod p,记 log g,p a=x,称 x 为 a 的(以 g 为底模除 p)对数。从 p,g,a 计算 x 称为离散对数问题。
  问题在于:给出 p,g,a,怎么求 x

  简单算法:
1 ∀x, 计算 g ^x
最多计算 0≤x≤ p-1 或 1≤x≤p,因为实际上离散对数<g>是循环群;
2 验证 a=g ^x mod p 是否成立。

dlog(g, a, p) {                // 当这样的对数不存在时,算法返回 p
     x ← 0; y ← 1;
    do {
        x++;
        y ← y*g;       // 计算 y=g^ x
    }  while ( a ≠ y mod p) and (x ≠ p);
    return x
}
问题:最坏 O(p),若 P 很大怎么办?所以简单算法不行,而且 x 的算出来的快慢取决于 a 的取值, a 的取值能够让算法较早找到正确的 x,则算法很快就完了,否则很慢,直到 p。

Sherwood