finding inverse of en element wiht Ext-GCD fails due to defining polynomial converts zero in function

asked 2020-08-25 15:44:40 -0600

kelalaka gravatar image

I'm trying to implement a fast Ext-GCD to find the inverse of an element in the finite field $GF(2^8)$ of AES.

def egcd(a, b):
    print(a)
    print(b)
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b/a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y


#Base field
R.<y> = PolynomialRing(GF(2), 'y')

#Defining polynomial
G = y^8+y^4+y^3+y+1

#The field extension
S.<x> = QuotientRing(R, R.ideal(G))
S.is_field()

print(egcd(x^8+x^4+x^3+x+1,x^7+x+1))

When the $x^8+x^4+x^3+x+1$ is sent to this function it is converted to zero, so the print(a) prints zero.

Is there a way to protect the variable from converting to zero so that this function can work as intended?

edit retag flag offensive close merge delete