On Factoring The RSA Modulus Using Tabu Search

Abstract

It is intuitively clear that the security of RSA cryptosystem depends on the hardness of factoring a very large integer into its two prime factors. Numerous studies about integer factorization in the field of number theory have been carried out, and as a result, lots of exact factorization algorithms, such as Fermat’s factorization algorithm, quadratic sieve method, and Pollard’s rho algorithm have been found. The factorization problem is in the class of NP (non-deterministic polynomial time). Tabu search is a metaheuristic in the field of artificial intelligence which is often used to solve NP and NP-hard problems; the result of this method is expected to be close-to-optimal (suboptimal). This study aims to factorize the RSA modulus into its two prime factors using tabu search by conducting experiments in Python programming language and to compare its time performance with an exact factorization algorithm, i.e. Pollard’s algorithm. The primality test is done with Lehmann’s algorithm.