1977 年，基于大整数分解难题的密码体系 RSA 诞生，命名自 Ron Rivest、Adi Shamir 和 Leonard Adleman 三位提出者姓氏的首字母。RSA 算法在公钥密码学上作出重要贡献并对全世界产生重要影响，三位提出者于 2002 年获该年度图灵奖。整数分解问题是当今几乎所有公钥密码安全性领域中最重要的课题之一。

RSA 算法的安全性依赖于大整数分解难题，即

有意思的是，虽然这是实践证明的一个「公认」难题，但现在仍无法证明其为   问题还是  问题。

针对小因子的几种典型的大整数分解算法有：

• Pollard's rho 算法

• Pollard’s p-1 算法

• ECM 算法（Lenstra elliptic curve factorization/elliptic-curve factorization method )

此次我们将介绍 Pollard’s p-1 算法、ECM 算法与 ECM 算法的一个具体实践 —— GMP-ECM。

Powersmooth：如果一个数  的所有的质数幂  都是 B-smooth 的，即  ，则称  为 B-smooth。

Pollard’s p-1 算法是 John Pollard 在 1974 年设计的一种利用费马小定理的整数分解算法。根据费马小定理，  ，假设待分解的  存在一个因子为  ，我们可以表示为  。  存在  ，因此  是  的倍数，由此可到

对于数据的选取，Pollard p-1 算法采用随机数的策略。如果随机不出结果，那么就从小于  （B-powersmooth）的质数列表里去生成  ，直到质数列表被用尽。

Pollard’s p-1 方法要求  存在因子  ，并且  拥有较小的因子，因此可以利用  找到  的因子。但是当  的因子较大时，Pollard’s p-1 大概率不能得到  的分解。

对于这个方法的改进，ECM 方法在 Pollard’s p-1 的基础上引入了随机的椭圆曲线，将原本的乘法群转换为椭圆曲线的点构成的群。椭圆曲线方法是一种基于数论的算法，利用椭圆曲线上的点的性质和运算规则，寻找满足一定条件的因子。

假设  是  的一个质因数，考虑椭圆曲线  ，基于  ，根据 Hasse 定理，可以知道椭圆曲线的阶  满足  。当椭圆曲线的  和  发生变化时，椭圆曲线的阶会落在范围   中。

利用 ECM 算法寻找  的因子分为三步：

ECM 算法能够找到  因子的原理在于，当随机选取的椭圆曲线阶  为 B-smooth 时，在计算  的过程中，如果遇到  或者  ，会计算得到  的非平凡因子。

GMP-ECM 的实现基于原有的 ECM 方法进行了优化。

首先是对整体的算法过程进行的优化。在 GMP-ECM 中计算因子分为两个步骤，每一个步骤选取两个  。

算法分为两个阶段，分别使用   与  进行运算。在 Stage 1 的计算与 ECM 类似。

首先计算在椭圆曲线  上的点  的积：

在 Stage 1 的计算中，GMP-ECM 优化了椭圆曲线的选取与计算。

在计算因子的过程中，当随机生成的椭圆曲线的阶在  范围内变化，且随机的椭圆曲线是 B1-smooth 时，可以分解  。在 GMP-ECM 中对于椭圆曲线的生成运用一定方法，可以使生成的椭圆曲线阶满足某些特征，例如：

• Suyama's form：保证椭圆曲线的阶  能被 12 整除

• Montgomery's form：保证椭圆曲线的阶  能被 3 整除

  
  

在 GMP-ECM 中使用 Montgomery's 形式的椭圆曲线，在求点的乘法或加法过程遵循如下规则：

•   

• 计算：  

  计算：  

•   

• 计算：  

  计算：  ,   ，其中  为椭圆曲线  中的参数

  
  

GMP-ECM 的第一阶段主要计算椭圆曲线  上的点  。如果失败，即  ，则在第二阶段将查找范围扩大至  ，并且新范围内存在一个质数  ，使得  。

Stage 2 的主要思想为中间相遇（meet-in-the-middle）策略：

• 在 Stage 2 计算一个  和  

• 若  表明  。因此计算   即可获得因子  

  
  

ECM 方法找到一个数  的因子  预计需要的时间为  ，其中  ，  则代表乘法模  的复杂度。

在实际的运算过程中，由于算法存在随机性，找到数  的因子  的时间可能存在差异。另外，算法能否分解与分解所需的时间也与  、  的选取有关（可以参考 GMP-ECM 文档推荐的  、  值进行计算）。

Safeheron 将持续输出更多技术内容，希望伴随传统行业以及区块链行业用户前行，提供有价值的参考。