1
$\begingroup$

I'd like to calculate derivative of polynomial in $GF(9)\equiv GF(3^2)$. For polynomials in fields of characteristic of $2$ it is quite easy, because operations are modulo 2 which means that there are multiplications by 1 or 0. But in GF(3) operations are modulo 3. For example, there is following polynomial in $GF(9)$: $$p(x)=\alpha x^2 + x$$ Derivative of this polynomial is: $$p'(x)=2 \cdot \alpha x + 1$$ Question is now, how to multiply $2$ by $\alpha$ (elements from $GF(3) (0,1,2)$ by elements in $GF(9) (0, 1, \alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6, \alpha^7)$)?

Edit:

Let generator polynomial for GF(9) be $w(x) = x^2 + x + 2$.

Edit2:

Polynomial representation of field elements can be used too.

  • 2
    Do you really want to express every element in terms of powers of $\alpha$? This seems unnecessarily complicated. You can express every element as $a + b \alpha$ where $a, b \in \mathbb{F}_3$ and this is much nicer; it is easy to both add and multiply this way. I don't think $2 \alpha$ needs a more complicated name than $2 \alpha$.2011-08-09
  • 0
    Program I'm writing uses such expression.2011-08-09
  • 0
    Well, I guess if you write a lookup table for addition, it shouldn't matter.2011-08-09
  • 2
    Or, if memory is a concern, a [Zech logarithm table](http://en.wikipedia.org/wiki/Zech%27s_logarithms) will do also. That is/was a standard trick for carrying out addition on a finite field, when elements are stored as their logarithms (w.r.t. a chosen primitive element).2011-08-09
  • 0
    THE HORROR. The wikipedia page on Zech logarithm's did contain the correct definition, but the rest of the material there was, to put it nicely, misguided. I edited the Wikipedia article, but this was my first edit, so we may have to wait whether it sticks. I have some doubts about whether the people who make decisions there actually know what they are doing.2011-12-13

1 Answers 1

4

Looks like $\alpha$ is a primitive element (=a generator of the multiplicative group), so it is of order $9-1=8$. Therefore $\alpha^4$ is of order 2. IOW $\alpha^4=-1=2.$ Thus $2\alpha=\alpha^4\cdot\alpha=\alpha^5$ in your table.