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.
 A: 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{eq1A}$$
$$B \equiv (zp+uq)^{e_2} \pmod n \tag{2}\label{eq2A}$$
Let $e = \text{lcm}(e_1,e_2)$. Take both sides of \eqref{eq1A} to the power of $f = \frac{e}{e_1}$ and both sides of \eqref{eq2A} to the power of $g = \frac{e}{e_2}$ to get
$$A^f \equiv (xp+yq)^e \pmod n \tag{3}\label{eq3A}$$
$$B^{\, g} \equiv (zp+uq)^e \pmod n \tag{4}\label{eq4A}$$
As Roddy MacPhee stated in the comments, in the binomial expansions of the RHS of \eqref{eq3A} and \eqref{eq4A}, 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. We then end up with
$$A^f \equiv x^e p^e + y^e q^e \pmod n \tag{5}\label{eq5A}$$
$$B^{\, g} \equiv z^e p^e + u^e q^e \pmod n \tag{6}\label{eq6A}$$
We now basically have $2$ linear equations in $2$ unknowns of $p^e$ and $q^e$. To solve them, multiply both sides of \eqref{eq5A} by $u^e$ and subtract \eqref{eq6A} 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{eq7A}$$
Since $n = pq$, this means the LHS of \eqref{eq7A} 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 we can use the Euclidean algorithm to relatively efficiently get $p = \gcd(n,u^e A^f - y^e B^{\, g})$, and then $q = \frac{n}{p}$. 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), we 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$, we can use the Euclidean algorithm to get $q = \gcd(n,C)$, and then $p = \frac{n}{q}$. However, if it is, then we can eliminate $p^e$ from \eqref{eq5A} and \eqref{eq6A} to use those other values instead. If they also fail in this respect, I don't offhand know what's 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 a few 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$.
