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

给出了整数分解的两种算法,试除法和Pollard算法.根据素数分布的规律,通过减少试除次数提高了试除法运算效率,使得其性能显著提高;对Pollard算法进行分析后,变换随机序列产生式并重启算法使算法运行更稳定有效.给出了这两类改进算法的运行时间对比表,结果表明,改进的试除法在分解32位内小整数效果更佳而改进的Pollard算法在分解32位以上大整数有明显的优化.

Analysis and improvement on two kinds of integer factorization algorithm

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 function,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.