Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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$. –  Qiaochu Yuan Aug 9 '11 at 15:31
    
Program I'm writing uses such expression. –  scdmb Aug 9 '11 at 15:33
    
Well, I guess if you write a lookup table for addition, it shouldn't matter. –  Qiaochu Yuan Aug 9 '11 at 15:50
2  
Or, if memory is a concern, a Zech logarithm table 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). –  Jyrki Lahtonen Aug 9 '11 at 15:52
    
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. –  Jyrki Lahtonen Dec 13 '11 at 12:08

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.