Revision history [back]

I still can't find the inverse of the polynomial 7*X^2 +1 in the Galois ring GR(2^3,3), where the modulus polynomial is h(X)=X^3+X+1

I received advice to compute the extended GCD over 𝑍. For instance, to find the inverse of 7X^2 + 1 (mod X^3+X+1), I got 2X^2 + 7X + 4 (see code attached).
If I only try xgcd(7X^2 + 1 , X^3+X+1) then the program crashes.

k = 3
d = 3
R = IntegerModRing(2**k)
GR = PolynomialRing(R, 'X')
X = GR.gen()
h = X^3 + X + 1
GaloisRing = GR.quotient(h, 'X')

elem = GaloisRing(7*X^2 + 1)
poly_elem = elem.lift()
poly_modulus = GR(h)
g, u, _ = xgcd(poly_elem.change_ring(ZZ), poly_modulus.change_ring(ZZ))   
inverse = GaloisRing(u % poly_modulus)
print(inverse)

How can I correctly find and verify the inverse of an element in this Galois ring?

I still can't find the inverse of the polynomial 7*X^2 +1 in the Galois ring GR(2^3,3), where the modulus polynomial is h(X)=X^3+X+1

I received advice to compute the extended GCD over 𝑍. For instance, to find the inverse of 7X^2 + 1 (mod X^3+X+1), I got 2X^2 + 7X + 4 (see code attached). attached), which I believe is wrong (as if I multiply both elements and take modulus, I get 3) .
If I only try xgcd(7X^2 + 1 , X^3+X+1) then the program simply crashes.

k = 3
d = 3
R = IntegerModRing(2**k)
GR = PolynomialRing(R, 'X')
X = GR.gen()
h = X^3 + X + 1
GaloisRing = GR.quotient(h, 'X')

elem = GaloisRing(7*X^2 + 1)
poly_elem = elem.lift()
poly_modulus = GR(h)
g, u, _ = xgcd(poly_elem.change_ring(ZZ), poly_modulus.change_ring(ZZ))   
inverse = GaloisRing(u % poly_modulus)
print(inverse)

How can I correctly find and verify the inverse of an element in this Galois ring?

I still can't find the inverse of the polynomial 7*X^2 +1 in the Galois ring GR(2^3,3), where the modulus polynomial is h(X)=X^3+X+1

I received advice to compute the extended GCD over 𝑍. For instance, to find the inverse of 7X^2 + 1 (mod X^3+X+1), I got 2X^2 + 7X + 4 (see code attached), which I believe is wrong seems to be incorrect (as if I multiply both elements and take modulus, I get 3) . 3.). I tried in Mathematica and the result for iverse was 6X^2 + 5X + 4.
If I only try xgcd(7X^2 + 1 , X^3+X+1) then the program simply crashes.

k = 3
d = 3
R = IntegerModRing(2**k)
GR = PolynomialRing(R, 'X')
X = GR.gen()
h = X^3 + X + 1
GaloisRing = GR.quotient(h, 'X')

elem = GaloisRing(7*X^2 + 1)
poly_elem = elem.lift()
poly_modulus = GR(h)
g, u, _ = xgcd(poly_elem.change_ring(ZZ), poly_modulus.change_ring(ZZ))   
inverse = GaloisRing(u % poly_modulus)
print(inverse)

How can I correctly find and verify the inverse of an element in this Galois ring?