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 59
- Downloads 0
Data Analysis as a Method to gather Data to study the Relation between Fundamental Rights and Rule of Law
The research described here involves the relation between fundamental rights and the rule of law. In the end we want to find out what meaning is attributed to ‘rule of law’ by the European Court of Human Rights. In this...
Subject Bias in Image Aesthetic Appeal Ratings
Automatic prediction of image aesthetic appeal is an important part of multimedia and computer vision research, as it contributes to providing better content quality to users. Various features and learning methods have b...
Improving Data Collection on Article Clustering by Using Distributed Focused Crawler
Collecting or harvesting data from the Internet is often done by using web crawler. General web crawler is developed to be more focus on certain topic. The type of this web crawler called focused crawler. To improve the...
Efficiency of Local Government Units in North Western Philippines as to the Attainment of the Millennium Development Goals
This study entitled “Efficiency of Local Government Units in Northwestern Philippines as to the Attainment of the Millennium Development Goals” determined the performance of the four provinces and eight cities in Region...
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...