Wednesday 25 March 2015

RSA Factoring Challenge (part 1)

In a diversion away from my continuing study of number theory, I have been thinking about the difficulty of factoring large integers. My attention was caught by the RSA Factoring Challenge which was set up by the RSA Laboratories to "learn about the actual difficulty of factoring large numbers of the type used in RSA keys." I have described RSA encryption in my other concurrent blog and the keys are used in the modulus of the encryption and decryption. The RSA challenge was terminated in 2007 and the monetary prizes that were offered were withdrawn, however, not all of the numbers were factored. So what were these numbers?

Wikipedia has a list of the RSA numbers and reports on the success of people factoring them. These numbers are semiprimes, that is they are a product of two primes (not necessarily distinct). One thing that I noticed as I was looking down the list of factorisations was that in most cases the two primes had the same number of decimal digits and this got me thinking about this specific problem. If you knew that a number was the product of two primes of the same length (in decimal digits) could you use the knowledge of the product to determine what the factors were?

My first thought was that you could probably have a guess at what the last digit of each prime was. If the last digit of the product n=pq was Z and the last digits of the two primes p and q were X and Y, then

$$XY \equiv Z \;\mbox{(mod 10)}$$

This is true because the products of all the other digits involve multiples of 10 and these products are congruent to zero modulo 10 and therefore can't contribute to the remainder here. This result is also true regardless of the number of digits in p and q. Now because prime numbers larger than 5 can only end in 1, 3, 7 or 9, then if Z was 1 then (X,Y) are either (1,1), (3,7) or (9,9) (or vice versa for X and Y). The other pairings for (X,Y) are (1,3) and (7,9) for Z=3, (1,7) and (3,9) for Z=7 and (1,9), (3,3) and (7,7) for Z=9 (or vice versa).

So, for example, for RSA-220 which is the 220 decimal digit number

2260138526203405784941654048610197513508038915719776718321197768109445641817
9666766085931213065825772506315628866769704480700018111497118630021124879281
99487482066070131066586646083327982803560379205391980139946496955261

we can say that the last digits of the two primes that divide it could be (1,1), (3,7) or (9,9).

No comments:

Post a Comment