密码学系列｜ 3.5 Pollard’s − 1 分解算法

3.5 Pollard’s  − 1 Factorization Algorithm

  在 3.4 一节中我们能够比较容易地去检测一个大数是否（可能）是素数。这很重要，因为 RSA 密码系统需要大素数才能操作下去。

  对于 RSA 来说，其安全性依赖于大数分解这一数学难题。而对因式分解的研究至少可以追溯到古希腊，但直到计算机的出现，人们才开始发明能够分解大数的算法。RSA 的悖论在于，为了使 RSA 更高效，我们希望使用一个尽可能小的模数 。另一方面，如果对手可以分解 ，那么我们的加密消息就不安全。因此，我们需要理解，或者尽可能量化大数分解的困难性，而其中的关键就是需要注意当前用于大数分解的不同算法的效率（算法复杂度）。

  在接下来的几节中，我们将不同程度地讨论一些已知的大整数分解方法。第 6.6 节描述了使用椭圆曲线的另一种方法。有兴趣研究这一主题的读者也可以查阅《A Course in Computational Algebraic Number Theory.》、《, Prime Numbers》、《Prime Numbers and Computer Methods for Factorization》、《Primality Testing and Integer Factorization in Public-Key Cryptography》以及这些作品中引用的参考文献。

  我们首先从 Pollard’s  − 1 算法开始。尽管这个方法并不适用于所有数字，但对于某些类型的数字，它是非常有效的。Pollard 的方法表明，存在乍一看似乎是安全，但实际上不安全的 RSA 模块，仅此一点就值得对Pollard 的方法进行研究。此外，Pollard’s  − 1方法为 Lenstra 的椭圆曲线因式分解方法提供了灵感，我们将在后面的第 6.6 节中研究该方法。

  现在我们有一个整数 ，我们的任务是分解整数  得到 。假设通过运气、努力或其他方法，我们找到了一个具有以下性质的整数 ，

  这意味着存在整数  以及  满足

  考虑一下如果我们随机选择一个整数  并计算  会发生什么？根据费马小定理，我们知道

  由于指数 ，所以  不太可能在模  下与 1 同余。因此随机选择一个整数 ，我们有很大的可能发现

  这就意味着我们用简单的 gcd 算法就可以分解出  来：

  这一切都很顺利，但你可能会问，我们在哪里可以找到这样一个指数 ，它可以被 整除，而不被  整除。Pollard 观察到，如果  是由一系列小素数乘积而来，那么它就能整除 （主要针对那些不太大的 ，否则也算不出它的阶乘）。那么想法出现，对于 ，我们随机选择一个整数 ，并计算

  （实际操作中我们通常简单的固定 ）如果 gcd 算法的结果是1，那么我们继续用下一个 ，如果 gcd 的结果是 ，那么我们就不太幸运了，不过兴许换一个  就能够成功。如果我们得到了一个大于  小于  的整数，那么就意味着我们找到了  的一个非平凡因子，算法结束。

注 3.28 在我们准备用代码实现 Pollard 的想法之前，这里有两个需要注意的点。第一，我们需要关注  值的大小。尽管 ,我们也选一个大小适中的 ，我们直接计算  的值也是不太适合。因为  的十进制位长高达  ，这比宇宙中已知基本粒子的数量还要多。幸运的是，我们并不需要准确的计算出它，这里我们只关注  和  的最大公因子，因此计算  就足够了，然后我们再计算其与  的 gcd。因此我们实际上不需要处理比  大的数字。

第二，我们甚至不需要去计算指数 。假设我们在上一步已经计算好了 ，那么我们可以通过以下的式子计算下一个值

这引出了我们在表 3.3 中介绍的算法。

注 3.29 计算  需要多长的时间呢？我们在第 1.3.2 一节中给出的计算  的算法至多需要  步，其中每一步都是模  的乘法。根据 Stirling 公式，如果  比较大，那么 。所以我们可以在  步内计算出  。因此，即使  比较大，计算  也是可行的。

例 3.30 我们使用 Pollard’s p−1 method 去分解 ，从  开始，然后连续增大指数，计算阶乘，我们发现

  从最后一行我们得到一个非平凡因子 ，是素数，另外一个因子 ，也是素数。

  之所以我们在  成功，是因为这里我们  可以分解为如下小素数的乘积：

  对于另外一个因子有 ，并不是由小（对于这里来说）因子乘积而来。

例 3.31 这里我们使用更大的数字，另 ， 然后我们有

注 3.32 注意到 Bob 和 Alice 在创建RSA密钥时很容易就能避免 Pollard’s  − 1方法。他们只需检查他们选择的秘密素数  和  ，是否满足  或者  能够完全分解为小素数的乘积这一性质。从密码学的角度来看，Pollard’s  − 1方法的重要性在于下面的一课。乍一看，大多数人不会想到  的因式分解性质会与分解  的难度有关。其寓意是，即使我们基于一个看似困难的问题（如整数分解）构建密码系统，我们也必须警惕这个问题的特殊情况，因为一些微妙和不那么明显的原因，这些问题比一般情况更容易解决。我们已经在离散对数问题的Pohlig–Hellman算法中看到了一个例子（第2.9节），稍后我们将在讨论椭圆曲线和椭圆曲线离散对数问题时再次看到它。

注 3.33 我们尚未讨论 Pollard’s  − 1 算法的成功率，假设  是随机选择的大小大致相同的素数。如果至少有一个  或  完全分解为小素数幂的乘积。那么明显  会是偶数，所以我们可以得到一个因子 ， 然后， 或多或少应该像一个大小约等于  的随机数。那么我们引出以下问题：

随机选择一个大小约等于  的整数，其能够整除  的概率为多少。

注意到，如果 ，那么每一个整除  的素因子  满足 。一个其素因子均小于或者等于  的数，我们称之为 。那么一个很自然的想法，如果随机选择一个大小约为  的整数，其为  的概率是多少。即

给出整数n，我们应该如何选择 ，以使得我们随机选择的大小约为  的整数有一个合适的概率为 ？

所有现代整数分解方法的效率（或缺乏效率）在很大程度上取决于这个问题的答案。我们将在第 3.7 一节中研究 smooth number。