众所周知，整数分解在密码学中扮演着举足轻重的角色。已知的整数分解算法众多，包括经典的试除法、Pollard’s rho算法、Pollard' s p− 1算法、Williams'p+1算法、椭圆曲线法，一般数域筛法，以及适用于量子计算机的Shor算法等。在这些算法中，椭圆曲线法是应用最广泛的快速整数分解算法之一，它的运行时间取决于待搜寻的因子大小，因此常常部署在一般数域筛法之前，用以移除待分解整数的较小因子。

自 Lenstra 提出只含有第一阶段的椭圆曲线法以来^[1]，针对它最重要的改进是将其扩展为两阶段，这极大地提升了算法搜寻大素因子的能力。截至目前，利用椭圆曲线法搜寻到的最大素因子是一个83十进制位素数，它是由Propper于2013年分解7³³⁷+1 时得到的。原始的椭圆曲线法只包含“第一阶段”。在文献[2]中，Brent 提出了2 种将椭圆曲线法扩展为两阶段的方法：一种是“p−1第二阶段”；另一种是“生日悖论第二阶段”，他也提到了Brent-Suyama扩展以及在第二阶段利用快速多项式求值算法的可能性，这些改进目前已经被广泛应用。在文献[3]中， Montgomery 对p−1法、p+1法以及椭圆曲线法进行了统一阐释，并提出在第二阶段使用FFT扩展，随后，他在文献[4]中对FFT扩展做了进一步改进，极大地提升了第二阶段的速度。自此，椭圆曲线法的基本框架已经建立，发展日趋完善。

2005 年，Zimmermann 等在文献[5]中总结了20年来椭圆曲线法的发展，并在文末提出一个开放问题：是否有可能设计“第三阶段”，进一步提升椭圆曲线法的分解能力？可惜的是，目前并没有发现这一方向的进展。本文通过将第一阶段和第二阶段进行“融合”，把椭圆曲线法扩展为三阶段，以期提升椭圆曲线法搜寻大素因子的能力。文中提出的新算法可以从两方面加以利用：一是在保持同两阶段椭圆曲线法参数相同的情况下，通过增加少许计算量，提升算法找到因子的概率；二是在搜寻同一个因子时，可以减小“光滑参数”的值。

假设本文致力于找出n的某个素因子p。任意选取 a，b，方程 y²=x³+ax+b mod n也蕴含着 y²=x³+ax+b mod p，且后者在椭圆曲线上定义的加法意义下形成群，而前者则不然。这是因为Z_n不是域，在进行椭圆曲线加法的运算过程中，求两点连线的斜率时需要求逆，这一步有可能失效。但恰恰是这点为利用椭圆曲线法分解整数提供了机遇。在mod n的情形下，按照椭圆曲线定义的加法意义进行计算。若求斜率时，分母在Z_n中的逆元不存在，意味着分母和n的最大公因数不为1，该最大公因数是n的非平凡因子（该最大公因数可能为平凡因子 n，但这样的概率很小，并且可以重新选择参数再次进行分解，因此不予考虑）。

由于p是未知的，运算只能在mod n下进行，根据前面的分析，为了找出n的非平凡因子，构造逆元不存在的情形。任选椭圆曲线上一点P₀，设在 mod p 下椭圆曲线群的阶为N_p，那么N_p⋅P₀=O，这里O表示无穷远点。在利用仿射坐标计算N_p⋅P₀时会出现mod n时逆元不存在的情形。由Hasse定理，群的阶

虽然N_p未知，但如果N_p是“光滑的”，那么最终就能找出 p。不是每一条椭圆曲线的阶都是“光滑的”，椭圆曲线法是概率算法，光滑参数选取越大，测试的曲线越多，找出因子 p 的概率越大。

如算法1所示，目前的椭圆曲线法需要2个“光滑参数”B₁、B₂,(B₁<B₂)。如果N _p最大的素因子不超过B₂，并且其余的素因子不超过B₁，就称N _p为(B₁,B₂)“光滑的”。在实际实现椭圆曲线法时，为了提升速度，避免每次运算都计算最大公因数和逆元，一般采用 Montgomery 形式下的齐次射影坐标进行运算。算法1中的步骤1)～步骤4)称为第一阶段（first step或first phase），也是 Lenstra 提出椭圆曲线法的最初版本；步骤 5)～步骤8)称为第二阶段。根据该算法，结合上文的分析，如果

那么算法1能够找到n的素因子（这只是充分条件），这里所有的p和q₁均为素数。

算法1 两阶段的椭圆曲线分解算法

输入 既不能被2整除又不能被3整除的整数n，以及光滑参数B₁≤B₂

输出 n的因子或FAIL

1) 任选椭圆曲线 E mod n 及该曲线上一点P₀=(x₀:y₀:z₀)

2) 在曲线E mod n 上计算

3) 设Q=(x_Q:y_Q:z_Q)，计算g=gcd(n,x_Q)

4) 如果g≠1，输出g并终止，否则继续

5) 对每个素数p(B₁<p≤B₂)

6) 计算(x_P:y_P:z_P)=p·Q

7) 计算g=gcd(n,x_P)

8) 如果g≠1，输出g并终止

9) 输出FAIL

实现时，需要进行快速标量乘运算。因为算法中并没有使用y坐标，所以使用Weierstrass形式并不是最佳选择，常采用齐次的Montgomery形式进行计算，这样的好处是在计算倍点时，可以只计算x坐标和z坐标^[13,14]，相比较 Montgomery 形式和Weierstrass形式而言，使用Edwards曲线可以减少模乘运算，而且找到因子的概率更高。此外，最近有研究提出算法1的量子计算版本^[15]。

本节提出一种算法1的改进算法，将椭圆曲线法扩展为三阶段。通过增加较小的计算量，提高椭圆曲线分解算法做出分解的可能性。如算法2所示，使用3个“光滑参数”B₁、B₂、B₃(B₁<B₂≤B₃)。算法2的步骤1)~步骤4)称为第一阶段，步骤5)～步骤7)称为第二阶段，步骤8)~步骤11)称为第三阶段。

与算法 1对比，算法2的第一阶段与第三阶段分别相当于算法1的第一阶段和第二阶段。若

那么算法2有一定概率找出n的素因子，这里所有的p和q₁、q₂均为素数。

算法2 扩展到三阶段的椭圆曲线分解算法

输入 既不能被2整除又不能被3整除的整数n，以及光滑参数B₁、B₂、B₃

输出 n的因子，或FAIL

1) 任选椭圆曲线 E mod n 及该曲线上一点P₀=(x₀:y₀:z₀)

2) 在曲线E mod n 上计算

3) 设Q=(x_Q:y_Q:z_Q)，计算g=gcd(n,x_Q)

4) 如果g≠1，输出g并终止，否则继续

5) 随机选取 r 个素数p₁,p₂,",p_r,B₁≤p_i≤B ₂,i≤r，计算 $Q_1=\left({\displaystyle \prod _{i=1}^r{p}_i}\right)\cdot Q$

6) 设Q₁=(x_Q1:yQ₁:z_Q1)，计算g=gcd(n,x_Q)1

7) 如果g≠1，输出g并终止，否则继续

8) 对每个素数p(B₁<p≤B₃)

9) 计算(x_P:y_P:z_P)=p·Q₁

10) 计算g=gcd(n,x_P)

11) 如果g≠1，输出g并终止

12) 输出FAIL

预先取定整数B₁、B₂，将算法1中的“光滑参数”取为B₁、B₂，将算法2中的“光滑参数”取为B₁、B₂、B₃，算法2的第一阶段与第三阶段分别等同于算法1的第一阶段和第二阶段。如果N_p最大的素因子不超过B₂，并且第二大的素因子不超过B₁，那么算法1可以找出n的素因子p；如果 N_p最大的素因子不超过 B₂，第二大的素因子不超过B₂，并且第三大的素因子不超过B₁，此时算法1便束手无策，但算法2却有可能找出n的素因子 p。因此算法 2 新设计的第二阶段增大了椭圆曲线法成功分解的概率，增加的消耗是r个椭圆曲线标量乘运算。

若N_p的第二大素因子落在B₁，B₂间，假设B₁、B₂间的素数个数为m，算法2新设计的第二阶段“击中”N_p的第二大素因子的概率为（在$r\ll m$的情况下）。

要使$\text{Prob}\ge \frac{1}{2}$，只需要$r\ge \sqrt{2m\ln 2}$。实践中，这样的消耗增加是微不足道的。举例来讲，如果要搜寻一个规模约为 60 十进制位的素因子，GMP-ECM 7.0.4^[6]推荐使用B₁=2.6 ×10⁸， ¹²B₂=3.2 ×10，此时，算法2第一阶段中需要的椭圆曲线标量乘运算超过π(B₁)=14 195 860个， π表示素数计数函数。而

Li表示对数积分函数。在这种情况下$r\ll \left(B_1\right)$。

第3节阐述了算法2在增加少许计算量的情况下，相比算法1提高了成功分解的概率。从另外一个角度考虑，在搜寻同一个素因子时，算法2可以适当减小“光滑参数”。下面以具体实践来阐述这一论断。

2018年“第三届全国高校密码数学挑战赛”赛题二要求参赛选手分解一个432十进制位的大整数，在将所有小素因子找出后，最困难的部分是分解一个116十进制位的整数n=183114226666 135858918346357409973966780454691208352147 034008159867395391585822600511889005020602 68468088445260535641。

使用算法2对n进行分解，分别取3个“光滑参数”，B₁=3×10⁶，B₂=B₃=1×10⁹，取

利用Suyama参数σ表示Montgomery形式的椭圆曲线。在使用σ=22 824 341 所对应的椭圆曲线进行分解时，成功地搜寻出n的58十进制位素因子 p=345764579608668445952537219644694 7094107078575533908472103。

该椭圆曲线的阶为N_p。

N_p=2⁵·3·5·7·353·1439·4231·20929·28753·144553 3·1533487·2283881·306842093·512194063

若按照 GMP-ECM 7.0.4推荐的搜寻60十进制位素因子的参数设定，B₁=2.6×10⁸，B₂=3.2×10¹²，并利用算法 1，使用该椭圆曲线无法成功分解出这一58十进制位素因子p。

本文将目前流行的两阶段椭圆曲线法扩展为三阶段，并通过理论分析和实践，从两方面阐述了改进后算法的优点，一是在保持同两阶段椭圆曲线法参数相同的情况下，通过增加微不足道的消耗，提升找到因子的概率；二是在搜寻同一个因子时，可以使用较小的“光滑参数”。此外，改进后的算法可能有能力搜寻更大的素因子。椭圆曲线法的瓶颈主要在第一阶段消耗过大，利用算法 2，可以适当减小 B₁，增大B₂与B₃，从而增强使用椭圆曲线法搜寻更大素因子的能力。

致谢

感谢吴宝峰、吕丽君在成文过程中和我进行诸多有益讨论，并提出宝贵意见。