Revision history [back]

You are operating on the wrong types. The extended euclidean algorithm takes polynomials as input. 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: 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.

You are operating on the wrong types. The extended euclidean algorithm takes polynomials as input. 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: 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.

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.