Enhanced Integer Factorization Method: Sequential and Parallel Approaches

Abstract

Integer factorization plays a foundational role in asymmetric cryptography systems, notably the Rivest, Shamir, and Adleman (RSA) cryptosystem. This paper presents an improvement of the integer factorization from both sequential and parallel computational perspectives. The algorithm is based on polynomial evaluation and the greatest common divisor. The objectives of these improvements are to decrease the execution time and memory consumption associated with the process of finding prime factors. Experimentally, we use different values of parameters (1) the number of bits n, (2) the difference between two factors, and (3) the number of processors in the parallel model. The experimental results indicate that both proposed methods, sequential and parallel, yield significant improvements regarding running time and memory usage when the difference between the two factors is n1/3 and n1/4. The average improvement observed is 99% in running time, with memory consumption reduced to a constant. This characteristic is important for limited hardware devices. Furthermore, the proposed parallel method demonstrates scalability and achieves sublinear speedup.