Factoring and Semiprimes

A semiprime (or near prime, pq number, etc.) is a number that only has two prime factors (not necessarily different primes). It is easy for a computer to quickly compute the value of a semiprime if given two prime numbers. For instance, the prime numbers 23 and 73 were used to send the Arecibo message decades ago into space. In the faint chance that an intelligent being intercepts this message, they will be able to arrange the message on a two-dimensional grid. Being a semiprime, the number 1679 only has two factors -- 23 and 73.

Factoring is a computationally difficult endeavor, however. In fact, the difficulty of factoring very large primes sits at the heart of the most secure encryption methods (including RSA especially). If one could find a fast way to factor large semiprimes, he or she would effectively have a way to quickly decrypt an encrypted message.

Here's an example of a large semiprime (yet still small by RSA 512 bit standards): 31,883,349,249,899,479. I know the two primes that make up that number -- but can you find them quickly? We know that at least one of the primes that make up this number has to be equal to or less than the square root of that number. The square root of 31,883,349,249,899,479 is 178,559,091.76 (rounded). One could write a program to check all primes below this number to find the one that divides into the original number. This would give the two primes that make up this semiprime number.

"That isn't so bad! I could write a program to figure it out in a few minutes and it probably wouldn't take but a few seconds to a minute to find the answer!"

Ok ... then try to crack this semiprime that stands between you and cracking MIT's 1999 challenge (which they believe will take more than 30 years to figure out).

n = 631446608307288889379935712613129233236329881833084137558899
077270195712892488554730844605575320651361834662884894808866
350036848039658817136198766052189726781016228055747539383830
826175971321892666861177695452639157012069093997368008972127
446466642331918780683055206795125307008202024124623398241073
775370512734449416950118097524189066796385875485631980550727
370990439711973361466670154390536015254337398252457931357531
765364633198906465140213398526580034199190398219284471021246
488745938885358207031808428902320971090703239693491996277899
532332018406452247646396635593736700936921275809208629319872
7008292431243681

This is the LCS35 MIT Challenge. That's a 2,048 bit modulus. Hell would freeze over well before all the computers in the world could come close to finding the factors of that number by brute force alone. However, there may yet be an undiscovered efficient algorithm that can factor in polynomial time. If such a method were possible, it might be possible to factor this semiprime within the span of years, months or perhaps even days. (That's saying a lot)