A Novel Dataset and Algorithm for Identifying Divisors of an Odd Composite Integer Using Distributed Parallel Network
Zhiying Liu
Guangzhou College of Applied Science and Technology, Guangzhou City, 511370, PR China.
Hao Li
Guangzhou College of Applied Science and Technology, Guangzhou City, 511370, PR China.
Xingbo Wang *
Guangzhou College of Applied Science and Technology, Guangzhou City, 511370, PR China and Foshan University, Foshan City, 528000, PR China.
*Author to whom correspondence should be addressed.
Abstract
For a given odd integer N = pq, where p and q are prime factors satisfying 2 < p < q, we propose a novel dataset that can accumulate multiples of p and q. By calculating the greatest common divisor (GCD) between N and one of these identified multiples using specific search algorithms, either p or q can be obtained. The proposed dataset exhibits geometric symmetry with respect to its center, which significantly reduces the search space. Subsequently, we develop an algorithm tailored for distributed parallel networks to perform searches on this dataset and compute a divisor of N. Experimental results demonstrate that combining the newly defined dataset with the designed algorithm achieves significantly superior efficiency, with processing speeds 100 or even 1000 times faster than those reported in previous studies.
Keywords: Dataset, integer factorization, distributed parallel computing, randomized algorithm