Dynamic Scaling Pollard’s P-1 Algorithm

The integer factorization problem is a hard problem in classical. Let N=PQ, where P and Q are large primes. Pollard’s P-1 Algorithm is an efficient integer factorization algorithm while all the prime factors of P−1 are small. However, the previous variants of Pollard’s P-1 algorithms require a strict bound on the prime factors, and the running time depends on the bound instead of the actual size of prime factors, which is undesirable. This paper firstly designs a dynamic scaling version of Pollard’s P-1 Algorithm (abbreviate as DSP) to solve this problem and also accelerate the algorithm’s efficiency by applying a fast multiplication method to it. Additionally, DSP saves the cost in computing the product of prime factors with high enough exponent by repeatedly using product of primes with low exponent. We also give the complexity analysis for our proposed algorithm and the latest published variant of Pollard’s P-1 Algorithm named IPP1 (Kritsanapong Somsuk, Symmetry). Moreover, we give a theoretical comparison between IPP1 and our algorithm. In particular, we show that our algorithm costs less than IPP1 in more than 95% while in IPP1 the bound of prime factors of P-1 is set to at least 64. Additionally, we also test several instances in factoring 1024-bit integers N=PQ in experiment. We firstly construct the P−1 as a product of several randomly generated 30-bit numbers to ensure its solvability by the Pollard’s P-1 Algorithm, then test four variants of Pollard’s P-1 Algorithm. The experimental result shows that our algorithm is most efficient among them. Its efficiency improvement performs more apparently while the exponent of a prime factor in P−1 is large. In factoring 1024-bit integer, our algorithm solves it nearly 23.5 times faster than IPP1, 16.4 times faster than the Original Pollard’s P-1 Algorithm (J. M. Pollard, MPCPS), 35.6 times faster than the trivial Pollard’s P-1 Algorithm (D. Bishop, Introduction to cryptography with Java applets).