I want to implement Extended GCD with SageMath so that the internal can be printed. The below is a modification of this
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?