RSA Laboratories

2.3.3 What is the factoring problem?

Factoring is the act of splitting an integer into a set of smaller integers (factors) which, when multiplied together, form the original integer. For example, the factors of 15 are 3 and 5; the factoring problem is to find 3 and 5 when given 15. Prime factorization requires splitting an integer into factors that are prime numbers; every integer has a unique prime factorization. Multiplying two prime integers together is easy, but as far as we know, factoring the product of two (or more) prime numbers is much more difficult.

Factoring is the underlying, presumably hard problem upon which several public-key cryptosystems are based, including the RSA algorithm. Factoring an RSA modulus (see Question 3.1.1) would allow an attacker to figure out the private key; thus, anyone who can factor the modulus can decrypt messages and forge signatures. The security of the RSA algorithm depends on the factoring problem being difficult and the presence of no other types of attack. There has been some recent evidence that breaking the RSA cryptosystem is not equivalent to factoring [BV98]. It has not been proven that factoring must be difficult, and there remains a possibility that a quick and easy factoring method might be discovered (see Question 2.3.5), though factoring researchers consider this possibility remote.

It is not necessarily true that a large number is more difficult to factor than a smaller number. For example, the number 101000is easy to factor, while the 155-digit number RSA-155 (see Question 2.3.6) was factored after seven months of extensive computations. What is true in general is that a number with large prime factors is more difficult to factor than a number with small prime factors (still, the running time of some factoring algorithms depends on the size of the number only and not on the size of its prime factors). This is why the size of the modulus in the RSA algorithm determines how secure an actual use of the RSA cryptosystem is. Namely, an RSA modulus is the product of two large primes; with a larger modulus, the primes become larger and hence an attacker needs more time to factor it. Yet, remember that a number with large prime factors might possess certain properties making it easy to factor. For example, this is the case if the prime factors are very close to each other (see Question 3.1.5).

Top of the page