Abstract:
In order to realize Elliptic Curve Methods of factorization(ECM) on Graphic Processing Unit(GPU), this paper uses Montgomery curve spot coordinate expression to implement the ECM of large number with length of 112 bit on GeFore9800GTX+ card parallel. Its speed can achieve 1 251 curves per second with bound 8 192 in the first stage confirms. The implementation provides an experimental support to the factorization of surplus factors in NFS of RSA768.
Key words:
Elliptic Curve Methods of factorization(ECM),
Graphic Processing Unit(GPU),
Montgomery curve
摘要: 针对ECM算法在图形处理单元上的实现问题,通过在GeFore9800GTX+显卡上采用Montgomery曲线的点坐标表示,并行实现大数长度为112 bit的ECM算法,选择第1阶段界为8 192,每秒可以验证1 251条曲线。该实现为RSA768数域筛法的剩余因子分解提供了实验支持。
关键词:
ECM算法,
图形处理单元,
Montgomery曲线
CLC Number:
WANG Lei, DIAO Long, HAN Wen-Bao. Rapid Implementation of Elliptic Curve Methods of Factorization on Graphic Processing Unit[J]. Computer Engineering, 2011, 37(6): 135-137.
王雷, 赵龙, 韩文报. GPU上ECM的快速实现[J]. 计算机工程, 2011, 37(6): 135-137.