Ask Your Question
1

ExtGCD in Finite Fields

asked 2022-04-12 11:02:29 +0200

klx gravatar image

updated 2022-04-12 11:14:57 +0200

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 flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
2

answered 2022-04-12 15:55:54 +0200

rburing gravatar image

updated 2022-04-12 15:58:36 +0200

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.

edit flag offensive delete link more

Comments

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.

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-04-12 11:02:29 +0200

Seen: 26 times

Last updated: Apr 12