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.