Foundations of Blockchain

Prime factorization

Prime factorization is a concept in number theory regarding the decomposition of a number into the product of two prime numbers. Prime factorization is a subset of integer factorization, in which a composite number is factored into the product of any two integers.

It is challenging to find the factors of semi-primes (numbers that result from the product of two prime numbers) because they have only a single pair of factors, and the complexity of finding the factors increases as the size of the prime number used in the product increases. There is no known efficient factorization algorithm for finding factors when numbers are of a certain size. RSA uses prime factorization, presuming that it's really difficult to find the ...