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$.

Link to paper:

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

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

1 Answer 1


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$.

  • $\begingroup$ Do you know why they pick h(x) to be monic polynomial? $\endgroup$
    – userg93
    Commented Apr 8 at 21:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bruno
    Commented Apr 10 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.