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

• I
• kmitza
In summary, the two papers discuss a method for finding explicit roots for polynomials in GF(3) constructed using monic polynomials of degree 1 and 3. The first paper is older and uses a von zur Gathen method, while the second paper is newer and uses a computer algorithm.
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.

Fix use {} around 27 for Latex.

mathman said:
Fix use {} around 27 for Latex.
Thanks for the tip!

kmitza said:
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.

## 1. How can I find roots in GF(p^n) quickly?

One method for finding roots in GF(p^n) quickly is by using the Tonelli-Shanks algorithm, which is specifically designed for finding square roots in finite fields. This algorithm has a time complexity of O(log^2 p), making it a fast and efficient method for finding roots in GF(p^n).

## 2. What is the Tonelli-Shanks algorithm?

The Tonelli-Shanks algorithm is a method for finding square roots in finite fields, specifically in GF(p^n). It is based on the properties of quadratic residues and non-residues in finite fields, and has a time complexity of O(log^2 p), making it a fast and efficient method for finding roots in GF(p^n).

## 3. Is there a creative method for finding roots in GF(p^n)?

One creative method for finding roots in GF(p^n) is by using the Cipolla-Lehmer algorithm, which is based on the properties of polynomials in finite fields. This algorithm has a time complexity of O(log^3 p), making it slightly slower than the Tonelli-Shanks algorithm, but it can be a useful alternative for finding roots in GF(p^n).

## 4. Can I use brute force to find roots in GF(p^n)?

Technically, yes, you can use brute force to find roots in GF(p^n). However, this method is not efficient and becomes increasingly difficult as the size of the finite field (p^n) increases. It is recommended to use specific algorithms, such as the Tonelli-Shanks or Cipolla-Lehmer algorithm, for finding roots in GF(p^n) instead of brute force.

## 5. Are there any limitations to finding roots in GF(p^n)?

One limitation to finding roots in GF(p^n) is that the finite field must be a prime field (p) raised to a power (n). Additionally, the size of the finite field can also impact the efficiency of finding roots, with larger finite fields being more challenging to work with. It is important to consider these limitations when choosing a method for finding roots in GF(p^n).

Replies
4
Views
2K
Replies
1
Views
2K
Replies
3
Views
865
Replies
5
Views
3K
Replies
8
Views
3K
Replies
1
Views
1K
Replies
2
Views
2K
Replies
1
Views
2K
Replies
6
Views
4K
Replies
9
Views
2K