Using random search and brute force algorithm in factoring the RSA modulus

Autor:	Mohammad Andri Budiman, Dian Rachmawati
Rok vydání:	2018
Předmět:	Random search Sieve of Eratosthenes Factorization Computer science Prime factor Prime number Brute-force search Cryptosystem Primality test Algorithm Computer Science::Cryptography and Security
Zdroj:	Data Science: Journal of Computing and Applied Informatics. 2:45-52
ISSN:	2580-829X 2580-6769
DOI:	10.32734/jocai.v2.i1-91
Popis:	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 cryptanalyst can use factorization algorithms such as Euler’s and Pollard’s algorithms to derive the private keys, p and q. Brute force is an algorithm that searches a solution to a problem by generating all the possible candidate solutions and testing those candidates one by one in order to get the most relevant solution. Random search is a numerical optimization algorithm that starts its search by generating one candidate solution randomly and iteratively compares it with other random candidate solution in order to get the most suitable solution. This work aims to compare the performance of brute force algorithm and random search in factoring the RSA modulus into its two prime factors by experimental means in Python programming language. The primality test is done by Fermat algorithm and the sieve of Eratosthenes.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b9b01f04d704b054e3d027a719b6acfd https://doi.org/10.32734/jocai.v2.i1-91 Zobrazit plný text záznamu