# How does gcd in $\mathbb Z_p[x]$ and $\mathbb Z_q[x]$ relate to gcd in $\mathbb Z_n[x]$?

I'm trying to understand part of a paper. How does the difference of gcd in $$\mathbb Z_p[x]$$ and $$\mathbb Z_q[x]$$ relate to the gcd in $$\mathbb Z_n[x]$$? And why is the result of gcd in $$\mathbb Z_n[x]$$ a non-trivial non-invertible element?

For $$b(x), c(x)\in\mathbb Z_n[x]$$, let $$\gcd_p(b(x), c(x))$$ and $$\gcd_q (b(x), c(x))$$ be the greatest common divisor of the polynomials modulo $$p$$ and $$q$$, respectively. Where $$n = p\cdot q$$ and $$p$$ and $$q$$ are primes.

Proposition 1: Let $$b(x), c(x)\in\mathbb Z_n[x]$$. If $$\deg(\gcd_p(b(x), c(x))) \neq \deg(\gcd_q (b(x), c(x)))$$, then Euclid’s algorithm on $$\mathbb Z_n[x]$$ with input $$b(x)$$ and $$c(x)$$ yields a non-trivial non-invertible element of $$\mathbb Z_n$$.

D. Aggarwal and U. Maurer. Breaking RSA Generically Is Equivalent to Factoring. EUROCRYPT 2009. http://eprint.iacr.org/2008/260.pdf

• This might be better suited to crypto.stackexchange.com (please avoid cross-posting though).
– cody
Commented Apr 8 at 18:52

To explain their proposition, let me recall Euclid's algorithm to compute the gcd of $$b(x)$$ and $$c(x)$$:

while c(x) ≠ 0:
t(x) ← b(x) mod c(x)
b(x) ← c(x)
c(x) ← t(x)
return b(x)


To compute $$b(x) \bmod c(x)$$, you need to invert the leading coefficient of $$c(x)$$. And this element may be non-invertible (when computing in $$ℤ_n[x]$$), this is what the authors write (or hint more precisely).

If such a non-invertible leading coefficient does not appear during the algorithm run in $$ℤ_n[x]$$, Euclid's algorithm terminates without error. In this case, you can do the exact same computations $$\bmod p$$ and $$\bmod q$$: All the polynomials you manipulate have the same degree $$\bmod n$$, $$\bmod p$$ and $$\bmod q$$ (due to the leading coefficients being invertible, thus prime with $$n$$, that is not divisible by $$p$$ nor $$q$$), and the final results have the same degrees $$\bmod n$$, $$\bmod p$$ and $$\bmod q$$. By contrapositive, if the degrees are not the same, there must be some non-invertible leading coefficient at some point.

Finding such a non-invertible element means finding an element with a non-trivial gcd with $$n$$, whence a factor of $$n$$.

• Do you know why they pick h(x) to be monic polynomial? Commented Apr 8 at 21:44
• There are several reasons to do so, one being Lemma 3 on the probabilities of a random monic polynomial to be irreducible, or to have a linear factor. But most importantly I guess is the fact that taking $h$ monic over $ℤ_n$ makes it monic over $ℤ_p$ and $ℤ_q$. In "CASE 2" of their proof, I think that non-monic polynomials would be an issue for the isomorphism they use. The real requirement is probably for $h$ to have an invertible leading coefficient, so taking $h$ monic is a good solution. Also, it would not help in any manner to allow $h$ not to be monic. Commented Apr 10 at 8:06