Speeding up wheel factoring method

Abstract

The security of many public key cryptosystems that are used today depends on the difficulty of factoring an integer into its prime factors. Although there is a polynomial time quantum-based algorithm for integer factorization, there is no polynomial time algorithm on a classical computer. In this paper, we study how to improve the wheel factoring method using two approaches. The first approach is introducing two sequential modifications on the wheel factoring method. The second approach is parallelizing the modified algorithms on a parallel system. The experimental studies on composite integers n that are a product of two primes of equal size show the following results. (1) The percentages of improvements for the two modified sequential methods compared to the wheel factoring method are almost 47 % and 90 %. (2) The percentage of improvement for the two proposed parallel methods compared to the two modified sequential algorithms is 90 % on the average. (3) The maximum speedup achieved by the best parallel proposed algorithm using 24 threads is almost 336 times the wheel factoring method.