The greatest common divisor (gcd) of two polynomials is a highest-degree polynomial dividing both, with equivalent answers differing by a nonzero constant. Over a finite field, compute it with the remainders from Euclid’s polynomial division. The result supports irreducible-polynomial searches and inversion-related elliptic-curve arithmetic. section 10.0 section 10.8
Implement the routine with this execution flow:
- Return the other polynomial when either input is zero. section 10.1 section 10.4
- Assign the higher-degree input to the working numerator aw and the lower-degree input to bw. section 10.1 section 10.4
- Repeatedly divide aw by bw, discard the quotient, replace aw with bw, and replace bw with the remainder. section 10.1 section 10.8
- Stop when bw has degree zero; return aw if that constant is zero, otherwise return bw. section 10.4
Remainder-driven computation
For gcd(a, b), initialize aw and bw in descending degree order. Compute r = aw / bw, where r denotes the remainder, then iterate with (aw, bw) ← (bw, r). When the final remainder is zero, the preceding working polynomial is the gcd; otherwise the final constant remainder is returned. If the inputs share no nonconstant factor, that result is 1 or another nonzero constant. section 10.1 section 10.4
Listing 10.3 Gcd main loop
poly_init(&q);
poly_init(&r);
while(bw.deg > 0) #1
{
poly_euclid(&q, &r, aw, bw); #2
poly_copy(&aw, bw); #3
poly_copy(&bw, r); #4
}
if(!mpz_cmp_ui(bw.coef[0], 0)) #5
poly_copy(d, aw); #5
else #6
poly_copy(d, bw); #6
poly_clear(&r);
poly_clear(&q);
poly_clear(&bw);
poly_clear(&aw);
}
The main-loop listing maps the mathematical recurrence directly to initialized remainder storage, repeated polynomial division, working-value updates, termination, and cleanup. section 10.4
