0

What is the biggest hurdle with finding the prime factors for RSA encryption?

If 3 doesn't factor, wouldn't that leave 33.3% left, then 20 then 14 as you move along the known more simple primes?

and of those, you would only be interested in primes, not just even or odd numbers correct?

Derek James
  • 31
  • 4
  • Intuitively, it may seem like discarding all multiples of 3 reduces the number of possible prime factors by $1/3$. However, don't forget that there are infinitely many primes and that they are distributed randomly. This is the major obstacle. – tylerc0816 Nov 19 '13 at 13:09

1 Answers1

2

The biggest problem is that there are only two prime factors of each RSA modulus, and that primes are fairly abundant in any given interval (http://en.wikipedia.org/wiki/Prime_number_theorem). Sure, you are only interested in odd primes, and can eliminate many options once you've deduced 3 doesn't factor. But think about this: a 1024-bit RSA number $n$ will have prime factors somewhere between 0 and $\sqrt(n)$. However, by the prime number theorem, this interval will contain approximately $1\times 10^{171}$ primes. Furthermore you don't a priori know which of those numbers are prime! Hence you have to check each number in the interval to see if it is prime, and then check to see if it factors $n$. Hence you wind up with an algorithm that is $\mathcal{O}(\sqrt{n})$, where $n$ is unfeasibly large.

Now, there are ways to speed up both parts of the above process by using number fields (the number field sieve), but even this very sophisticated algorithm is impractically slow for most RSA moduli.

Ben Perez
  • 505
  • 2
  • 10
  • Why would you need to check if the number is prime before determining if its a factor?

    I would assume you only need to find a factor.

    Every time you determine which odd number doesn't work that gets you much closer to the number.

    Are there limitations to the "division" algorithm?

     – Derek James Nov 19 '13 at 18:25
  • Ah, sorry, you don't need to check that the number is prime until you know that it divides $n$ (since an integer may have non-prime factors). But even so, running the division algorithm on every integer between 0 and $\sqrt{n}$, where $n$ is a 1024-bit number would take you an inconceivable amount of time. You have to realize that even if you cut out all the even numbers in that list, you still are checking a massive list. – Ben Perez Nov 19 '13 at 19:22
  • Ok, one more tid bit of info... although we would only be checking odd numbers that would also cut the number of possibilities in half correct?

    With the fastest machines and distributed computing, is this still a multi year running algorithm to find the factors?

     – Derek James Nov 19 '13 at 22:50
  • Yes, only checking odd numbers cuts the search space in half, but this isn't enough to make the algorithm fast enough for practical purposes. Even with the best supercomputers available and algorithms far more sophisticated than the just guessing every odd integer, you'd still be waiting at least a year to factor an RSA number. – Ben Perez Nov 19 '13 at 23:02
  • Ok, makes sense, but counting is fairly quick with computers. Is the bottle neck in the process a) "the algorithm to determine if it's divisible" or b) shear size of the possibilities? – Derek James Nov 20 '13 at 00:14
  • Well the division algorithm will slow exponentially as the size of your number increases. But really its just the shear size of possibilities. – Ben Perez Nov 20 '13 at 13:09