Given the following
$N = p*q$
and the following 2 equations
$r1 = (a*p + b*q)^x \mod N$
$r2 = (c*p + d*q)^y \mod N$
$r1$, $r2$, $a$, $b$, $c$, $d$, $x$, $y$ and $N$ are all known. The only unknowns here are the 2 factors of $N$, i.e. $p$ & $q$
How do I go about solving these to find $p$ & $q$?
I am sitting on this for the past one day, but have no clue where to start. Does anyone have any hints on how to go about approaching these kinds of problems?
All the numbers involved here are really huge numbers.
UPDATE: From the comments, I have reached the next stage. If you do a binomial expansion, all terms except the first & last term involve (pq), so can they can be removed from the equation. So we end up with
$r1 = (a*p)^x + (b*q)^x \mod N$
$r2 = (c*p)^y + (d*q)^y \mod N$
How do I proceed from here?
(1) Suppose for the moment that $x=y$. Can you solve for $p^x,q^x$? From here, can you solve for $p,q$?
(2) Now reduce general $x,y$ to the $x=y$ case. Compute $r_1'=r_1^z\bmod N$ and $r_2'=r_2^w\bmod N$. The goal is to have $r_1'=(ap+bq)^{x'}\bmod N$ and $r_2'=(cp+dq)^{x'}\bmod N$, for some positive integer $x'$. What $z,w$ will accomplish this? Now apply the algorithm from (1) to $r_1',r_2'$ using $x'$.