RSA Factoring Challenge (part 5)

I want to consider the solutions of equation (11) specifically for the values of a and b that we are likely to encounter. From the discussion in that blog entry we can see that in each of the equations (2) to (4) coefficient a takes the values of Y₀ and coefficient b takes the values of X₀. This means that in these cases a and b are elements of {1,3,7,9} and all the numbers in this set are coprime to 10.

Now suppose the RHS of equation (11) takes the value 5 then there are ten ways in which this number may be obtained on the LHS of the equation. We can have, modulo 10, 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 6+9, 7+8, 8+7 and 9+6. So if the RHS takes the value c then the 10 possibilities for the LHS are i+(c-i) where i runs through 0 to 9. Note that if c-i<0 then c-i is congruent to 10+c-i modulo 10.

So in essence our solutions for x and y boil down to two equations:-

$$ax \equiv i \;\mbox{(mod 10)}...(14)$$

and

$$by \equiv c-i \;\mbox{(mod 10)}...(15)$$

where i runs through 0 to 9. As a and b are coprime to 10, then a and b have an inverse a^-1 and b^-1 such that

$$aa^{-1} \equiv 1 \;\mbox{(mod 10)}...(16)$$

and

$$bb^{-1} \equiv 1 \;\mbox{(mod 10)}...(17)$$

Hence our solutions for x and y are

$$x \equiv a^{-1}i \;\mbox{(mod 10)}...(18)$$

and

$$y \equiv b^{-1}(c-i) \;\mbox{(mod 10)}...(19)$$

Previously, in equation (12) we considered the situation where a was 7, b was 3 and c was 4. Now the inverse of 7 modulo 10 is 3 (and vice versa since 3x7=21 which is congruent to 1 modulo 10) and so the 10 pairs of solutions are (3i,7(4-i)) modulo 10 where i runs from 0 to 9. This is congruent to (3i,8-7i) modulo 10. So we obtain the pairs (0,8), (3,1), (6,4), (9,7), (2,0), (5,3), (8,6), (1,9), (4,2) and (7,5) as before.