RSA Factoring Challenge (part 3)

Suppose you had two prime numbers p and q, both m digits long, and these were, respectively, X_m-1X_m-2...X₁X₀ and Y_m-1Y_m-2...Y₁Y₀ (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 Z_2m-1Z_2m-2Z_2m-3...Z₁Z₀ (where the subscripted Z's represent the decimal digits of n). This means that Z_2m-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 X₃Y₀ and X₀Y₃ have a multiple of 10 which is the same for each term. Since Z_i (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 C_i for each equation so that we can accommodate the multiples of 10 accumulated in the previous equation. We also know that Z₇ may be zero in which case so might be C₇ (via equation 8).