2

As I understood, a minimal polynomial for some $A$ over a finite field is an irreducible polynomial with a minimal degree for which $A$ is a "root".

However, I can't understand how to find one. For example, if we have an element of order 13 over $GF(27)$. (I want to find a minimal polynomial for such an $A$)

T J. Kim
  • 610
Pineapple
  • 21
  • 1
    How do you specify $A$, other than saying which polynomial it is a root of? If you have no information about $A$, should we just find all deg 13 elements in the closure? – ziggurism May 04 '18 at 15:11
  • I know that the degree of $A$ is 13 in multiplicative group over a finite field $GF(27)$. And I want to find its minimal polynomial – Pineapple May 04 '18 at 15:25
  • Are you looking for an element of order $13$ as opposed to degree? This may be lost in translation, so please define, "degree". I'm not sure there is anything called "the degree of an element", possibly that could be a shorthand for "the degree of the minimal polynomial of an element" which also equals "the degree of the field extension generated by that element. Furthermore, the order of an element is independent of the field. Because you use the phrase "degree over a field $K$" I rather suspec that you do mean the degree of field extension = degree of the minimal polynomial. – Jyrki Lahtonen May 08 '18 at 12:42
  • (cont'd) The only answerer assumed that you meant "order" as opposed to "degree". This in turn is suggested by your request for a minimal polynomial of such an element. That's because there are $$\frac1{13}(27^{13}-27)=311735011770690480$$ irreducible polynomials of degree $13$ over $GF(27)$ and they have $13$ times that many roots $A$, all lying in the field $GF(27^{13})$. On the other hand, there are $12$ elements of order $13$. They all belong to the field $GF(27)$. They have $13$ distinct minimal polynomials over $GF(27)$, all of degree $1$ (see Morgan Rodgers's answer). – Jyrki Lahtonen May 08 '18 at 12:53
  • (cont'd) But, they have only four minimal polynomials ** OVER GF(3)**, all those minimal polynomials have degree three. $x^3-x-1$ is one such. Occam's razor tells me that if this from your first course in finite fields, then the question really asks for those cubic polynomials. But, if you are reading a paper on coding/crypto/some other application of finite fields, then the answer you need is one of the alternatives. So, please clarify :-) – Jyrki Lahtonen May 08 '18 at 12:58
  • Yeah, i meant an element of $order$ 13, sorry. And it is really from my first course in finite fields. May I ask smth a bit offtop then. Is there an algorithm to find an irreducable polynomial over GF(3) of degree 3? – Pineapple May 09 '18 at 19:34

1 Answers1

1

If $\alpha$ has order 13, then it is a root of $x^{13}-1$. But this polynomial is not irreducible. So you need to find the irreducible factor of $x^{13}-1$ that has $\alpha$ as a root.

For your particular example, if you take $\alpha$ to be the generator of $GF(27)$, then $\alpha$ has order 26. Then $\alpha^{2}$ will have order 13.

When you talk about minimal polynomials you want to know over which field. For example, an element $\beta$ of order 13 is in $GF(27)$, so the minimal polynomial over $GF(27)$ will be $x-\beta$. On the other hand, if you want to find the minimal polynomial of $\beta$ over $GF(3)$, it will be something different.

For more general examples, if you look up cyclotomic cosets you will find a method for factoring a polynomial like this, and if you look up cyclotomic polynomials it should help you find the factor you are looking for.

xxxxxxxxx
  • 13,302