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 Z0 there are either two or three solutions for the pair (X0,Y0) (I shall ignore the fact that we can swap the values for X0 and Y0, 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 (X0,Y0) and we plug it back into equation (1) to find C1, 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 X0 and Y0) are not zero. This equation may or may not have solutions and I will consider this in future blogs. However, consider the case when (X0,Y0) is (3,7) (so Z0 is 1 and C1 is 2) and suppose Z1 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 (X0,Y0) we can end up with 10 possibilities for (X1,Y1). Now we can again choose one of these solutions for (X1,Y1), substitute it into equation (2) and using our original values for (X0,Y0) and C1 arrive at a value for C2.
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 Y0 and b is X0. 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 (X0,Y0), (X1,Y1), (X2,Y2) and (X3,Y3), 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).
Thursday, 16 April 2015
Saturday, 4 April 2015
RSA Factoring Challenge (part 3)
Suppose you had two prime numbers p and q, both m digits long, and these were, respectively, Xm-1Xm-2...X1X0 and Ym-1Ym-2...Y1Y0 (where the subscripted X and Y's represent the decimal digits of p and q) then the product of p and q can be written as the product of
$$(X_{m-1} \times 10^{m-1} + X_{m-2} \times 10^{m-2} + ... + X_{1} \times 10 + X_{0}) \times (Y_{m-1} \times 10^{m-1} + Y_{m-2} \times 10^{m-2} + ... + Y_{1} \times 10 + Y_{0})$$
Ignoring the powers of 10 for the moment, the terms in the above can be written as a matrix of products of digits in p and q. For example for m=4, we get
$$\begin{pmatrix} X_{0}Y_{0} & X_{0}Y_{1} & X_{0}Y_{2} & X_{0}Y_{3} \\
X_{1}Y_{0} & X_{1}Y_{1} & X_{1}Y_{2} & X_{1}Y_{3} \\
X_{2}Y_{0} & X_{2}Y_{1} & X_{2}Y_{2} & X_{2}Y_{3} \\
X_{3}Y_{0} & X_{3}Y_{1} & X_{3}Y_{2} & X_{3}Y_{3}
\end{pmatrix}$$
Suppose that the result of the product was n then, as we have seen in my previous post, we can say that n is either 2m or 2m-1 digits long and we can write n as Z2m-1Z2m-2Z2m-3...Z1Z0 (where the subscripted Z's represent the decimal digits of n). This means that Z2m-1 may be zero. We can now relate the products of the digits in p and q to the digits in n by noticing that the terms along any diagonal line in the above matrix parallel to the one that passes through X3Y0 and X0Y3 have a multiple of 10 which is the same for each term. Since Zi (i running from 0 to 2m-1) involves the sum of these terms modulo 10 we can write a set of simultaneous equations, which for m=4 are:-
$$X_{0}Y_{0}-10C_{1}=Z_{0}...(1)$$
$$X_{1}Y_{0}+X_{0}Y_{1}+C_{1}-10C_{2}=Z_{1}...(2)$$
$$X_{2}Y_{0}+X_{1}Y_{1}+X_{0}Y_{2}+C_{2}-10C_{3}=Z_{2}...(3)$$
$$X_{3}Y_{0}+X_{2}Y_{1}+X_{1}Y_{2}+X_{0}Y_{3}+C_{3}-10C_{4}=Z_{3}...(4)$$
$$X_{3}Y_{1}+X_{2}Y_{2}+X_{1}Y_{3}+C_{4}-10C_{5}=Z_{4}...(5)$$
$$X_{3}Y_{2}+X_{2}Y_{3}+C_{5}-10C_{6}=Z_{5}...(6)$$
$$X_{3}Y_{3}+C_{6}-10C_{7}=Z_{6}...(7)$$
$$C_{7}=Z_{7}...(8)$$
Note that we have to include a carry term Ci for each equation so that we can accommodate the multiples of 10 accumulated in the previous equation. We also know that Z7 may be zero in which case so might be C7 (via equation 8).
$$(X_{m-1} \times 10^{m-1} + X_{m-2} \times 10^{m-2} + ... + X_{1} \times 10 + X_{0}) \times (Y_{m-1} \times 10^{m-1} + Y_{m-2} \times 10^{m-2} + ... + Y_{1} \times 10 + Y_{0})$$
Ignoring the powers of 10 for the moment, the terms in the above can be written as a matrix of products of digits in p and q. For example for m=4, we get
$$\begin{pmatrix} X_{0}Y_{0} & X_{0}Y_{1} & X_{0}Y_{2} & X_{0}Y_{3} \\
X_{1}Y_{0} & X_{1}Y_{1} & X_{1}Y_{2} & X_{1}Y_{3} \\
X_{2}Y_{0} & X_{2}Y_{1} & X_{2}Y_{2} & X_{2}Y_{3} \\
X_{3}Y_{0} & X_{3}Y_{1} & X_{3}Y_{2} & X_{3}Y_{3}
\end{pmatrix}$$
Suppose that the result of the product was n then, as we have seen in my previous post, we can say that n is either 2m or 2m-1 digits long and we can write n as Z2m-1Z2m-2Z2m-3...Z1Z0 (where the subscripted Z's represent the decimal digits of n). This means that Z2m-1 may be zero. We can now relate the products of the digits in p and q to the digits in n by noticing that the terms along any diagonal line in the above matrix parallel to the one that passes through X3Y0 and X0Y3 have a multiple of 10 which is the same for each term. Since Zi (i running from 0 to 2m-1) involves the sum of these terms modulo 10 we can write a set of simultaneous equations, which for m=4 are:-
$$X_{0}Y_{0}-10C_{1}=Z_{0}...(1)$$
$$X_{1}Y_{0}+X_{0}Y_{1}+C_{1}-10C_{2}=Z_{1}...(2)$$
$$X_{2}Y_{0}+X_{1}Y_{1}+X_{0}Y_{2}+C_{2}-10C_{3}=Z_{2}...(3)$$
$$X_{3}Y_{0}+X_{2}Y_{1}+X_{1}Y_{2}+X_{0}Y_{3}+C_{3}-10C_{4}=Z_{3}...(4)$$
$$X_{3}Y_{1}+X_{2}Y_{2}+X_{1}Y_{3}+C_{4}-10C_{5}=Z_{4}...(5)$$
$$X_{3}Y_{2}+X_{2}Y_{3}+C_{5}-10C_{6}=Z_{5}...(6)$$
$$X_{3}Y_{3}+C_{6}-10C_{7}=Z_{6}...(7)$$
$$C_{7}=Z_{7}...(8)$$
Note that we have to include a carry term Ci for each equation so that we can accommodate the multiples of 10 accumulated in the previous equation. We also know that Z7 may be zero in which case so might be C7 (via equation 8).
Subscribe to:
Posts (Atom)