Factorization « Integer Overflow

Factorization

The factorization problem is both old and difficult. It’s statement is simple: for a number $n$ , find distinct primes $p_1,p_2,...,p_k$ and positive integers $m_1,m_2,...,m_k$ such that

$n = p_1^{m_1}\cdot p_2^{m_2} \cdot \cdots \cdot p_k^{m_k}$

There is an obvious technique we can use to solve this problem: trial division. It’s simple enough: to factor $n$ , find a number $q < \sqrt{n}$ that divides $n$ . If we write $n = q\cdot r$ , we see that the problem of factoring $n$ reduces to the problem of factoring $q$ and $r$ . If we iterate this process far enough, we’ll eventually be at a point where these factorizations are easy to perform.

Unfortunately, there is a serious problem with trial division. If $n$ is a $d$ -digit number (say, base 10), then in the worst-case we might need to try $10^{d/2}$ numbers before we find our $q$ ! For this reason, we say that trial division is an exponential-time algorithm. If $d$ is large, this process simply requires too many steps to be practical.

In the articles to follow, we will talk about more manageable techniques for factoring “large” numbers (I put “large” in quotes because, even with these more advanced techniques, there are still some practical limitations — although they are not nearly as restrictive as trial division!) Each of the techniques we will look are are heuristics, which means they will work “most of the time.” In each of these articles, we will hopefully get a sense of why these techniques work.

Since efficient factorization is really only interesting when it is applied to a problem, I thought it would be fun to make up a scenario for us to use it in. So for this reason, our first article will be on the RSA cryptosystem; the remainder of the articles will focus on attacking the examples from the RSA article.