Given $m,n,e,c_1,c_2,\alpha,\beta \in \mathbb{N}$ and the system of congruences: $$ \begin{align} m^e \equiv c_1 &\pmod n &(1)\\ (\alpha m+\beta)^e \equiv c_2 &\pmod n &(2) \end{align} $$
One can solve for $m$ algebraically in terms of $\alpha$, $\beta$, $c_1$, and $c_2$. When $e=3$, one gets: $$\frac{\beta(c_2+2\alpha^3c_1-\beta^3)}{\alpha(c_2-\alpha^3c_1+2\beta^3)} = \frac{mP(m)}{P(m)} = \frac{Q(m)}{P(m)} = m\pmod n$$
with $Q(m) = \beta(c_2+2\alpha^3c_1-\beta^3)$ and $P(m) = \alpha(c_2-\alpha^3c_1+2\beta^3)$.
This comes up, for example, in the context of the Franklin-Reiter related message attack on RSA where $n$, $e$, $\alpha$, $\beta$, $c_1$, $c_2$ are known and $m$ is the secret an adversary wishes to recover.
Coppersmith et al.[1] provide $P(m)$ and $Q(m)$ above but warn expressing $m$ as a ratio of polynomials gets complicated fairly quickly as the exponent $e$ in (1) and (2) increases.
The authors also provide a less convoluted method for retrieving $m$ given the above system of congruences that relies on $\gcd(x^e-c_1, (\alpha x+\beta)^e-c_2) \in \mathbb{Z}/n\mathbb{Z}[x]$ almost always yielding the linear polynomial $x-m$ when conditions imposed by RSA are met.
This simpler method notwithstanding, how does one construct polynomials $P(m)$ and $Q(m)$ used in the first method?
Thanks!
[1] Coppersmith, D., Franklin, M., Patarin, J., and M. Reiter. 1996. Low-exponent RSA with related messages. Advances in Cryptology–EUROCRYPT '96:1–9.