两类整数分解算法的分析与改进  

Analysis and improvement on two kinds of integer factorization algorithm

作　　者：伍传敏[1] 孟金涛[1] 刘俊芳[1] 

机构地区：[1]华中师范大学计算机科学系,湖北武汉430079

出　　处：《计算机工程与设计》2007年第17期4094-4095,4104,共3页Computer Engineering and Design

摘　　要：给出了整数分解的两种算法,试除法和Pollard算法。根据素数分布的规律,通过减少试除次数提高了试除法运算效率,使得其性能显著提高;对Pollard算法进行分析后,变换随机序列产生式并重启算法使算法运行更稳定有效。给出了这两类改进算法的运行时间对比表,结果表明,改进的试除法在分解32位内小整数效果更佳而改进的Pollard算法在分解32位以上大整数有明显的优化。Two algorithm of integer factorization are given, which is trial division and Pollard algorithm, According to the distribution of the prime numbers and reducing the times of trial division to improve its efficiency, which greatly improve performance of the trial di- vision. After the analysis of Pollard algorithm, this work restart the algorithm with a different random sequence produce fimction, this will let the algorithm run more effectively. At last, a running time table of the two kinds of algorithm are given. Results show that the proposed trial division is accurate and effective in factorizing small integer on 32 digit bit and Pollard algorithm is effective on others.

关 键 词：素数 合数 整数分解 试除法 Pollard算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]