Mixing
Find the elements of the extension field using primitive polynomial over $GF(4)$
$begingroup$
Let $p(z) = z^2 + z + 2$ be a primitive polynomial. I want to construct the elements of the extensional field $GF(4^2)= GF(16).$
Since $p(z)$ is primitive polynomial , it should generate the elements of the extension field.
Let $alpha$ be zero point then :
$alpha^2 + alpha + 2 rightarrow alpha^2 = -alpha-2 rightarrow alpha^2 = 3alpha + 2$.
Using $alpha$ :
- $alpha^1 = alpha$
$alpha^2 = 3alpha+2$ and according to the book, $alpha^2 = alpha+2$ but $-1 mod 4 = 3$.
Since the base is $4$ how can it be that the correct value of $alpha^2 = alpha + 2$?
I have mostly solved problems where the base is a prime number and the same procedure i have used here.
polynomials galois-theory finite-fields cryptography coding-theory
asked Jan 28 at 1:52
Khan SaabKhan Saab
1979
$endgroup$
add a comment |
$begingroup$
Let $p(z) = z^2 + z + 2$ be a primitive polynomial. I want to construct the elements of the extensional field $GF(4^2)= GF(16).$
Since $p(z)$ is primitive polynomial , it should generate the elements of the extension field.
Let $alpha$ be zero point then :
$alpha^2 + alpha + 2 rightarrow alpha^2 = -alpha-2 rightarrow alpha^2 = 3alpha + 2$.
Using $alpha$ :
- $alpha^1 = alpha$
$alpha^2 = 3alpha+2$ and according to the book, $alpha^2 = alpha+2$ but $-1 mod 4 = 3$.
Since the base is $4$ how can it be that the correct value of $alpha^2 = alpha + 2$?
I have mostly solved problems where the base is a prime number and the same procedure i have used here.
polynomials galois-theory finite-fields cryptography coding-theory
asked Jan 28 at 1:52
Khan SaabKhan Saab
1979
$endgroup$
1
$begingroup$
$GF(4)$ is not the same as $mathbb{Z}/(4)$; it's a degree $2$ extension of $mathbb{Z}/(2)$. So over $GF(4)$, $z^2+z+2=z^2+z$ is not even irreducible.
$endgroup$
– Eric Wofsey
Jan 28 at 1:59
$begingroup$
@EricWofsey I want the coefficients to be one of the these values ${0,1,2,3}$. I need this for BCH codes where the coefficients are not only binary.
$endgroup$
– Khan Saab
Jan 28 at 2:06
$begingroup$
Khan Saab, see my answer for an explanation as to how $p(z)$ becomes a primitive polynomial. When we interpret the coefficient $2$ as a zero of $x^2+x+1$ in the field $GF(4)$, then $z^2+z+2$ is irreducible and also primitive. You need to adjust your meaning of $2$ for all this to make sense. Starting from $1+1neq2$.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:52
$begingroup$
Eric Wofsey did explain the relevant bits in his answer. I simply elaborated.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:30
add a comment |
$begingroup$
Let $p(z) = z^2 + z + 2$ be a primitive polynomial. I want to construct the elements of the extensional field $GF(4^2)= GF(16).$
Since $p(z)$ is primitive polynomial , it should generate the elements of the extension field.
Let $alpha$ be zero point then :
$alpha^2 + alpha + 2 rightarrow alpha^2 = -alpha-2 rightarrow alpha^2 = 3alpha + 2$.
Using $alpha$ :
- $alpha^1 = alpha$
$alpha^2 = 3alpha+2$ and according to the book, $alpha^2 = alpha+2$ but $-1 mod 4 = 3$.
Since the base is $4$ how can it be that the correct value of $alpha^2 = alpha + 2$?
I have mostly solved problems where the base is a prime number and the same procedure i have used here.
polynomials galois-theory finite-fields cryptography coding-theory
asked Jan 28 at 1:52
Khan SaabKhan Saab
1979
$endgroup$
Let $p(z) = z^2 + z + 2$ be a primitive polynomial. I want to construct the elements of the extensional field $GF(4^2)= GF(16).$
Since $p(z)$ is primitive polynomial , it should generate the elements of the extension field.
Let $alpha$ be zero point then :
$alpha^2 + alpha + 2 rightarrow alpha^2 = -alpha-2 rightarrow alpha^2 = 3alpha + 2$.
Using $alpha$ :
- $alpha^1 = alpha$
$alpha^2 = 3alpha+2$ and according to the book, $alpha^2 = alpha+2$ but $-1 mod 4 = 3$.
Since the base is $4$ how can it be that the correct value of $alpha^2 = alpha + 2$?
I have mostly solved problems where the base is a prime number and the same procedure i have used here.
polynomials galois-theory finite-fields cryptography coding-theory
polynomials galois-theory finite-fields cryptography coding-theory
asked Jan 28 at 1:52
Khan SaabKhan Saab
1979
asked Jan 28 at 1:52
Khan SaabKhan Saab
1979
asked Jan 28 at 1:52
Khan SaabKhan Saab
1979
asked Jan 28 at 1:52
Khan SaabKhan Saab
1979
asked Jan 28 at 1:52
Khan SaabKhan Saab
1979
1979
1
$begingroup$
$GF(4)$ is not the same as $mathbb{Z}/(4)$; it's a degree $2$ extension of $mathbb{Z}/(2)$. So over $GF(4)$, $z^2+z+2=z^2+z$ is not even irreducible.
$endgroup$
– Eric Wofsey
Jan 28 at 1:59
$begingroup$
@EricWofsey I want the coefficients to be one of the these values ${0,1,2,3}$. I need this for BCH codes where the coefficients are not only binary.
$endgroup$
– Khan Saab
Jan 28 at 2:06
$begingroup$
Khan Saab, see my answer for an explanation as to how $p(z)$ becomes a primitive polynomial. When we interpret the coefficient $2$ as a zero of $x^2+x+1$ in the field $GF(4)$, then $z^2+z+2$ is irreducible and also primitive. You need to adjust your meaning of $2$ for all this to make sense. Starting from $1+1neq2$.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:52
$begingroup$
Eric Wofsey did explain the relevant bits in his answer. I simply elaborated.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:30
add a comment |
1
$begingroup$
$GF(4)$ is not the same as $mathbb{Z}/(4)$; it's a degree $2$ extension of $mathbb{Z}/(2)$. So over $GF(4)$, $z^2+z+2=z^2+z$ is not even irreducible.
$endgroup$
– Eric Wofsey
Jan 28 at 1:59
$begingroup$
@EricWofsey I want the coefficients to be one of the these values ${0,1,2,3}$. I need this for BCH codes where the coefficients are not only binary.
$endgroup$
– Khan Saab
Jan 28 at 2:06
$begingroup$
Khan Saab, see my answer for an explanation as to how $p(z)$ becomes a primitive polynomial. When we interpret the coefficient $2$ as a zero of $x^2+x+1$ in the field $GF(4)$, then $z^2+z+2$ is irreducible and also primitive. You need to adjust your meaning of $2$ for all this to make sense. Starting from $1+1neq2$.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:52
$begingroup$
Eric Wofsey did explain the relevant bits in his answer. I simply elaborated.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:30
1
1
$begingroup$
$GF(4)$ is not the same as $mathbb{Z}/(4)$; it's a degree $2$ extension of $mathbb{Z}/(2)$. So over $GF(4)$, $z^2+z+2=z^2+z$ is not even irreducible.
$endgroup$
– Eric Wofsey
Jan 28 at 1:59
$begingroup$
$GF(4)$ is not the same as $mathbb{Z}/(4)$; it's a degree $2$ extension of $mathbb{Z}/(2)$. So over $GF(4)$, $z^2+z+2=z^2+z$ is not even irreducible.
$endgroup$
– Eric Wofsey
Jan 28 at 1:59
$begingroup$
@EricWofsey I want the coefficients to be one of the these values ${0,1,2,3}$. I need this for BCH codes where the coefficients are not only binary.
$endgroup$
– Khan Saab
Jan 28 at 2:06
$begingroup$
@EricWofsey I want the coefficients to be one of the these values ${0,1,2,3}$. I need this for BCH codes where the coefficients are not only binary.
$endgroup$
– Khan Saab
Jan 28 at 2:06
$begingroup$
Khan Saab, see my answer for an explanation as to how $p(z)$ becomes a primitive polynomial. When we interpret the coefficient $2$ as a zero of $x^2+x+1$ in the field $GF(4)$, then $z^2+z+2$ is irreducible and also primitive. You need to adjust your meaning of $2$ for all this to make sense. Starting from $1+1neq2$.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:52
$begingroup$
Khan Saab, see my answer for an explanation as to how $p(z)$ becomes a primitive polynomial. When we interpret the coefficient $2$ as a zero of $x^2+x+1$ in the field $GF(4)$, then $z^2+z+2$ is irreducible and also primitive. You need to adjust your meaning of $2$ for all this to make sense. Starting from $1+1neq2$.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:52
$begingroup$
Eric Wofsey did explain the relevant bits in his answer. I simply elaborated.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:30
$begingroup$
Eric Wofsey did explain the relevant bits in his answer. I simply elaborated.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:30
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You seem confused about what $GF(4)$ is: it's not $mathbb{Z}/(4)$ (which is not even a field). You can represent $GF(4)$ as an extension of $GF(2)=mathbb{Z}/(2)$ by an element $beta$ such that $beta^2=beta+1$. You can identify $GF(4)$ with the set ${0,1,2,3}$ by mapping $beta$ to $2$ and $beta+1$ to $3$, which appears to be what the book you refer to has in mind, but this does not mean you are working mod $4$ (the addition and multiplication operations are not ordinary mod $4$ addition and multiplication on ${0,1,2,3}$).
In particular, $1+1=0$ in $GF(4)$ and so $alpha+2$ and $-alpha-2$ are the same thing, and so you have $alpha^2=alpha+2$.
answered Jan 28 at 2:45
Eric WofseyEric Wofsey
191k14216349
$endgroup$
$begingroup$
You are correct about the confusion between $GF(4)$ and $Bbb{Z}/(4)$. Yet, I'm sure the OP got their primitive polynomial from some source. See my answer for an explanation.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:51
$begingroup$
And +1 for including the interpretation $beta=2$, $beta+1=3$. I missed that in my first reading.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:15
add a comment |
$begingroup$
Here is an educated guess. You are confused by the difference between algebraic/arithmetic and computers representation of elements of $GF(4)$.
The field
$$GF(4)={0,1,beta,beta+1},$$
where the arithmetic comes from the rules $1+1=beta+beta=0$, $beta^2=beta+1$. The element $beta$ (it could be denoted by something else if you wish) has no integer naturally associated with it.
However, in computer implementations we (including code written by yours truly worth a couple hundred CPU hours) we write the elements of $GF(4)$ as string of two bits:
$$0=00_2,quad 1=01_2,quad beta=10_2,quad beta+1=11_2.$$
Do you see the idea? The element $b_0+b_1beta$ is represented as the bitstring $b_1b_0$. Similarly we represent elements of $GF(2^m)$ as strings of $m$ bits. A big advantage of this is that addition in the field $GF(2^m)$ then becomes bitwise XOR of those bitstrings. Most (all?) computer hardwares have a superfast built-in function for performing bitwise XOR of two registers. So that's one of the basic arithmetic operations handed to us on a silver platter. Too good to pass up! The programmer only needs to worry about implementing the multiplication of $GF(2^m)$.
For smallish values of $m$ there are efficient ways of doing that (Caveat: there are other ways
of implementing e.g. $GF(4^2)$ even more efficiently for devices really short of memory).
Anyway, having fixed an internal presentation of elements of $GF(2^m)$, programmers
occasionally refer to them as integers represented by the same string of bits.
Because the integer $2$ is $10_2$ in binary, such a programmer may choose to refer to
$beta$ as $2$ and $beta+1$ as $11_2=3$. But they know that this is safe only among people in the know. If you do this in a general math forum, you are bound to confuse people. If you are a student still learning about this, you are bound to become confused by program documentation unless you first study this difference between algebraic notation and data representation internal to a computer.
So you may think of $GF(4)$ as the set ${0,1,2,3}$, but then you must include rules like $1+1=0$, $2+2=0$, $3=2+1$ in the definition of your addition.
And, you also need to make rules like $2*2=3$, $2*3=1$ a part of your definition of multiplication. If you don't know this, you will be confused, and your questions will confuse others.
The above is all standard, but I claimed to have AN EDUCATED GUESS. Here it is.
If we present $beta=2$ internally, then the quadratic
$$
p(x)=x^2+x+beta "=" x^2+x+2
$$
is a primitive polynomial. It takes a bit of experience to see this at a glance.
But, see the last part of my linked answer (prepared with referrals like this in mind). You see that I explain there why $x^2+x+beta$ is the minimal polynomial (over $GF(4)$) of some of the zeros of the well known primitive polynomial $x^4+x+1$ (over $GF(2)$).
So if $alpha$ is a zero of $p(x)$ you can do the usual reduction business, and show that the elements $alpha^i, i=0,1,ldots,14$, are the non-zero elements of $GF(16)$,
and $alpha^{15}=1$:
$$
begin{aligned}
alpha^2&=alpha+beta,\
alpha^3&=alpha^2+betaalpha=(1+beta)alpha+beta,\
alpha^4&=(1+beta)alpha^2+betaalpha=(1+beta+beta)alpha+(1+beta)beta=alpha+1,\
end{aligned}
$$
et cetera. All those powers of $alpha$ can be written in the form $c_1alpha+c_0$
where $c_0,c_1$ are elements of $GF(4)$. Feel free to continue that list.
If we revert to the $0,1,2,3$ notation of elements of $GF(4)$, the above calculation presents $alpha^2$ as $alpha+2$, $alpha^3$ as $3alpha+2$ and
$alpha^4$ as $alpha+1$. The last point proving that $alpha$ is a zero of the primitive polynomial $x^4+x+1$ over $GF(2)$.
answered Jan 28 at 5:50
Jyrki LahtonenJyrki Lahtonen
110k13171387
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3090351%2ffind-the-elements-of-the-extension-field-using-primitive-polynomial-over-gf4%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You seem confused about what $GF(4)$ is: it's not $mathbb{Z}/(4)$ (which is not even a field). You can represent $GF(4)$ as an extension of $GF(2)=mathbb{Z}/(2)$ by an element $beta$ such that $beta^2=beta+1$. You can identify $GF(4)$ with the set ${0,1,2,3}$ by mapping $beta$ to $2$ and $beta+1$ to $3$, which appears to be what the book you refer to has in mind, but this does not mean you are working mod $4$ (the addition and multiplication operations are not ordinary mod $4$ addition and multiplication on ${0,1,2,3}$).
In particular, $1+1=0$ in $GF(4)$ and so $alpha+2$ and $-alpha-2$ are the same thing, and so you have $alpha^2=alpha+2$.
answered Jan 28 at 2:45
Eric WofseyEric Wofsey
191k14216349
$endgroup$
$begingroup$
You are correct about the confusion between $GF(4)$ and $Bbb{Z}/(4)$. Yet, I'm sure the OP got their primitive polynomial from some source. See my answer for an explanation.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:51
$begingroup$
And +1 for including the interpretation $beta=2$, $beta+1=3$. I missed that in my first reading.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:15
add a comment |
$begingroup$
You seem confused about what $GF(4)$ is: it's not $mathbb{Z}/(4)$ (which is not even a field). You can represent $GF(4)$ as an extension of $GF(2)=mathbb{Z}/(2)$ by an element $beta$ such that $beta^2=beta+1$. You can identify $GF(4)$ with the set ${0,1,2,3}$ by mapping $beta$ to $2$ and $beta+1$ to $3$, which appears to be what the book you refer to has in mind, but this does not mean you are working mod $4$ (the addition and multiplication operations are not ordinary mod $4$ addition and multiplication on ${0,1,2,3}$).
In particular, $1+1=0$ in $GF(4)$ and so $alpha+2$ and $-alpha-2$ are the same thing, and so you have $alpha^2=alpha+2$.
answered Jan 28 at 2:45
Eric WofseyEric Wofsey
191k14216349
$endgroup$
$begingroup$
You are correct about the confusion between $GF(4)$ and $Bbb{Z}/(4)$. Yet, I'm sure the OP got their primitive polynomial from some source. See my answer for an explanation.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:51
$begingroup$
And +1 for including the interpretation $beta=2$, $beta+1=3$. I missed that in my first reading.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:15
add a comment |
$begingroup$
You seem confused about what $GF(4)$ is: it's not $mathbb{Z}/(4)$ (which is not even a field). You can represent $GF(4)$ as an extension of $GF(2)=mathbb{Z}/(2)$ by an element $beta$ such that $beta^2=beta+1$. You can identify $GF(4)$ with the set ${0,1,2,3}$ by mapping $beta$ to $2$ and $beta+1$ to $3$, which appears to be what the book you refer to has in mind, but this does not mean you are working mod $4$ (the addition and multiplication operations are not ordinary mod $4$ addition and multiplication on ${0,1,2,3}$).
In particular, $1+1=0$ in $GF(4)$ and so $alpha+2$ and $-alpha-2$ are the same thing, and so you have $alpha^2=alpha+2$.
answered Jan 28 at 2:45
Eric WofseyEric Wofsey
191k14216349
$endgroup$
You seem confused about what $GF(4)$ is: it's not $mathbb{Z}/(4)$ (which is not even a field). You can represent $GF(4)$ as an extension of $GF(2)=mathbb{Z}/(2)$ by an element $beta$ such that $beta^2=beta+1$. You can identify $GF(4)$ with the set ${0,1,2,3}$ by mapping $beta$ to $2$ and $beta+1$ to $3$, which appears to be what the book you refer to has in mind, but this does not mean you are working mod $4$ (the addition and multiplication operations are not ordinary mod $4$ addition and multiplication on ${0,1,2,3}$).
In particular, $1+1=0$ in $GF(4)$ and so $alpha+2$ and $-alpha-2$ are the same thing, and so you have $alpha^2=alpha+2$.
answered Jan 28 at 2:45
Eric WofseyEric Wofsey
191k14216349
answered Jan 28 at 2:45
Eric WofseyEric Wofsey
191k14216349
answered Jan 28 at 2:45
Eric WofseyEric Wofsey
191k14216349
answered Jan 28 at 2:45
Eric WofseyEric Wofsey
191k14216349
191k14216349
$begingroup$
You are correct about the confusion between $GF(4)$ and $Bbb{Z}/(4)$. Yet, I'm sure the OP got their primitive polynomial from some source. See my answer for an explanation.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:51
$begingroup$
And +1 for including the interpretation $beta=2$, $beta+1=3$. I missed that in my first reading.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:15
add a comment |
$begingroup$
You are correct about the confusion between $GF(4)$ and $Bbb{Z}/(4)$. Yet, I'm sure the OP got their primitive polynomial from some source. See my answer for an explanation.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:51
$begingroup$
And +1 for including the interpretation $beta=2$, $beta+1=3$. I missed that in my first reading.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:15
$begingroup$
You are correct about the confusion between $GF(4)$ and $Bbb{Z}/(4)$. Yet, I'm sure the OP got their primitive polynomial from some source. See my answer for an explanation.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:51
$begingroup$
You are correct about the confusion between $GF(4)$ and $Bbb{Z}/(4)$. Yet, I'm sure the OP got their primitive polynomial from some source. See my answer for an explanation.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:51
$begingroup$
And +1 for including the interpretation $beta=2$, $beta+1=3$. I missed that in my first reading.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:15
$begingroup$
And +1 for including the interpretation $beta=2$, $beta+1=3$. I missed that in my first reading.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:15
add a comment |
$begingroup$
Here is an educated guess. You are confused by the difference between algebraic/arithmetic and computers representation of elements of $GF(4)$.
The field
$$GF(4)={0,1,beta,beta+1},$$
where the arithmetic comes from the rules $1+1=beta+beta=0$, $beta^2=beta+1$. The element $beta$ (it could be denoted by something else if you wish) has no integer naturally associated with it.
However, in computer implementations we (including code written by yours truly worth a couple hundred CPU hours) we write the elements of $GF(4)$ as string of two bits:
$$0=00_2,quad 1=01_2,quad beta=10_2,quad beta+1=11_2.$$
Do you see the idea? The element $b_0+b_1beta$ is represented as the bitstring $b_1b_0$. Similarly we represent elements of $GF(2^m)$ as strings of $m$ bits. A big advantage of this is that addition in the field $GF(2^m)$ then becomes bitwise XOR of those bitstrings. Most (all?) computer hardwares have a superfast built-in function for performing bitwise XOR of two registers. So that's one of the basic arithmetic operations handed to us on a silver platter. Too good to pass up! The programmer only needs to worry about implementing the multiplication of $GF(2^m)$.
For smallish values of $m$ there are efficient ways of doing that (Caveat: there are other ways
of implementing e.g. $GF(4^2)$ even more efficiently for devices really short of memory).
Anyway, having fixed an internal presentation of elements of $GF(2^m)$, programmers
occasionally refer to them as integers represented by the same string of bits.
Because the integer $2$ is $10_2$ in binary, such a programmer may choose to refer to
$beta$ as $2$ and $beta+1$ as $11_2=3$. But they know that this is safe only among people in the know. If you do this in a general math forum, you are bound to confuse people. If you are a student still learning about this, you are bound to become confused by program documentation unless you first study this difference between algebraic notation and data representation internal to a computer.
So you may think of $GF(4)$ as the set ${0,1,2,3}$, but then you must include rules like $1+1=0$, $2+2=0$, $3=2+1$ in the definition of your addition.
And, you also need to make rules like $2*2=3$, $2*3=1$ a part of your definition of multiplication. If you don't know this, you will be confused, and your questions will confuse others.
The above is all standard, but I claimed to have AN EDUCATED GUESS. Here it is.
If we present $beta=2$ internally, then the quadratic
$$
p(x)=x^2+x+beta "=" x^2+x+2
$$
is a primitive polynomial. It takes a bit of experience to see this at a glance.
But, see the last part of my linked answer (prepared with referrals like this in mind). You see that I explain there why $x^2+x+beta$ is the minimal polynomial (over $GF(4)$) of some of the zeros of the well known primitive polynomial $x^4+x+1$ (over $GF(2)$).
So if $alpha$ is a zero of $p(x)$ you can do the usual reduction business, and show that the elements $alpha^i, i=0,1,ldots,14$, are the non-zero elements of $GF(16)$,
and $alpha^{15}=1$:
$$
begin{aligned}
alpha^2&=alpha+beta,\
alpha^3&=alpha^2+betaalpha=(1+beta)alpha+beta,\
alpha^4&=(1+beta)alpha^2+betaalpha=(1+beta+beta)alpha+(1+beta)beta=alpha+1,\
end{aligned}
$$
et cetera. All those powers of $alpha$ can be written in the form $c_1alpha+c_0$
where $c_0,c_1$ are elements of $GF(4)$. Feel free to continue that list.
If we revert to the $0,1,2,3$ notation of elements of $GF(4)$, the above calculation presents $alpha^2$ as $alpha+2$, $alpha^3$ as $3alpha+2$ and
$alpha^4$ as $alpha+1$. The last point proving that $alpha$ is a zero of the primitive polynomial $x^4+x+1$ over $GF(2)$.
answered Jan 28 at 5:50
Jyrki LahtonenJyrki Lahtonen
110k13171387
$endgroup$
add a comment |
$begingroup$
Here is an educated guess. You are confused by the difference between algebraic/arithmetic and computers representation of elements of $GF(4)$.
The field
$$GF(4)={0,1,beta,beta+1},$$
where the arithmetic comes from the rules $1+1=beta+beta=0$, $beta^2=beta+1$. The element $beta$ (it could be denoted by something else if you wish) has no integer naturally associated with it.
However, in computer implementations we (including code written by yours truly worth a couple hundred CPU hours) we write the elements of $GF(4)$ as string of two bits:
$$0=00_2,quad 1=01_2,quad beta=10_2,quad beta+1=11_2.$$
Do you see the idea? The element $b_0+b_1beta$ is represented as the bitstring $b_1b_0$. Similarly we represent elements of $GF(2^m)$ as strings of $m$ bits. A big advantage of this is that addition in the field $GF(2^m)$ then becomes bitwise XOR of those bitstrings. Most (all?) computer hardwares have a superfast built-in function for performing bitwise XOR of two registers. So that's one of the basic arithmetic operations handed to us on a silver platter. Too good to pass up! The programmer only needs to worry about implementing the multiplication of $GF(2^m)$.
For smallish values of $m$ there are efficient ways of doing that (Caveat: there are other ways
of implementing e.g. $GF(4^2)$ even more efficiently for devices really short of memory).
Anyway, having fixed an internal presentation of elements of $GF(2^m)$, programmers
occasionally refer to them as integers represented by the same string of bits.
Because the integer $2$ is $10_2$ in binary, such a programmer may choose to refer to
$beta$ as $2$ and $beta+1$ as $11_2=3$. But they know that this is safe only among people in the know. If you do this in a general math forum, you are bound to confuse people. If you are a student still learning about this, you are bound to become confused by program documentation unless you first study this difference between algebraic notation and data representation internal to a computer.
So you may think of $GF(4)$ as the set ${0,1,2,3}$, but then you must include rules like $1+1=0$, $2+2=0$, $3=2+1$ in the definition of your addition.
And, you also need to make rules like $2*2=3$, $2*3=1$ a part of your definition of multiplication. If you don't know this, you will be confused, and your questions will confuse others.
The above is all standard, but I claimed to have AN EDUCATED GUESS. Here it is.
If we present $beta=2$ internally, then the quadratic
$$
p(x)=x^2+x+beta "=" x^2+x+2
$$
is a primitive polynomial. It takes a bit of experience to see this at a glance.
But, see the last part of my linked answer (prepared with referrals like this in mind). You see that I explain there why $x^2+x+beta$ is the minimal polynomial (over $GF(4)$) of some of the zeros of the well known primitive polynomial $x^4+x+1$ (over $GF(2)$).
So if $alpha$ is a zero of $p(x)$ you can do the usual reduction business, and show that the elements $alpha^i, i=0,1,ldots,14$, are the non-zero elements of $GF(16)$,
and $alpha^{15}=1$:
$$
begin{aligned}
alpha^2&=alpha+beta,\
alpha^3&=alpha^2+betaalpha=(1+beta)alpha+beta,\
alpha^4&=(1+beta)alpha^2+betaalpha=(1+beta+beta)alpha+(1+beta)beta=alpha+1,\
end{aligned}
$$
et cetera. All those powers of $alpha$ can be written in the form $c_1alpha+c_0$
where $c_0,c_1$ are elements of $GF(4)$. Feel free to continue that list.
If we revert to the $0,1,2,3$ notation of elements of $GF(4)$, the above calculation presents $alpha^2$ as $alpha+2$, $alpha^3$ as $3alpha+2$ and
$alpha^4$ as $alpha+1$. The last point proving that $alpha$ is a zero of the primitive polynomial $x^4+x+1$ over $GF(2)$.
answered Jan 28 at 5:50
Jyrki LahtonenJyrki Lahtonen
110k13171387
$endgroup$
add a comment |
$begingroup$
Here is an educated guess. You are confused by the difference between algebraic/arithmetic and computers representation of elements of $GF(4)$.
The field
$$GF(4)={0,1,beta,beta+1},$$
where the arithmetic comes from the rules $1+1=beta+beta=0$, $beta^2=beta+1$. The element $beta$ (it could be denoted by something else if you wish) has no integer naturally associated with it.
However, in computer implementations we (including code written by yours truly worth a couple hundred CPU hours) we write the elements of $GF(4)$ as string of two bits:
$$0=00_2,quad 1=01_2,quad beta=10_2,quad beta+1=11_2.$$
Do you see the idea? The element $b_0+b_1beta$ is represented as the bitstring $b_1b_0$. Similarly we represent elements of $GF(2^m)$ as strings of $m$ bits. A big advantage of this is that addition in the field $GF(2^m)$ then becomes bitwise XOR of those bitstrings. Most (all?) computer hardwares have a superfast built-in function for performing bitwise XOR of two registers. So that's one of the basic arithmetic operations handed to us on a silver platter. Too good to pass up! The programmer only needs to worry about implementing the multiplication of $GF(2^m)$.
For smallish values of $m$ there are efficient ways of doing that (Caveat: there are other ways
of implementing e.g. $GF(4^2)$ even more efficiently for devices really short of memory).
Anyway, having fixed an internal presentation of elements of $GF(2^m)$, programmers
occasionally refer to them as integers represented by the same string of bits.
Because the integer $2$ is $10_2$ in binary, such a programmer may choose to refer to
$beta$ as $2$ and $beta+1$ as $11_2=3$. But they know that this is safe only among people in the know. If you do this in a general math forum, you are bound to confuse people. If you are a student still learning about this, you are bound to become confused by program documentation unless you first study this difference between algebraic notation and data representation internal to a computer.
So you may think of $GF(4)$ as the set ${0,1,2,3}$, but then you must include rules like $1+1=0$, $2+2=0$, $3=2+1$ in the definition of your addition.
And, you also need to make rules like $2*2=3$, $2*3=1$ a part of your definition of multiplication. If you don't know this, you will be confused, and your questions will confuse others.
The above is all standard, but I claimed to have AN EDUCATED GUESS. Here it is.
If we present $beta=2$ internally, then the quadratic
$$
p(x)=x^2+x+beta "=" x^2+x+2
$$
is a primitive polynomial. It takes a bit of experience to see this at a glance.
But, see the last part of my linked answer (prepared with referrals like this in mind). You see that I explain there why $x^2+x+beta$ is the minimal polynomial (over $GF(4)$) of some of the zeros of the well known primitive polynomial $x^4+x+1$ (over $GF(2)$).
So if $alpha$ is a zero of $p(x)$ you can do the usual reduction business, and show that the elements $alpha^i, i=0,1,ldots,14$, are the non-zero elements of $GF(16)$,
and $alpha^{15}=1$:
$$
begin{aligned}
alpha^2&=alpha+beta,\
alpha^3&=alpha^2+betaalpha=(1+beta)alpha+beta,\
alpha^4&=(1+beta)alpha^2+betaalpha=(1+beta+beta)alpha+(1+beta)beta=alpha+1,\
end{aligned}
$$
et cetera. All those powers of $alpha$ can be written in the form $c_1alpha+c_0$
where $c_0,c_1$ are elements of $GF(4)$. Feel free to continue that list.
If we revert to the $0,1,2,3$ notation of elements of $GF(4)$, the above calculation presents $alpha^2$ as $alpha+2$, $alpha^3$ as $3alpha+2$ and
$alpha^4$ as $alpha+1$. The last point proving that $alpha$ is a zero of the primitive polynomial $x^4+x+1$ over $GF(2)$.
answered Jan 28 at 5:50
Jyrki LahtonenJyrki Lahtonen
110k13171387
$endgroup$
Here is an educated guess. You are confused by the difference between algebraic/arithmetic and computers representation of elements of $GF(4)$.
The field
$$GF(4)={0,1,beta,beta+1},$$
where the arithmetic comes from the rules $1+1=beta+beta=0$, $beta^2=beta+1$. The element $beta$ (it could be denoted by something else if you wish) has no integer naturally associated with it.
However, in computer implementations we (including code written by yours truly worth a couple hundred CPU hours) we write the elements of $GF(4)$ as string of two bits:
$$0=00_2,quad 1=01_2,quad beta=10_2,quad beta+1=11_2.$$
Do you see the idea? The element $b_0+b_1beta$ is represented as the bitstring $b_1b_0$. Similarly we represent elements of $GF(2^m)$ as strings of $m$ bits. A big advantage of this is that addition in the field $GF(2^m)$ then becomes bitwise XOR of those bitstrings. Most (all?) computer hardwares have a superfast built-in function for performing bitwise XOR of two registers. So that's one of the basic arithmetic operations handed to us on a silver platter. Too good to pass up! The programmer only needs to worry about implementing the multiplication of $GF(2^m)$.
For smallish values of $m$ there are efficient ways of doing that (Caveat: there are other ways
of implementing e.g. $GF(4^2)$ even more efficiently for devices really short of memory).
Anyway, having fixed an internal presentation of elements of $GF(2^m)$, programmers
occasionally refer to them as integers represented by the same string of bits.
Because the integer $2$ is $10_2$ in binary, such a programmer may choose to refer to
$beta$ as $2$ and $beta+1$ as $11_2=3$. But they know that this is safe only among people in the know. If you do this in a general math forum, you are bound to confuse people. If you are a student still learning about this, you are bound to become confused by program documentation unless you first study this difference between algebraic notation and data representation internal to a computer.
So you may think of $GF(4)$ as the set ${0,1,2,3}$, but then you must include rules like $1+1=0$, $2+2=0$, $3=2+1$ in the definition of your addition.
And, you also need to make rules like $2*2=3$, $2*3=1$ a part of your definition of multiplication. If you don't know this, you will be confused, and your questions will confuse others.
The above is all standard, but I claimed to have AN EDUCATED GUESS. Here it is.
If we present $beta=2$ internally, then the quadratic
$$
p(x)=x^2+x+beta "=" x^2+x+2
$$
is a primitive polynomial. It takes a bit of experience to see this at a glance.
But, see the last part of my linked answer (prepared with referrals like this in mind). You see that I explain there why $x^2+x+beta$ is the minimal polynomial (over $GF(4)$) of some of the zeros of the well known primitive polynomial $x^4+x+1$ (over $GF(2)$).
So if $alpha$ is a zero of $p(x)$ you can do the usual reduction business, and show that the elements $alpha^i, i=0,1,ldots,14$, are the non-zero elements of $GF(16)$,
and $alpha^{15}=1$:
$$
begin{aligned}
alpha^2&=alpha+beta,\
alpha^3&=alpha^2+betaalpha=(1+beta)alpha+beta,\
alpha^4&=(1+beta)alpha^2+betaalpha=(1+beta+beta)alpha+(1+beta)beta=alpha+1,\
end{aligned}
$$
et cetera. All those powers of $alpha$ can be written in the form $c_1alpha+c_0$
where $c_0,c_1$ are elements of $GF(4)$. Feel free to continue that list.
If we revert to the $0,1,2,3$ notation of elements of $GF(4)$, the above calculation presents $alpha^2$ as $alpha+2$, $alpha^3$ as $3alpha+2$ and
$alpha^4$ as $alpha+1$. The last point proving that $alpha$ is a zero of the primitive polynomial $x^4+x+1$ over $GF(2)$.
answered Jan 28 at 5:50
Jyrki LahtonenJyrki Lahtonen
110k13171387
edited Jan 28 at 6:13
answered Jan 28 at 5:50
Jyrki LahtonenJyrki Lahtonen
110k13171387
answered Jan 28 at 5:50
Jyrki LahtonenJyrki Lahtonen
110k13171387
answered Jan 28 at 5:50
Jyrki LahtonenJyrki Lahtonen
110k13171387
110k13171387
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3090351%2ffind-the-elements-of-the-extension-field-using-primitive-polynomial-over-gf4%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
$GF(4)$ is not the same as $mathbb{Z}/(4)$; it's a degree $2$ extension of $mathbb{Z}/(2)$. So over $GF(4)$, $z^2+z+2=z^2+z$ is not even irreducible.
$endgroup$
– Eric Wofsey
Jan 28 at 1:59
$begingroup$
@EricWofsey I want the coefficients to be one of the these values ${0,1,2,3}$. I need this for BCH codes where the coefficients are not only binary.
$endgroup$
– Khan Saab
Jan 28 at 2:06
$begingroup$
Khan Saab, see my answer for an explanation as to how $p(z)$ becomes a primitive polynomial. When we interpret the coefficient $2$ as a zero of $x^2+x+1$ in the field $GF(4)$, then $z^2+z+2$ is irreducible and also primitive. You need to adjust your meaning of $2$ for all this to make sense. Starting from $1+1neq2$.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 5:52
$begingroup$
Eric Wofsey did explain the relevant bits in his answer. I simply elaborated.
$endgroup$
– Jyrki Lahtonen
Jan 28 at 6:30