I need to implement extended Euclidian algortihm for polynomials to get coefficients of Bézout's identity. Problem is I'm struggling with correct implementation of such 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 operatrions such as +, -,*. Every performed operations are over some finite field which is specified within polynomial class (F3 forexample) and modular aritmethics is already implemented and applied in every aspect of program.
So concider you have following:
Polynomial (type), that has all basic operations.
My question is how to efficiently transform method gcdExtended <- from this page on one, that would take my Polynomial class as an parameters instead of int type.
I'm on good way to 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 first code snipped means I'm supposed to do first iteration of Euclidean algorithm and return remainder? And what does b / a mean in 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.
Edited: Ofc returned x & b has to be of type Polynomial <=> ax+by = gcd(a,b).