RSA Factoring Challenge (part 6)

I want to consider an example to show how we can attempt to find a solution to the eight simultaneous equations (1) to (8). I will start with an example where we know the two four digit primes p and q and then attempt to recover p and q from their product n using equations (1) to (8).

Let p be 2029 and q be 4919 then their product n is 9980651. If we didn't know what p and q were then following our analysis in part (1) then (X₀,Y₀) are either (1,1), (3,7) or (9,9). Let's suppose we try the middle pair first. Plugging (X₀,Y₀)=(3,7) back into equation (1) we find that C₁=2. Equation (2) then becomes equivalent to

$$7X_{1}+3Y_{1} \equiv 3\;\mbox{(mod 10)}$$

From what we discussed in part 5 our possible solutions for (X₁,Y₁) are (3i,7(3-i)) modulo 10 (where i runs from 0 to 9) and these are the pairs (0,1), (3,4), (6,7), (9,0), (2,3), (5,6), (8,9), (1,2), (4,5) and (7,8).

Let's take the pair (X₁,Y₁)=(2,3). Substituting the values (X₀,Y₀)=(3,7), (X₁,Y₁)=(2,3) and C₁=2 into equation (2) we find that C₂=2. Equation (3) then becomes equivalent to

$$7X_{2}+3Y_{2} \equiv 8\;\mbox{(mod 10)}$$

and our possible solutions for (X₂,Y₂) are (3i,7(8-i)) modulo 10 and these are the pairs (0,6), (3,9), (6,2), (9,5), (2,8), (5,1), (8,4), (1,7), (4,0) and (7,3).

Let's take the pair (X₂,Y₂)=(2,8). Substituting the values (X₀,Y₀)=(3,7), (X₁,Y₁)=(2,3),  (X₂,Y₂)=(2,8) and C₂=2 into equation (3) we find that C₃=4. Equation (4) then becomes equivalent to

$$7X_{3}+3Y_{3} \equiv 4\;\mbox{(mod 10)}$$

and our possible solutions for (X₃,Y₃) are (3i,7(4-i)) modulo 10 and these are the pairs (0,8), (3,1), (6,4), (9,7), (2,0), (5,3), (8,6), (1,9), (4,2) and (7,5).

So what are these solutions for p and q? They are the following ten pairs of numbers; (223,8837), (3223,1837), (6223,4837), (9223,7837), (2223,837), (5223,3837), (8223,6837), (1223,9837), (4223,2837) and (7223,5837). Rather than showing that these numbers fail to satisfy equations (5) to (8) we can just multiply them together and compare them to n which is 9 980 651. We find that 223x8837=1 970 651, 3223x1837=5 920 651, 6223x4837=30 100 651, 9223x7837=72 280 651, 2223x837=1 860 651, 5223x3837=20 040 651, 8223x6837=56 220 651, 1223x9837=12 030 651, 4223x2837=11 980 651 and 7223x5837=42 160 651.

As expected none of them equal n. What it does demonstrate is that the method works, since each of the ten products ends in the number 0651, the same as the last four digits of n. This is to be expected as this was what was demanded by satisfying equations (1) to (4).