利用椭圆曲线方法和GMP库分解大整数

郭汝廷

1 引言

2 椭圆曲线因子分解方法介绍。

年 H.W .Lenstra 创造了椭圆曲线因子分解方法。该方法是在Pollard p-1 方法的基础上发展而成。如果整数 N 有素因子 p ，p-1 是光滑数。用 p-1 方法就可以找到这个素因子。但当p 比较大时 p-1 光滑的概率比较小。所以该方法不易找到大的素因子（比如40位以上）。

N}F7TQ4_%HRS@T[T7F]1]IS点击并拖拽以移动                        （1）

的点集 36{TDICRKE2`3Z_OQ@WW{$K点击并拖拽以移动，其中0H4R～2KJ948523$T2[29）6G点击并拖拽以移动且$$ZU8NGY8（[5AKMI2}14@YH点击并拖拽以移动此点集加上无穷远点在定义加法运算后构成一个Abel 群。

给定椭圆曲线E上的两个点{W[`DW6{3F（RX{R`HE3MO6U点击并拖拽以移动和椭圆曲线}99T@4L9$CI4YPTKI（7E～`H点击并拖拽以移动

JKC～%%7@～VMV～ASB`G}（YEE点击并拖拽以移动用下面的公式计算：

7Y（T9QI%D56J[9V8NCGITKR点击并拖拽以移动

9SY5BS4LQ1OZCF_N_1[JG）H点击并拖拽以移动

ZIK6（QUM]KS[2BGRHUJOID6点击并拖拽以移动

如果IHO{HTJJ___S3H）Z4KK][）I点击并拖拽以移动为一素数，Helmut Hasse证明了群 G 的阶介于FB9VAU6H]{88CT95JY_4$VH點击并拖拽以移动和AQR{%W%GPEQ6Z）NX～UH{J9R点击并拖拽以移动之间。通过改变a，b的值可以得到阶不同的群。如果该群的阶光滑，就可以找到素因子 p 。这样对同样大小的 p 利用不同的椭圆曲线可以得到阶介于0K]P4PB1H6（KZH5X_～_$8ET点击并拖拽以移动 和_WDH}JG6PH（QX{QU3250{]U点击并拖拽以移动之间的多个群，而 p-1 方法只能限制在阶为 p-1 的乘法群。Lenstra 的椭圆曲线因子分解方法算法如下：

输入： 奇合数。

（1）选择（E，P），ET5]}E$1DZU39H6E）]2K937点击并拖拽以移动，BL%PB9ZJ%9ESYZ8G94PXWSA点击并拖拽以移动，P是E在Z上的点;

（2）计算 {BVM（{9I@46IR48X9V[VZ$6点击并拖拽以移动，若 7JDHZTA）J6}JFV[}$7Q]（82点击并拖拽以移动 则输出d;否则返回第一步;

（3）选择 BJ]INPKPA9I{1DI（8WSEEMX点击并拖拽以移动;

（4）计算 $7`F]K）X3）N9KUTP42U329L点击并拖拽以移动其中P4Y[Z$V$17JF]）5%}1BVG3J点击并拖拽以移动;

（5）计算kP （mod m）点击并拖拽以移动若在计算过程中出现整数s对模m 的求逆运算无法继续，则计算[PJV3_44R}B`SL6{（（8）5NK点击并拖拽以移动若ULG54[OW`}9GRT[QBDO$N9M点击并拖拽以移动 则输出 d。否则返回第一步。由于求逆的运算比较耗时，Montgomery 用齐次坐标对上述算法进行了如下改进。

选择椭圆曲线

Z（FP}6LXBY[2FY7`4435@{W点击并拖拽以移动（2）

对于椭圆曲线（2）Montgomery 给出了如下的加法公式和倍点公式

GIK42HO$6$B～H$3RRG%XY5S点击并拖拽以移动

利用上面的公式，计算点的加法需要进行6次乘法和4次加法运算;计算倍点需要进行5次乘法和4次加法。利用改进后的方法，Brent分解了第十个Fermat数。

3  GMP 大整数运算库和因子分解实例

GMP大整数运算库是一个开源库。该库提供了长整数和有理数以及高精度浮点的 C语言库函数。数据运算精度仅受计算机物理内存的限制。该运算库的源代码在CentOS6.5操作系统上编译后即可使用。利用该运算库的 mpz_t 数据类型，可以开发基于椭圆曲线因子分解方法的C语言程序，也可以利用它提供的C++类mpz_class。利用该运算库编写的程序，很容易找到一个大合数30位以内的素因子。

例如用该方法选择椭圆曲线可以分解梅森数

其中P₉₆是一个96位的素数。

4 结束语

（作者单位：山东大学信息化工作办公室）