Polynomial GCD — the Euclidean algorithm on polynomials, and the trick that recovers a shared root

The GCD of two polynomials over a ring/field, computed by the same repeated-remainder Euclidean algorithm as integers, pinpoints roots the two polynomials *share* — which is the whole reason it shows up in crypto: build two polynomials that both vanish at your unknown secret, and their GCD hands you a low-degree polynomial (ideally linear) with that secret as its root.

The signal that gives it away

- Two equations, same unknown, no way to solve either alone — but you can write both as polynomials in one variable that share exactly one root (the value you want). That's the shape polynomial GCD wants. - Concretely in RSA: two ciphertexts c1, c2 under the same modulus `n` and same (small) exponent `e`, encrypting two messages m1, m2 that satisfy a known relation m2 = f(m1) — e.g. m2 = m1 + r for a known offset r, or the general affine m2 = a·m1 + b. This is the Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD setup. Both x^e - c1 and f(x)^e - c2 vanish at x = m1, so x - m1 divides their GCD. - Also shows up as a cleanup step: after Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction or a lattice attack produces a candidate polynomial whose roots include noise, taking a GCD against a second, independently-built polynomial with the same target root strips the noise and isolates the real root. - Root-finding for Discrete Logarithm — the factorization of the group order picks your algorithm-adjacent problems and curve-equation work over Finite Field Arithmetic — the GF(p^k) substrate under AES, LFSRs, and extension-field curves/DLP also reduce to this when you already have two polynomials known to share a root. - e must stay small — the polynomials have degree e, and both the arithmetic and the GCD cost grow with it. This is textbook-RSA territory in the same sense as RSA Fundamentals — the routing hub: which artifact points to which attack's small-e branch: it's the shape, not the size of n, that matters.

How to exploit it

1. Build both polynomials in the same ring, Zmod(n)[x] (Sage), not over the integers: ``python R.<x> = PolynomialRing(Zmod(n)) g1 = x^e - c1 g2 = (a*x + b)^e - c2 # known relation m2 = a*m1 + b ` 2. Compute the GCD with the ordinary Euclidean algorithm (repeated remainder, made monic at the end) — Sage's .gcd() does this automatically: `python g = g1.gcd(g2) ` 3. **Read the degree of the result, not just its value.** A degree-1 result x - m1 is success: m1 = -g.monic().constant_coefficient() % n. Anything else means the assumed relation is wrong, or e` is too large for the GCD to collapse cleanly — go re-check the relation before spending more compute. 4. If you only have one relation and it's an *unknown* small offset rather than a known one, polynomial GCD alone doesn't have enough constraints — that's when you fold in Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction, the general bounded-unknown-relation technique for two distinct messages tied by a small unknown offset, instead of, or on top of, the GCD step. 5. The chain-of-custody detail worth remembering: this whole technique is really "the Euclidean algorithm for integers, ported to polynomials." If you can already do modular arithmetic and the extended Euclidean algorithm by hand, you already understand the mechanics — the only new idea is that the "numbers" are now polynomials and their "size" is degree, not magnitude. 6. Field vs ring matters mechanically, not just theoretically. Euclidean division of polynomials needs to invert leading coefficients. Over a field (F_p, p prime) that always works. Over Z/n[x] with composite n it can fail mid-algorithm when a leading coefficient shares a factor with n — see below, because that failure is actually useful.

What does NOT work

- Running the GCD over the integers instead of `Zmod(n)`. Without reducing mod n first, the coefficients are enormous (they involve c1, c2 which are themselves mod-n residues but the polynomial arithmetic explodes if you don't stay in the ring) and the Euclidean algorithm either never terminates sensibly or returns garbage. Always construct the ring as Zmod(n)[x] first. - Assuming the GCD will "settle" to degree 1 even when the guessed relation is wrong. If g1.gcd(g2) comes back constant (a unit, not x - m1), that's a hard signal the relation you assumed is incorrect — not a bug to work around with more compute. Re-derive the relation (check padding scheme, counter increment, byte offset) instead of retrying the same GCD. - Ignoring a GCD computation that dies partway with a "leading coefficient not invertible" style error over composite `n`. This looks like a failure but is a gift: a non-invertible leading coefficient shares a nontrivial common factor with n. Taking gcd(coefficient, n) (plain integer GCD, not polynomial) factors n on the spot. Treat a crash here as a signal to switch tools, not to catch-and-ignore the exception. - Trying this when `e` is large. The polynomials have degree e; large e makes both the exponentiation to build g1/g2 and the GCD itself expensive, and in practice large-e RSA challenges are signaling a different attack path entirely (padding oracle, signature forgery, etc.), not a related-message setup. - Expecting polynomial GCD to work when the relation between messages is only approximately known, or known only up to a small unknown error. GCD needs the relation to be *exact* — any slack turns the shared root into two nearby-but-distinct roots and the GCD degenerates to a constant. That's the boundary where you need Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction or a lattice/LLL Reduction — the polynomial-time workhorse behind almost every lattice attack formulation instead, which tolerate a bounded unknown rather than requiring an exact known relation.

Related

Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction RSA Fundamentals — the routing hub: which artifact points to which attack Finite Field Arithmetic — the GF(p^k) substrate under AES, LFSRs, and extension-field curves/DLP Lattice Fundamentals — encoding a bounded unknown as a short vector Discrete Logarithm — the factorization of the group order picks your algorithm