原文来源：Safeheron
大整数分解
1977 年，基于大整数分解难题的密码体系 RSA 诞生，命名自 Ron Rivest、Adi Shamir 和 Leonard Adleman 三位提出者姓氏的首字母。RSA 算法在公钥密码学上作出重要贡献并对全世界产生重要影响，三位提出者于 2002 年获该年度图灵奖。整数分解问题是当今几乎所有公钥密码安全性领域中最重要的课题之一。
RSA 算法的安全性依赖于大整数分解难题，即
将一个大整数分解成若干大素因子的乘积。
有意思的是，虽然这是实践证明的一个「公认」难题，但现在仍无法证明其为 P 问题还是 NP 问题。
针对小因子的几种典型的大整数分解算法有：
Pollards rho 算法
Pollard’s p-1 算法
ECM 算法（Lenstra elliptic curve factorization/elliptic-curve factorization method )
此次我们将介绍 Pollard’s p-1 算法、ECM 算法与 ECM 算法的一个具体实践 —— GMP-ECM。
Pollard’s p-1 算法
对于数据的选取，Pollard p-1 算法采用随机数的策略。如果随机不出结果，那么就从小于 B（B-powersmooth）的质数列表里去生成 d ，直到质数列表被用尽。
输入：n（合数）
输出：n 或失败的非平凡因子
STEP 1
选择一个平滑边界 B
STEP 2
定义：
STEP 3
随机选择一个和 n 互质的数 a
STEP 4
计算：
STEP 5
如果 1< g <n ，返回 g
如果 g = 1 ，选择一个更大的 B 并转到步骤 2 或返回失败
如果 g = n ，选择一个更小的 B 并转到步骤 2 或返回失败
ECM 算法
对于这个方法的改进，ECM 方法在 Pollard’s p-1 的基础上引入了随机的椭圆曲线，将原本的乘法群转换为椭圆曲线的点构成的群。椭圆曲线方法是一种基于数论的算法，利用椭圆曲线上的点的性质和运算规则，寻找满足一定条件的因子。
算法概述
利用 ECM 算法寻找 n 的因子分为三步：
STEP 1
选择 B ，并计算 m = lcm( 1, 2,...,B)
STEP 2
在 Z/NZ 上选择一条随机的曲线与曲线上的随机一点 P
STEP 3
计算 mP。在计算过程中，如果不能计算出对应的椭圆曲线中的点的加法，则找到了 n 的因子，否则可以更换一条曲线进行计算，或返回失败
ECM 算法能够找到 n 因子的原理在于，当随机选取的椭圆曲线阶 g 为 B-smooth 时，在计算 mP 的过程中，如果遇到 gcd(v, p)=p 或者 gcd(v, p)=q ，会计算得到 gcd(v, n) 的非平凡因子。
一种 ECM 实现 —— GMP-ECM
GMP-ECM 的实现基于原有的 ECM 方法进行了优化。
首先是对整体的算法过程进行的优化。在 GMP-ECM 中计算因子分为两个步骤，每一个步骤选取两个 (B 1, B 2) 。
算法分为两个阶段，分别使用 B 1 与 B 2 进行运算。在 Stage 1 的计算与 ECM 类似。
Stage 1
在 Stage 1 的计算中，GMP-ECM 优化了椭圆曲线的选取与计算。
随机的椭圆曲线生成
椭圆曲线运算
在 GMP-ECM 中使用 Montgomerys 形式的椭圆曲线，在求点的乘法或加法过程遵循如下规则：
Stage 2
算法复杂度
在实际的运算过程中，由于算法存在随机性，找到数 n 的因子 p 的时间可能存在差异。另外，算法能否分解与分解所需的时间也与 B 1、B 2 的选取有关（可以参考 GMP-ECM 文档推荐的 B 1、B 2 值进行计算）。
示例
以大整数 N（2048 bit）为例：
N = 0x A 2862 FB 145 AC 7 CE 580 E 0 BFF 3 CEFF 42646050 F 8 C 611 D 36 A 3026 E 6 EFB 433 B 5 CDD 9 EEFBA 893 E 3 F 25 C 23 A 4951 BA 20992680162934 CBDB 6876 CC 791738 C 140 C 6 EA 6 EC 82938 F 7 E 18 C 5 F 0760367 CF 2088 3D CAB 1 D 6885 E 22 2B BC 7 A 1 B 5 D 434 FD 9 FC 148 E 387 FA 9 AD 69 CE 708 FDDDE 3 E 963 F 9 AB 2 AF 2046 A 37 D 7 DBA 21 BC 92 E 6 F 2 A 631 C 3 E 7770 C 77 C 95 FAD 6 F 1 DC 60 D 9 F 0645 AEF 2C C 5 D 0 3D 2151 E 35443 FE 0 F 90 F 1 E 2 EAE 58489 C 4450 C 8281 EDCC 58 DDB 409 C 306797 C 616954 ACABCE 4881 E 40 ABDD 2689 A 9 F 7596 F 29 C D5 CB 4 2C 75 2D A 9306 E 7 DB 87 CAC 8957 E 3 CA 165421 CF 9 E 1 B 7220759 A 10588 B 386 E 33 FD 8 E 762 E 9 2C 9 F 79 D5 0150 EF 5 FCA5F411DE23B8DFFE47A95D48ADDCF4797565
调用解析工具（https://github.com/Safeheron/integer-factorization）使用 GMP-ECM 方法分解：
ecm -c 2 25 e 4 1.3 e 8 -mpzmod threads: 2 mod: 1
A2862FB145AC7CE580E0BFF3CEFF42646050F8C611D36A3026E6EFB433B5CDD9EEFBA893E3F25C23A4951BA20992680162934CBDB6876CC791738C140C6EA6EC82938F7E18C5F0760367CF20883DCAB1D6885E222BBC7A1B5D434FD9FC148E387FA9AD69CE708FDDDE3E963F9AB2AF2046A37D7DBA21BC92E6F2A631C3E7770C77C95FAD6F1DC60D9F0645AEF2CC5D03D2151E35443FE0F90F1E2EAE58489C4450C8281EDCC58DDB409C306797C616954ACABCE4881E40ABDD2689A9F7596F29CD5CB42C752DA9306E7DB87CAC8957E3CA165421CF9E1B7220759A10588B386E33FD8E762E92C9F79D50150EF5FCA5F411DE23B8DFFE47A95D48ADDCF4797565
********** Factor found in step 2: 1021791499165844943393503 21 52761 ms
成功找到素因子 1021791499165844943393503。
