Modular arithmetic equation system

Assume I have the following modular congruences, where $n = pq$ is the product of two (large) primes:

$$A \equiv (xp+yq)^{e_1} \mod n$$

$$B \equiv (zp+uq)^{e_2} \mod n$$

We know $A,B, x,y,z,u, e_1, e_2$ and $n$, but not its prime factors $p$ and $q$.

I have some vague recollections from one of my classes that using this system of congruences, given the properties of modular exponentiation, I can find $p$ and $q$. I am not necessarily looking for a plain solution but for an explanation why.

My first instinct was to solve the following system:

$$k_1n + A = (xp+yq)^{e_1}$$

$$k_2n + B = (zp+uq)^{e_2}$$

$$n = pq$$

But that has 4 unknowns so I'd need 4 equations.

Answer

The following may be what you are thinking of from your class. You have the following $2$ congruence equations:

$$A \equiv (xp+yq)^{e_1} \pmod n \tag{1}\label{eq1}$$
$$B \equiv (zp+uq)^{e_2} \pmod n \tag{2}\label{eq2}$$

Let $e = \text{lcm}(e_1,e_2)$. Take both sides of $\eqref{eq1}$ to the power of $f = \frac{e}{e_1}$ and both sides of $\eqref{eq2}$ to the power of $g = \frac{e}{e_2}$ to get

$$A^f \equiv (xp+yq)^e \pmod n \tag{3}\label{eq3}$$
$$B^{\, g} \equiv (zp+uq)^e \pmod n \tag{4}\label{eq4}$$

As Roddy MacPhee stated in the comments, in the binomial expansion of the RHS of $\eqref{eq3}$ and $\eqref{eq4}$, each term except for the first & last ones have a factor of $pq$, so are congruent to $0$ modulo $n$ and, thus, can be ignored. You then end up with

$$A^f \equiv x^e p^e + y^e q^e \pmod n \tag{5}\label{eq5}$$
$$B^{\, g} \equiv z^e p^e + u^e q^e \pmod n \tag{6}\label{eq6}$$

You now basically have $2$ linear equations in $2$ unknowns of $p^e$ and $q^e$. To solve them, you can multiply and subtract to eliminate one of the variables. Multiply both sides of $\eqref{eq5}$ by $u^e$ and subtract $\eqref{eq6}$ multiplied by $y^e$ to get

$$u^e A^f - y^e B^{\, g} \equiv \left(\left(ux\right)^e - \left(zy\right)^e\right)p^e \pmod n \tag{7}\label{eq7}$$

Since $n = pq$, this means the LHS of $\eqref{eq7}$ must be a multiple of $p$. There are $2$ basic cases to consider now. If the LHS is not congruent to $0$ modulo $n$, then you can use the Euclidean algorithm to efficiently get $p = \gcd(n,u^e A^f - y^e B^{\, g})$, and then $q$ from $n$. However, if the LHS is congruent to $0$ modulo $n$, then if $p \neq q$ (note: if there is any chance of this not being true, you should check for & handle this initially), you have instead that $C = \left(ux\right)^e - \left(zy\right)^e \equiv 0 \pmod q$, so there are now $2$ sub-cases to handle. If $C$ is not congruent to $0$ modulo $n$, you can use the Euclidean algorithm to get $q = \gcd(n,C)$, and then $p$ from $n$. However, if it is, then you can eliminate $p^e$ from $\eqref{eq5}$ and $\eqref{eq6}$ to use those other values instead. If they also fail in this respect, I don't know offhand what is best to do next, but I doubt this will happen very often, if at all, especially since $p$ and $q$ are both large primes.

One thing to note is there are relatively fast and efficient means to get the modulo results of $j^k \pmod m$ for even quite large values of $j, k$ and $m$. For example, Congruence Modulo with large exponents has some ideas, with my suggestion being to consider a binary method, like repeated squaring and reduction, as outlined in the answer by André Nicolas, or repeated squaring & multiplication of the values corresponding to the $1$ coefficients in the binary representation of $k$.