In cryptoanalysis, factoring a positive integer n into two prime factors p and q plays an important role in breaking the RSA (Rivest, Shamir, Adleman) cryptosystem. Fermat’s method is one of the most efficient techniques for integer factorization, such that the difference between the prime factors is \(\delta =\root 4 \of {n}.\) The drawback of Fermat’s method is that the time complexity increases with an increasing \(\delta\) . In this paper, a new method is designed for a parallel shared model to reduce the execution time of finding prime factors and increase the effectiveness of Fermat’s method when \(\delta> \root 4 \of {n}\) . The proposed algorithm is based on the removal of a large number of integers from the search space using two modulo operations. Extensive experiments are implemented on three algorithms with different values of (1) \(n=2^i, 6\le i\le 11,\) (2) \(\delta =\root 4 \of {n}+k, k=4, 8, 12, 16, 20\) , and (3) the number of threads, \(t=2^j, 1\le j\le 4\) . The experiments show that the running time of the proposed algorithm is approximately t-time and 3.9-time faster than those of the previously known sequential and parallel algorithms, respectively. Furthermore, the speedup of the proposed algorithm is linear.
