I need to implement an extended Euclidean algorithm for polynomials to get coefficients of Bézout's identity. The problem is I'm struggling with the correct implementation of such a function. I've found some code examples which shows solution but for N numbers (int). In my project, I'm working with my own class of polynomials and this custom type already has well-tested elementary operations such as +, -,*. Every performed operation is over some finite field which is specified within the polynomial class (F3 for example) and modular arithmetics is already implemented and applied in every aspect of the program.

So consider you have the following:

Polynomial (type), which has all basic operations.

My question is how to efficiently transform method gcdExtended <- from this page on one, which would take my Polynomial class as a parameter instead of int type.

I'm on a good way to a solution on this, but I'm not sure about lines:

int gcd = gcdExtended(b % a, a, x1, y1);

and

x = y1 - (b / a) * x1;

Does b % a in the first code snipped mean I'm supposed to do the first iteration of the Euclidean algorithm and return remainder? And what does b / a mean in the second one?

This should not be that complicated but I think I've been staring at this project for 2 long already and now I'm frozen at this simple thing.

Ofc returned x & b has to be of type Polynomial <=> ax+by = gcd(a,b).