Multiplicative inverse of a polynomial in $GF(8)$
up vote
0
down vote
favorite
I am trying to find the inverse of $x ^3+x +1$ in $GF(8)$.
I have done the Euclidean algorithm but I am stuck in the forward process to get the inverse. Please explain how to do it from reverse.
number-theory galois-theory finite-fields cryptography
asked Nov 15 at 0:22
Mariam Mashuryan
13
|
show 3 more comments
up vote
0
down vote
favorite
I am trying to find the inverse of $x ^3+x +1$ in $GF(8)$.
I have done the Euclidean algorithm but I am stuck in the forward process to get the inverse. Please explain how to do it from reverse.
number-theory galois-theory finite-fields cryptography
asked Nov 15 at 0:22
Mariam Mashuryan
13
Do it this way - much less painful and less error-prone.
– Bill Dubuque
Nov 15 at 0:25
Normally $x$ stands for an indeterminate, when $x^3+x+1$ is a polynomial. Polynomials don't have inverses in a finite field. If, as I suspect, $x$ stands for some element of $GF(8)$ you need to tell us which element. Or at least, tell us its minimal polynomial. You see, very often the field $GF(8)$ is defined as the quotient ring $GF(2)[x]/langle x^3+x+1rangle$. But, in that field the coset of $x^3+x+1$ is equal to zero. Again implying that it has no inverse (can't divide by zero).
– Jyrki Lahtonen
Nov 15 at 4:14
The (only) other alternative is to have defined $GF(8)$ as the quotien $GF(2)[x]/langle x^3+x^2+1rangle$. In that case the coset of $x^3+x+1$ equals the coset of $x^2+x$ (because $(x^3+x+1)-(x^3+x^2+1)=x^2+x$). You can find the inverse of that by the usual process involving extended Euclid. You see, to positively id an element of the quotient ring we customarily reduce them by the polynomial defining the field.
– Jyrki Lahtonen
Nov 15 at 4:17
1
But, Mariam, the polynomial $x^8+x^4+x^3+x+1$ defines the version of the field $GF(2^8)=GF(256)=GF(2)[x]/langle x^8+x^4+x^3+x+1rangle$ IIRC used in AES cryptosystem (among other things).
– Jyrki Lahtonen
Nov 15 at 20:10
1
Here I spell out what $GF(8)$, also known as $Bbb{F}_8$, looks like. If I were to use $GF(256)$ in a computer program I would build a similar logarithm table for $GF(256)$ and use it calculate inverses.
– Jyrki Lahtonen
Nov 15 at 20:15
|
show 3 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am trying to find the inverse of $x ^3+x +1$ in $GF(8)$.
I have done the Euclidean algorithm but I am stuck in the forward process to get the inverse. Please explain how to do it from reverse.
number-theory galois-theory finite-fields cryptography
asked Nov 15 at 0:22
Mariam Mashuryan
13
I am trying to find the inverse of $x ^3+x +1$ in $GF(8)$.
I have done the Euclidean algorithm but I am stuck in the forward process to get the inverse. Please explain how to do it from reverse.
number-theory galois-theory finite-fields cryptography
number-theory galois-theory finite-fields cryptography
asked Nov 15 at 0:22
Mariam Mashuryan
13
asked Nov 15 at 0:22
Mariam Mashuryan
13
edited Nov 15 at 8:59
asked Nov 15 at 0:22
Mariam Mashuryan
13
asked Nov 15 at 0:22
Mariam Mashuryan
13
asked Nov 15 at 0:22
Mariam Mashuryan
13
13
Do it this way - much less painful and less error-prone.
– Bill Dubuque
Nov 15 at 0:25
Normally $x$ stands for an indeterminate, when $x^3+x+1$ is a polynomial. Polynomials don't have inverses in a finite field. If, as I suspect, $x$ stands for some element of $GF(8)$ you need to tell us which element. Or at least, tell us its minimal polynomial. You see, very often the field $GF(8)$ is defined as the quotient ring $GF(2)[x]/langle x^3+x+1rangle$. But, in that field the coset of $x^3+x+1$ is equal to zero. Again implying that it has no inverse (can't divide by zero).
– Jyrki Lahtonen
Nov 15 at 4:14
The (only) other alternative is to have defined $GF(8)$ as the quotien $GF(2)[x]/langle x^3+x^2+1rangle$. In that case the coset of $x^3+x+1$ equals the coset of $x^2+x$ (because $(x^3+x+1)-(x^3+x^2+1)=x^2+x$). You can find the inverse of that by the usual process involving extended Euclid. You see, to positively id an element of the quotient ring we customarily reduce them by the polynomial defining the field.
– Jyrki Lahtonen
Nov 15 at 4:17
1
But, Mariam, the polynomial $x^8+x^4+x^3+x+1$ defines the version of the field $GF(2^8)=GF(256)=GF(2)[x]/langle x^8+x^4+x^3+x+1rangle$ IIRC used in AES cryptosystem (among other things).
– Jyrki Lahtonen
Nov 15 at 20:10
1
Here I spell out what $GF(8)$, also known as $Bbb{F}_8$, looks like. If I were to use $GF(256)$ in a computer program I would build a similar logarithm table for $GF(256)$ and use it calculate inverses.
– Jyrki Lahtonen
Nov 15 at 20:15
|
show 3 more comments
Do it this way - much less painful and less error-prone.
– Bill Dubuque
Nov 15 at 0:25
Normally $x$ stands for an indeterminate, when $x^3+x+1$ is a polynomial. Polynomials don't have inverses in a finite field. If, as I suspect, $x$ stands for some element of $GF(8)$ you need to tell us which element. Or at least, tell us its minimal polynomial. You see, very often the field $GF(8)$ is defined as the quotient ring $GF(2)[x]/langle x^3+x+1rangle$. But, in that field the coset of $x^3+x+1$ is equal to zero. Again implying that it has no inverse (can't divide by zero).
– Jyrki Lahtonen
Nov 15 at 4:14
The (only) other alternative is to have defined $GF(8)$ as the quotien $GF(2)[x]/langle x^3+x^2+1rangle$. In that case the coset of $x^3+x+1$ equals the coset of $x^2+x$ (because $(x^3+x+1)-(x^3+x^2+1)=x^2+x$). You can find the inverse of that by the usual process involving extended Euclid. You see, to positively id an element of the quotient ring we customarily reduce them by the polynomial defining the field.
– Jyrki Lahtonen
Nov 15 at 4:17
1
But, Mariam, the polynomial $x^8+x^4+x^3+x+1$ defines the version of the field $GF(2^8)=GF(256)=GF(2)[x]/langle x^8+x^4+x^3+x+1rangle$ IIRC used in AES cryptosystem (among other things).
– Jyrki Lahtonen
Nov 15 at 20:10
1
Here I spell out what $GF(8)$, also known as $Bbb{F}_8$, looks like. If I were to use $GF(256)$ in a computer program I would build a similar logarithm table for $GF(256)$ and use it calculate inverses.
– Jyrki Lahtonen
Nov 15 at 20:15
Do it this way - much less painful and less error-prone.
– Bill Dubuque
Nov 15 at 0:25
Do it this way - much less painful and less error-prone.
– Bill Dubuque
Nov 15 at 0:25
Normally $x$ stands for an indeterminate, when $x^3+x+1$ is a polynomial. Polynomials don't have inverses in a finite field. If, as I suspect, $x$ stands for some element of $GF(8)$ you need to tell us which element. Or at least, tell us its minimal polynomial. You see, very often the field $GF(8)$ is defined as the quotient ring $GF(2)[x]/langle x^3+x+1rangle$. But, in that field the coset of $x^3+x+1$ is equal to zero. Again implying that it has no inverse (can't divide by zero).
– Jyrki Lahtonen
Nov 15 at 4:14
Normally $x$ stands for an indeterminate, when $x^3+x+1$ is a polynomial. Polynomials don't have inverses in a finite field. If, as I suspect, $x$ stands for some element of $GF(8)$ you need to tell us which element. Or at least, tell us its minimal polynomial. You see, very often the field $GF(8)$ is defined as the quotient ring $GF(2)[x]/langle x^3+x+1rangle$. But, in that field the coset of $x^3+x+1$ is equal to zero. Again implying that it has no inverse (can't divide by zero).
– Jyrki Lahtonen
Nov 15 at 4:14
The (only) other alternative is to have defined $GF(8)$ as the quotien $GF(2)[x]/langle x^3+x^2+1rangle$. In that case the coset of $x^3+x+1$ equals the coset of $x^2+x$ (because $(x^3+x+1)-(x^3+x^2+1)=x^2+x$). You can find the inverse of that by the usual process involving extended Euclid. You see, to positively id an element of the quotient ring we customarily reduce them by the polynomial defining the field.
– Jyrki Lahtonen
Nov 15 at 4:17
The (only) other alternative is to have defined $GF(8)$ as the quotien $GF(2)[x]/langle x^3+x^2+1rangle$. In that case the coset of $x^3+x+1$ equals the coset of $x^2+x$ (because $(x^3+x+1)-(x^3+x^2+1)=x^2+x$). You can find the inverse of that by the usual process involving extended Euclid. You see, to positively id an element of the quotient ring we customarily reduce them by the polynomial defining the field.
– Jyrki Lahtonen
Nov 15 at 4:17
1
1
But, Mariam, the polynomial $x^8+x^4+x^3+x+1$ defines the version of the field $GF(2^8)=GF(256)=GF(2)[x]/langle x^8+x^4+x^3+x+1rangle$ IIRC used in AES cryptosystem (among other things).
– Jyrki Lahtonen
Nov 15 at 20:10
But, Mariam, the polynomial $x^8+x^4+x^3+x+1$ defines the version of the field $GF(2^8)=GF(256)=GF(2)[x]/langle x^8+x^4+x^3+x+1rangle$ IIRC used in AES cryptosystem (among other things).
– Jyrki Lahtonen
Nov 15 at 20:10
1
1
Here I spell out what $GF(8)$, also known as $Bbb{F}_8$, looks like. If I were to use $GF(256)$ in a computer program I would build a similar logarithm table for $GF(256)$ and use it calculate inverses.
– Jyrki Lahtonen
Nov 15 at 20:15
Here I spell out what $GF(8)$, also known as $Bbb{F}_8$, looks like. If I were to use $GF(256)$ in a computer program I would build a similar logarithm table for $GF(256)$ and use it calculate inverses.
– Jyrki Lahtonen
Nov 15 at 20:15
|
show 3 more comments
1 Answer
1
active
oldest
votes
up vote
0
down vote
Hint: The field $GF(8)$ is isomorphic to $GF(2)[x]/langle x^3+x+1rangle$ or to $GF(2)[x]/langle x^3+x^2+1rangle$. The polynomials $x^3+x+1$ and $x^3+x^2+1$ are the only irreducible polynomials over $GF(2)$ (and they are conjugate).
The elements of $GF(8)$ are the residue classes of the polynomials $ax^2+bx+c$, where $a,b,cin GF(2)$. So maybe you should rethink about your question.
answered Nov 23 at 21:44
Wuestenfux
2,6621410
What do you mean by those polynomials being conjugate?
– Tobias Kildetoft
Nov 23 at 21:50
1
The comment thread under the question sounds a lot like the OP didn't actually mean $GF(8)$ but $GF(2^8)$, represented using the primitive polynomial $x^8+x^4+x^3+x+1$.
– Henning Makholm
Nov 23 at 21:51
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Hint: The field $GF(8)$ is isomorphic to $GF(2)[x]/langle x^3+x+1rangle$ or to $GF(2)[x]/langle x^3+x^2+1rangle$. The polynomials $x^3+x+1$ and $x^3+x^2+1$ are the only irreducible polynomials over $GF(2)$ (and they are conjugate).
The elements of $GF(8)$ are the residue classes of the polynomials $ax^2+bx+c$, where $a,b,cin GF(2)$. So maybe you should rethink about your question.
answered Nov 23 at 21:44
Wuestenfux
2,6621410
What do you mean by those polynomials being conjugate?
– Tobias Kildetoft
Nov 23 at 21:50
1
The comment thread under the question sounds a lot like the OP didn't actually mean $GF(8)$ but $GF(2^8)$, represented using the primitive polynomial $x^8+x^4+x^3+x+1$.
– Henning Makholm
Nov 23 at 21:51
add a comment |
up vote
0
down vote
Hint: The field $GF(8)$ is isomorphic to $GF(2)[x]/langle x^3+x+1rangle$ or to $GF(2)[x]/langle x^3+x^2+1rangle$. The polynomials $x^3+x+1$ and $x^3+x^2+1$ are the only irreducible polynomials over $GF(2)$ (and they are conjugate).
The elements of $GF(8)$ are the residue classes of the polynomials $ax^2+bx+c$, where $a,b,cin GF(2)$. So maybe you should rethink about your question.
answered Nov 23 at 21:44
Wuestenfux
2,6621410
What do you mean by those polynomials being conjugate?
– Tobias Kildetoft
Nov 23 at 21:50
1
The comment thread under the question sounds a lot like the OP didn't actually mean $GF(8)$ but $GF(2^8)$, represented using the primitive polynomial $x^8+x^4+x^3+x+1$.
– Henning Makholm
Nov 23 at 21:51
add a comment |
up vote
0
down vote
up vote
0
down vote
Hint: The field $GF(8)$ is isomorphic to $GF(2)[x]/langle x^3+x+1rangle$ or to $GF(2)[x]/langle x^3+x^2+1rangle$. The polynomials $x^3+x+1$ and $x^3+x^2+1$ are the only irreducible polynomials over $GF(2)$ (and they are conjugate).
The elements of $GF(8)$ are the residue classes of the polynomials $ax^2+bx+c$, where $a,b,cin GF(2)$. So maybe you should rethink about your question.
answered Nov 23 at 21:44
Wuestenfux
2,6621410
Hint: The field $GF(8)$ is isomorphic to $GF(2)[x]/langle x^3+x+1rangle$ or to $GF(2)[x]/langle x^3+x^2+1rangle$. The polynomials $x^3+x+1$ and $x^3+x^2+1$ are the only irreducible polynomials over $GF(2)$ (and they are conjugate).
The elements of $GF(8)$ are the residue classes of the polynomials $ax^2+bx+c$, where $a,b,cin GF(2)$. So maybe you should rethink about your question.
answered Nov 23 at 21:44
Wuestenfux
2,6621410
answered Nov 23 at 21:44
Wuestenfux
2,6621410
answered Nov 23 at 21:44
Wuestenfux
2,6621410
answered Nov 23 at 21:44
Wuestenfux
2,6621410
2,6621410
What do you mean by those polynomials being conjugate?
– Tobias Kildetoft
Nov 23 at 21:50
1
The comment thread under the question sounds a lot like the OP didn't actually mean $GF(8)$ but $GF(2^8)$, represented using the primitive polynomial $x^8+x^4+x^3+x+1$.
– Henning Makholm
Nov 23 at 21:51
add a comment |
What do you mean by those polynomials being conjugate?
– Tobias Kildetoft
Nov 23 at 21:50
1
The comment thread under the question sounds a lot like the OP didn't actually mean $GF(8)$ but $GF(2^8)$, represented using the primitive polynomial $x^8+x^4+x^3+x+1$.
– Henning Makholm
Nov 23 at 21:51
What do you mean by those polynomials being conjugate?
– Tobias Kildetoft
Nov 23 at 21:50
What do you mean by those polynomials being conjugate?
– Tobias Kildetoft
Nov 23 at 21:50
1
1
The comment thread under the question sounds a lot like the OP didn't actually mean $GF(8)$ but $GF(2^8)$, represented using the primitive polynomial $x^8+x^4+x^3+x+1$.
– Henning Makholm
Nov 23 at 21:51
The comment thread under the question sounds a lot like the OP didn't actually mean $GF(8)$ but $GF(2^8)$, represented using the primitive polynomial $x^8+x^4+x^3+x+1$.
– Henning Makholm
Nov 23 at 21:51
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f2999014%2fmultiplicative-inverse-of-a-polynomial-in-gf8%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
Do it this way - much less painful and less error-prone.
– Bill Dubuque
Nov 15 at 0:25
Normally $x$ stands for an indeterminate, when $x^3+x+1$ is a polynomial. Polynomials don't have inverses in a finite field. If, as I suspect, $x$ stands for some element of $GF(8)$ you need to tell us which element. Or at least, tell us its minimal polynomial. You see, very often the field $GF(8)$ is defined as the quotient ring $GF(2)[x]/langle x^3+x+1rangle$. But, in that field the coset of $x^3+x+1$ is equal to zero. Again implying that it has no inverse (can't divide by zero).
– Jyrki Lahtonen
Nov 15 at 4:14
The (only) other alternative is to have defined $GF(8)$ as the quotien $GF(2)[x]/langle x^3+x^2+1rangle$. In that case the coset of $x^3+x+1$ equals the coset of $x^2+x$ (because $(x^3+x+1)-(x^3+x^2+1)=x^2+x$). You can find the inverse of that by the usual process involving extended Euclid. You see, to positively id an element of the quotient ring we customarily reduce them by the polynomial defining the field.
– Jyrki Lahtonen
Nov 15 at 4:17
1
But, Mariam, the polynomial $x^8+x^4+x^3+x+1$ defines the version of the field $GF(2^8)=GF(256)=GF(2)[x]/langle x^8+x^4+x^3+x+1rangle$ IIRC used in AES cryptosystem (among other things).
– Jyrki Lahtonen
Nov 15 at 20:10
1
Here I spell out what $GF(8)$, also known as $Bbb{F}_8$, looks like. If I were to use $GF(256)$ in a computer program I would build a similar logarithm table for $GF(256)$ and use it calculate inverses.
– Jyrki Lahtonen
Nov 15 at 20:15