# ExtGCD in Finite Fields

I want to implement Extended GCD with SageMath so that the internal can be printed. The below is a modification of this. This should be straightforward, however, I might miss something;

def extended_euclides(a,b):

s = 0; old_s = 1
t = 1; old_t = 0
r = b; old_r = a

while r != 0:
quotient,rem = old_r.quo_rem(r)

old_r, r = r, old_r - quotient*r
old_s, s = s, old_s - quotient*s
old_t, t = t, old_t - quotient*t
return [old_r, old_s, old_t]

K.<a> =  GF(2^8, modulus=x^8+x^4+x^3+x+1)
print(K)
print("m = ", K.modulus())

g = a^7 + a^5 + a^4 + a
h = a^4 + a^2 + 1

r,s,t = extended_euclides(g,h)

print("The GCD of \n \t [ {} ] and  \n \t [ {} ]  is \n\t [ {} ]".format(g,h,r))
print("Its Bézout coefficients are {} and {}".format(s,t))
assert r == g.gcd(h), "The gcd should be {}!".format(g.gcd(h))
assert r == s*g + t*h, "The cofactors are wrong!"


In the end, I've got the assertion error AssertionError: The gcd should be 1!

Any idea to solve this?

edit retag close merge delete

Sort by » oldest newest most voted

You are operating on the wrong types. The extended euclidean algorithm takes polynomials as input and returns polynomials as output. Elements of a finite field are not polynomials, though they can be represented as such.

The function is fine (possibly up to a plusminus sign in the output if you prefer); its correct usage is as follows:

sage: r,s,t = extended_euclides(g.polynomial(), h.polynomial())
sage: r, s, t
(1, a^3 + a^2 + a + 1, a^6 + a^5 + a^4 + a + 1)
sage: s*g.polynomial() + t*h.polynomial() == r
True
sage: K(s)*g + K(t)*h == K(r)
True


P.S. The definition of quotient inside the function can be replaced by quotient = old_r // r.

more

I see. I rather consider calculating it over the finite field instead of polynomials. Since the polynomials are always less than the primitive then this is ok.

( 2022-04-13 02:22:58 +0200 )edit