I Looking for a creative or quick method for finding roots in GF(p^n)

[kmitza]

TL;DR Summary

I have been revising some calculation skills in Galois theory and I ran into a problem. if we have an irreducible polynomial of degree 3 over GF(3) and we construct GF(27) as GF(3)/<f> and we have another such polynomial g(x) how do we find it's explicit roots in GF(27)

I am going to give up a bit more on the given problem. We start with polynomial $x^27 -x$ over GF(3)[x] and we factorize it using a well known theorem it turns out it factorises into the product of monic polynomials of degree 1 and 3, 11 of them all together.

We then choose one of those polynomials and consider $GF(3)/<x^3+x^2+2>$ and we're asked to find roots for the other 7 irreducible polynomials of degree 3 in GF(27) constructed this way and give isomorphisms between $GF(3)/<f>$ and $GF(3)/<g>$ for each of them.

It's not hard to see how to give the isomorphism but I am struggling with finding the explicit roots. I am wondering if anyone knows of a good method for doing this that isn't just plugging in all 27 elements the first time and then 24 and so on...

I know that there are probably computer methods for doing this but I am not looking for those.

 

[mathman]

Fix use {} around 27 for Latex.

 

[kmitza]

Fix use {} around 27 for Latex.

Thanks for the tip!

 

[fresh_42]

Summary:: I have been revising some calculation skills in Galois theory and I ran into a problem. if we have an irreducible polynomial of degree 3 over GF(3) and we construct GF(27) as GF(3)/<f> and we have another such polynomial g(x) how do we find it's explicit roots in GF(27)

I am going to give up a bit more on the given problem. We start with polynomial $x^27 -x$ over GF(3)[x] and we factorize it using a well known theorem it turns out it factorises into the product of monic polynomials of degree 1 and 3, 11 of them all together.

We then choose one of those polynomials and consider $GF(3)/<x^3+x^2+2>$ and we're asked to find roots for the other 7 irreducible polynomials of degree 3 in GF(27) constructed this way and give isomorphisms between $GF(3)/<f>$ and $GF(3)/<g>$ for each of them.

It's not hard to see how to give the isomorphism but I am struggling with finding the explicit roots. I am wondering if anyone knows of a good method for doing this that isn't just plugging in all 27 elements the first time and then 24 and so on...

I know that there are probably computer methods for doing this but I am not looking for those.

I have found two papers about it.
https://www.ams.org/journals/mcom/1...-1969-0257039-X/S0025-5718-1969-0257039-X.pdf
https://people.csail.mit.edu/dmoshkov/courses/codes/poly-factorization.pdf

I once met von zur Gathen, so I would start with the second one, but the first one is on the reference list of the second.