Semiprimes

Between 1991 and 2007, RSA laboratories were awarding cash prizes to any individual who could factor any number from their published list of semiprimes known as RSA numbers.  The first cash prize of $1000 was given on April 1, 1991 to Arjen Lenstra for factoring RSA-100, a semiprime with 100 decimal digits (330 binary digits), and the largest cash prize of $20,000 was given on November 2, 2005 to Jens Franke for factoring RSA-640, a semiprime with 193 decimal digits (640 binary digits).  To date, the largest RSA number to be factored is RSA-220, a semiprime with 220 decimal digits (729 binary digits) on May 13, 2016, but unfortunately no cash prize was given since the challenge is now over.

A semiprime is the product of two prime numbers.  For example, 15 is a semiprime because it is the product of the two primes 3 and 5.  The RSA Challenge is to find the two prime factors when given just the semiprime.  There are several ways to do this, but all of them are time consuming for large numbers.

Factoring Methods

For example, let’s say you wanted to find the two prime factors of the semiprime 91.  One way would be to divide 91 by each prime number between 1 and the square root of 91 until you reach one that divides it evenly.  So in this case, 91 ÷ 2 = 45 r 1 (no), 91 ÷ 3 = 30 r 1 (no), 91 ÷ 5 = 18 r 1 (no), 91 ÷ 7 = 13 r 0 (yes!), so 91 = 7 x 13.  (This method can be made to go somewhat faster by using divisibility rules.)

Another way would be to subtract a perfect prime square and see if the difference is also divisible by that squared number.  This is because if you call the semiprime n and the two factors p and p + d, n = p(p + d) or n = p² + pd or n – p² = pd.  So to factor 91, (91 – 2²) ÷ 2 = 43 r 1 (no), (91 – 3²) ÷ 3 = 27 r 1 (no), (91 – 5²) ÷ 5 = 13 r 1 (no), (91 – 7²) ÷ 7 = 6 r 0 (yes!), so 91 is divisible by 7.

One more way to factor a semiprime would be to add a perfect square and see if the sum is also a perfect square (assuming the semiprime is odd).  This is because if you call the semiprime n and the two factors p and q, and let u = ½(p + q) and v = ½(q – p), then u – v = ½(p + q) – ½(q – p) = ½p + ½q – ½q + ½p = p and u + v = ½(p + q) + ½(q – p) = ½p + ½q + ½q – ½p = q, which means n = pq = (u – v)(u + v) = u² – v², or n + v² = u².  So to factor 91, 91 + 1² = 92 (not a square), 91 + 2² = 95 (not a square), 91 + 3² = 100 = 10² (a square!), so the two factors of 91 are 10 – 3 and 10 + 3, or 7 and 13.  (This method can be made to go somewhat faster by filtering out sums whose last digit cannot possibly be a square number, which include 2, 3, 7, and 8.)

Computer Encryptions

As mentioned earlier, all the methods for factoring a large semiprime are time consuming, even for a computer, because they all use some variation of brute force or trial and error.  Computer programs rely on this fact with public and private key encryptions.  In a computer encryption, each user is given a public key (a large semiprime typically 1024 or 2048 binary digits long) that is publicly available for others to use to encode a message.  The message can then be decoded only by the private key (the two factors of the semiprime) that is known only by the receiver.  The RSA Challenge (hopefully) proved that this method of encryption is safe, because even after over 25 years nobody come even close to factoring RSA-1024.

Unfortunately, just like World War 2 Germany, public and private key computer encryptions are fighting a two-front war.  On the one front is mathematics – someone in the future may be clever enough to think of a more efficient way to factor large semiprimes.  On the other front is technology – someone in the future may develop a computer fast enough to use a brute force method to be able to factor large semiprimes.

Either way, the first person who can successfully factor large semiprimes, whether it is by a mathematical or technological breakthrough, would have the power to hack into anybody’s computer and steal their identity, including their bank account and credit card information, which presents an interesting hypothetical dilemma.  If this were to happen, will he or she use it for good or for evil? If for good, will he or she give large companies sufficient warning to find a new computer encryption method?  In the time in between, will he or she be kidnapped by the bad guys and forced to hack into computers for them?  Sounds like a Hollywood movie in the making!

At any rate, like all two-front wars it will only be a matter of time before the middle man will be defeated.  At some point, public and private key computer encryptions will become obsolete. Already on the technology front quantum computer processors are being developed where if they work they could factor large semiprimes almost instantaneously.  It’s time for a new encryption method!