On Factoring The RSA Modulus Using Tabu Search
Journal Title: Data Science: Journal of Computing and Applied Informatics - Year 2017, Vol 1, Issue 1
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.
Authors and Affiliations
Ade Candra, Mohammad Budiman, Dian Rachmawati
Keywords
Related Articles
- EP ID EP435200
- DOI 10.32734/jocai.v1.i1-65
- Views 45
- Downloads 0
On Factoring The RSA Modulus Using Tabu Search
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 theo...
Using random search and brute force algorithm in factoring the RSA modulus
Abstract. The security of the RSA cryptosystem is directly proportional to the size of its modulus, n. The modulus n is a multiplication of two very large prime numbers, notated as p and q. Since modulus n is public, a c...
A Framework to Ensure Data Integrity and Safety
The technology development allows people to more easily communicate and convey information. The current communication media can facilitate its users to send and receive digital data, such as text, sound or digital image....
Time Series And Data Envelopment Analysis On The Performance Efficiency Of Dmmmsu-South La Union Campus
This study entitled “Time Series and Data Envelopment Analysis (DEA) on the Performance Efficiency of DMMMSU-South La Union Campus” determined the performance of the Don Mariano Marcos Memorial State University -South La...
Implementation and comparison of Berry-Ravindran and Zhu- Takaoka exact string matching algorithms in Indonesian-Batak Toba dictionary
Indonesia has a variety of local languages, which is the Batak Toba language. This time, there are still some Batak Toba people who do not know speak Batak Toba language fluently. Nowadays, desktop based dictionary is on...