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