Computation in a ring and Galois Field

[ftneek]

I'm taking an applied abstract algebra course and am trying figure out how to check my work using the hp prime. Attached are a few problems we did in class. My professor gave me a skeptical look when I said I think my calculator is able to do these types of calculations, so I'd like to show them it can.

I worked out problem 4 by hand and got the inverse is x^3 + x + 1. On my calculator I entered GF(2,k^5 + k^3 + 1) and was able to enter inv(k^3 + 1) to obtain k^3 + k + 1, and the product is indeed 1.

Now when I try problem 1 I know there is an inverse because the gcd of the the two polynomials is 1 (in mod 2). But when I clear my variables and tried entering GF(2,k^4) I'm met with the error that k^4 is not irreducible. I was able to check my answer I got by hand by using the expression ((x^3 + x^2 + 1)%%2)*((x^3 + x^2 + 1)%%2) mod ((x^4)%%2). To find the inverse using my calculator I tried a few expressions such as inv(((x^3 + x^2 + 1)%%2) mod ((x^4)%%2)) but it returned a fraction which isn't what I was expecting. My question is how can I actually find this inverse using my calculator?

I'm still learning about Galois fields, I'm more familiar working in integers mod p or m. I think I understand it wouldn't be a field if the polynomial is reducible, so it makes sense why GF is giving that error. But is there some other way to perform these types of computations on the hp prime where the modulus polynomial is reducible?

[parisse]

You can not build a finite field with a polynomial that is not irreducible. But that's not the right way to invert a polynomial modulo another one, the right way is a call to the extended gcd algorithm. The commandname is egcd.
For example if a:=x^3 + 1 %% 2and b:=x^5+x^3+1 %% 2, egcd(a,b) will return three polynomials u, v and d such that d is the gcd of the input polynomials and a*u+b*v=d. If a and b are coprime, d will be 1 and modulo b you have a*u==1, therefore the inverse of a is u.

[ftneek]

Thanks for the explanation, I appreciate it.

One more question about the egcd() command. If integers/constants are polynomials of degree 0, should the command work for integers as well? For example I tried egcd(161,70) and it returned [1 0 161] while gcd(161,70) returns 7.

[parisse]

For integers, the commandname is iegcd.

[jte]

(04-04-2023 10:18 PM)ftneek Wrote:  I'm taking an applied abstract algebra course and am trying figure out how to check my work using the hp prime. Attached are a few problems we did in class. My professor gave me a skeptical look when I said I think my calculator is able to do these types of calculations, so I'd like to show them it can.
⋮

When I first read this I thought about piping up as not long before your post I was looking through raw flash dumps from calculators. BCH codes are used for error correction (this is a standard approach for error correction with flash); the HP Prime certainly does many calculations involving Galois fields (at a very high rate of speed, even, when interacting with its flash memory) — as do many devices employing flash memory for storage. (Raw flash dumps include “all the bits”, not just those presented after performing error correction.) But these calculations are not presented to users...

Prof. Parisse came to the rescue with much more pertinent information.