RSA Factoring Challenge (part 2)

In my previous blog I asked the question "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?" In what follows I will assume that for a number n we want to find the m-digit primes p and q such that n=pq.

So a question that you could ask is how many digits does n have if p and q have m digits? Primes p or q can't exceed 10^m-1 as 10^m is an m+1 digit number and

$$(10^{m}-1)^{2}=10^{2m}-2 \times 10^{m}+1$$

For m>1 this is the number 999...800...1 which is 2m digits long. The m+1 digit from the right is an 8 and all the digits to the left of the 8 are 9's (there are m-1 of them) and all the digits to the right are 0's except the last which is a 1.

Primes p and q cannot be less than 10^m-1 as one less than this is an m-1 digit number and

$$(10^{m-1})^{2}=10^{2m-2}$$

which is a 2m-1 digit number. It follows then that if p and q have m digits, then n will have between 2m-1 and 2m digits. It also follows that if n has k digits, then p and q will have k/2 digits if k is even and (k+1)/2 digits if k is odd.

So, if RSA-220 was the product of two prime factors containing the same number of decimal digits, then we would be looking for primes that are 110 digits long.

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).