RSA Factoring Challenge (part 4)

Looking back at my previous post, is it possible to solve these eight simultaneous equations given that a number n is the product of two prime numbers p and q each of four digits long? The first thing to notice is that equation (1) is equivalent to

$$X_{0}Y_{0} \equiv Z_{0} \;\mbox{(mod 10)}...(9)$$

which is as I discussed in part 1. So for a given Z₀ there are either two or three solutions for the pair (X₀,Y₀) (I shall ignore the fact that we can swap the values for X₀ and Y₀, as this just reflects the commutative property of the product, that is n=pq=qp).

So, it seems that we could make progress as follows. We take one of the pairs of solutions (X₀,Y₀) and we plug it back into equation (1) to find C₁, the multiple of 10 to be carried over into equation (2). That second equation then becomes equivalent to

$$X_{1}Y_{0}+X_{0}Y_{1} \equiv Z_{1}-C_{1}\;\mbox{(mod 10)}...(10)$$

and this equation is of the form

$$ax+by \equiv c\;\mbox{(mod 10)}...(11)$$

where a,b,c,x and y are elements of {0,1,2,...9} and a, b and c are known and x and y are not. Actually, as we saw in part 1 a and b in this case (being X₀ and Y₀) are not zero. This equation may or may not have solutions and I will consider this in future blogs. However, consider the case when (X₀,Y₀) is (3,7) (so Z₀ is 1 and C₁ is 2) and suppose Z₁ is 6 then we have the equation

$$7x+3y \equiv 4\;\mbox{(mod 10)}...(12)$$

By considering all 100 possibilities for x and y we find that there are exactly 10 possible solutions for the pair (x,y) and these are (0,8), (1,9), (2,0), (3,1), (4,2), (5,3), (6,4), (7,5), (8,6) and (9,7). Note that any one solution (x,y) can be obtained from another solution by adding multiples of (1,1) modulo 10.

So it follows that for our one choice of (X₀,Y₀) we can end up with 10 possibilities for (X₁,Y₁). Now we can again choose one of these solutions for (X₁,Y₁), substitute it into equation (2) and using our original values for (X₀,Y₀) and C₁ arrive at a value for C₂.

We can use these values in equation (3) which can be written as

$$X_{2}Y_{0}+X_{0}Y_{2} \equiv Z_{2}-X_{1}Y_{1}-C_{2}\;\mbox{(mod 10)}...(13)$$

and this is again of the form of equation (11). Not only that but the coefficients of x and y (a and b) are the same as before since a is Y₀ and b is X₀. This means that if we have already calculated a table of the hundred possibilities of ax+by modulo 10 then we can just pick out the solutions.

It is no surprise that we can continue in a similar vein until we reach equation (4). By then we have a set of possible solutions for (X₀,Y₀), (X₁,Y₁), (X₂,Y₂) and (X₃,Y₃), that is for the four digits of both p and q. However, only one of those solutions will satisfy the four remaining equations (5) to (8).