<p>To explain their proposition, let me recall Euclid's algorithm to compute the gcd of <span class="math-container">$b(x)$</span> and <span class="math-container">$c(x)$</span>:</p>
<pre><code>while c(x) ≠ 0:
     t(x) ← b(x) mod c(x)
     b(x) ← c(x)
     c(x) ← t(x)
return b(x)
</code></pre>
<p>To compute <span class="math-container">$b(x) \bmod c(x)$</span>, you need to invert the leading coefficient of <span class="math-container">$c(x)$</span>. And this element may be non-invertible (when computing in <span class="math-container">$ℤ_n[x]$</span>), this is what the authors write (or hint more precisely).</p>
<p>If such a non-invertible leading coefficient does not appear during the algorithm run in <span class="math-container">$ℤ_n[x]$</span>, Euclid's algorithm terminates without error. In this case, you can do the exact same computations <span class="math-container">$\bmod p$</span> and <span class="math-container">$\bmod q$</span>: All the polynomials you manipulate have the same degree <span class="math-container">$\bmod n$</span>, <span class="math-container">$\bmod p$</span> and <span class="math-container">$\bmod q$</span> (due to the leading coefficients being invertible, thus prime with <span class="math-container">$n$</span>, that is not divisible by <span class="math-container">$p$</span> nor <span class="math-container">$q$</span>), and the final results have the same degrees <span class="math-container">$\bmod n$</span>, <span class="math-container">$\bmod p$</span> and <span class="math-container">$\bmod q$</span>. By contrapositive, if the degrees are not the same, there must be some non-invertible leading coefficient at some point.</p>
<p>Finding such a non-invertible element means finding an element with a non-trivial gcd with <span class="math-container">$n$</span>, whence a factor of <span class="math-container">$n$</span>.</p>

CC BY-SA 4.0
2024-04-08T21:44:54.573Z
Do you know why they pick h(x) to be monic polynomial?
userg93
CC BY-SA 4.0
2024-04-10T08:06:39.603Z
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.
Bruno
CC BY-SA 4.0
2024-04-08T20:27:59.787Z
2024-04-08T20:27:59.787Z
Bruno
<p>I'm trying to understand part of a paper. How does the difference of gcd in <span class="math-container">$\mathbb Z_p[x]$</span>  and <span class="math-container">$\mathbb Z_q[x]$</span> relate to the gcd in <span class="math-container">$\mathbb Z_n[x]$</span>? And why is the result of gcd in <span class="math-container">$\mathbb Z_n[x]$</span> a non-trivial non-invertible element?</p>
<blockquote>
<p>For <span class="math-container">$b(x), c(x)\in\mathbb Z_n[x]$</span>, let <span class="math-container">$\gcd_p(b(x), c(x))$</span> and <span class="math-container">$\gcd_q (b(x), c(x))$</span> be the greatest common divisor of the polynomials modulo <span class="math-container">$p$</span> and <span class="math-container">$q$</span>, respectively. Where <span class="math-container">$n = p\cdot q$</span> and <span class="math-container">$p$</span> and <span class="math-container">$q$</span> are primes.</p>
</blockquote>
<blockquote>
<p>Proposition 1: Let <span class="math-container">$b(x), c(x)\in\mathbb Z_n[x]$</span>. If
<span class="math-container">$\deg(\gcd_p(b(x), c(x))) \neq \deg(\gcd_q (b(x), c(x)))$</span>, then
Euclid’s algorithm on <span class="math-container">$\mathbb Z_n[x]$</span> with input <span class="math-container">$b(x)$</span> and <span class="math-container">$c(x)$</span>
yields a non-trivial non-invertible element of <span class="math-container">$\mathbb Z_n$</span>.</p>
</blockquote>
<p>Link to paper:</p>
<blockquote>
<p>D. Aggarwal and U. Maurer. Breaking RSA Generically Is Equivalent to Factoring. EUROCRYPT 2009. <a href="http://eprint.iacr.org/2008/260.pdf" rel="nofollow noreferrer">http://eprint.iacr.org/2008/260.pdf</a></p>
</blockquote>

CC BY-SA 4.0
2024-04-08T18:52:32.100Z
This might be better suited to [crypto.stackexchange.com](https://crypto.stackexchange.com/) (please avoid cross-posting though).
cody
<cr.crypto-security><factoring>
How does gcd in $\mathbb Z_p[x]$ and $\mathbb Z_q[x]$ relate to gcd in $\mathbb Z_n[x]$?
userg93
# How does gcd in $\mathbb Z_p[x]$ and $\mathbb Z_q[x]$ relate to gcd in $\mathbb Z_n[x]$?

(Asked by: username_0 on 2024-04-07)

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>

**Tags:** cr.crypto-security, factoring

> **Comments:**
> **username_1**: This might be better suited to [crypto.stackexchange.com](https://crypto.stackexchange.com/) (please avoid cross-posting though).  

---

## 1 answers

### Answer by username_2 on 2024-04-08. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: Do you know why they pick h(x) to be monic polynomial?  
> **username_2**: 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.  

---

