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.

there are two primitive polynomials which I can use to construct $GF(2^3)=GF(8)$:

$p_1(x) = x^3+x+1$

$p_2(x) = x^3+x^2+1$

$GF(8)$ created with $p_1(x)$:

0

1

$\alpha$

$\alpha^2$

$\alpha^3 = \alpha + 1$

$\alpha^4 = \alpha^3 \cdot \alpha=(\alpha+1) \cdot \alpha=\alpha^2+\alpha$

$\alpha^5 = \alpha^4 \cdot \alpha = (\alpha^2+\alpha) \cdot \alpha=\alpha^3 + \alpha^2 = \alpha^2 + \alpha + 1$

$\alpha^6 = \alpha^5 \cdot \alpha=(\alpha^2+\alpha+1) \cdot \alpha=\alpha^3+\alpha^2+\alpha=\alpha+1+\alpha^2+\alpha=\alpha^2+1$

$GF(8)$ created with $p_2(x)$:

0

1

$\alpha$

$\alpha^2$

$\alpha^3=\alpha^2+1$

$\alpha^4=\alpha \cdot \alpha^3=\alpha \cdot (\alpha^2+1)=\alpha^3+\alpha=\alpha^2+\alpha+1$

$\alpha^5=\alpha \cdot \alpha^4=\alpha \cdot(\alpha^2+\alpha+1) \cdot \alpha=\alpha^3+\alpha^2+\alpha=\alpha^2+1+\alpha^2+\alpha=\alpha+1$

$\alpha^6=\alpha \cdot (\alpha+1)=\alpha^2+\alpha$

So now let's say I want to add $\alpha^2 + \alpha^3$ in both fields. In field 1 I get $\alpha^2 + \alpha + 1$ and in field 2 I get $1$. Multiplication is the same in both fields ($\alpha^i \cdot \alpha^j = \alpha^{i+j\bmod(q-1)}$. So does it work so, that when some $GF(q)$ is constructed with different primitive polynomials then addition tables will vary and multiplication tables will be the same? Or maybe one of presented polynomials ($p_1(x), p_2(x)$) is not valid to construct field (altough both are primitive)?

share|improve this question
1  
Good answers have been posted. I just emphasize one point. In your first field $\alpha$ was a root of the equation $\alpha^3=\alpha+1$. In the second $\alpha$ was a root of the equation $\alpha^3=\alpha^2+1$. So (as $\alpha$ cannot be 0 or 1) the two $\alpha$:s cannot mean the same thing! –  Jyrki Lahtonen Jun 9 '11 at 19:23

3 Answers 3

up vote 5 down vote accepted

To more directly answer the questions asked:

  1. Yes, in general using different primitive polynomials will change the operations. If one uses expressions such as αi to refer to field elements (as is done in GAP and Magma, for instance), then the multiplication table stays the same, and the addition table changes. However, if one uses expressions like α2+α+1 (as is done in Macaulay2 and Maple, for instance) , then addition table stays the same, and the multiplication table changes. Zech logarithms are used to efficiently convert between the two representations.

  2. Both of your polynomials p1 and p2 are good. This is proven in Charles Staats's answer.

share|improve this answer
    
Since all finite fields of the same order are isomorphic to each other, is there really anything that makes one choice of primitive polynomial better than the other? –  tacos_tacos_tacos Dec 15 '12 at 23:24
    
@tacos_tacos_tacos: It depends on the application. For hardware implementations, polynomials with few nonzero terms use fewer gates. For group theory and fields of order $p^{mn}$ it is nice if the polynomials chosen for $p^m$, $p^n$, and $p^{mn}$ satisfy certain compatibility conditions. For modular character theory, it is nice if everyone in the entire world uses exactly the same polynomials, so polynomials satisfying a somewhat arbitrary but reproducible condition are used. –  Jack Schmidt Mar 26 at 3:41

The generator $\alpha$ for your field with the first description cannot be equal to the generator $\beta$ for your field with the second description. An isomorphism between $\mathbb{F}_2(\alpha)$ and $\mathbb{F}_2(\beta)$ is given by taking $\alpha \mapsto \beta + 1$; you can check that $\beta + 1$ satisfies $p_1$ iff $\beta$ satisfies $p_2$.

share|improve this answer

The situation is not so different in a simpler context, the field of 5 elements, also known as the integers modulo 5. Whether $\alpha$ is $2$ or $3$, the field is $0,1,\alpha,\alpha^2,\alpha^3$, but whether $\alpha+\alpha+1=0$ depends on which $\alpha$ you choose.

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.