Ask Your Question
0

Finding Inverse of a Polynomial in a Galois Ring $GR(2^k,d)$

asked 2024-08-03 13:01:52 +0100

Doron gravatar image

updated 2024-11-20 08:25:34 +0100

FrédéricC gravatar image

I'm trying to find the inverse of the polynomial ( 7X^2 + 1 ) in the Galois ring ( GR(2^3, 3) ) where the modulus polynomial is ( h(X) = X^3 + X + 1 ). However, I keep encountering the error "Flint exception (Impossible inverse): Cannot invert modulo (2 4)."

Here is the SageMath code I'm using:

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')

poly = GaloisRing(7*X^2 + 1)

poly_elem = poly.lift()
poly_modulus = h

g, u, v = xgcd(poly_elem, poly_modulus)

if g != 1: raise ValueError(f"The element {elem} does not have an inverse in the Galois ring.")
inverse = GaloisRing(u % poly_modulus)

Then I get an error:

Flint exception (Impossible inverse):Cannot invert modulo 2*4
------------------------------------------------------------------------
(no backtrace available)
------------------------------------------------------------------------
Unhandled SIGABRT: An abort() occurred.
This probably occurred because a *compiled* module has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Python will now terminate.

Questions: 1. Why am I encountering this error when trying to find the inverse of ( 7X^2 + 1 ) in ( \text{GR}(2^3, 3) )? 2. Is there a mistake in how I'm defining the Galois ring or using the extended Euclidean algorithm? 3. How can I correctly find the inverse of \7X^2 + 1 ) in this Galois ring?

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
0

answered 2024-08-04 06:24:44 +0100

Max Alekseyev gravatar image

updated 2024-08-04 11:46:24 +0100

xgcd should be computed over ZZ, not R - e.g.:

g, u, v = xgcd(poly_elem.change_ring(ZZ), poly_modulus.change_ring(ZZ))

and the formula for inverse should be changed to

inverse = GaloisRing(u)/g
edit flag offensive delete link more

Comments

It works! Thanks!

Doron gravatar imageDoron ( 2024-08-04 12:39:57 +0100 )edit

Can you explain or hint why the extended Euclidean algorithm might give a gcd that different from 1?

Doron gravatar imageDoron ( 2024-08-04 14:31:29 +0100 )edit

To get g=1, u and v would have to have fractional coefficients, which are not in ZZ. You may try to compute xgcd over QQ to get g=1.

Max Alekseyev gravatar imageMax Alekseyev ( 2024-08-04 16:47:22 +0100 )edit

@Doron If this pointed answer does satisfy the needs, please consider accepting (and upvoting) it! So it will show up next time as solved!

dan_fulea gravatar imagedan_fulea ( 2024-08-14 18:36:59 +0100 )edit

Unfortunately, I don't have enough point to upvote

Doron gravatar imageDoron ( 2024-08-20 12:16:21 +0100 )edit
0

answered 2024-08-04 10:53:45 +0100

Doron gravatar image

updated 2024-08-04 11:36:26 +0100

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 seems to be incorrect (as if I multiply both elements and take modulus, I get 3.). I tried in Mathematica and the result for iverse was 6X^2 + 5X + 4.
If I only try xgcd(7
X^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?

edit flag offensive delete link more

Comments

You need further fix the formula for inverse:

inverse = GaloisRing(u)/g
Max Alekseyev gravatar imageMax Alekseyev ( 2024-08-04 11:11:07 +0100 )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

Stats

Asked: 2024-08-03 12:55:14 +0100

Seen: 319 times

Last updated: Aug 04