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
New contributor
|
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
New contributor
Do it this way - much less painful and less error-prone.
– Bill Dubuque
yesterday
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
21 hours ago
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
21 hours ago
By saying finite field, i mean the polynomial of the field, which is x^8+ x^4+ x^3+x+1. So i have to find the inverse of the first polynomial modulus this one
– Mariam Mashuryan
18 hours ago
What do you mean by $x^8 + x^4 + x^3 + x + 1$ being the "polynomial of the field"?
– Tobias Kildetoft
16 hours ago
|
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
New contributor
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
New contributor
New contributor
edited 16 hours ago
New contributor
asked yesterday
Mariam Mashuryan
13
13
New contributor
New contributor
Do it this way - much less painful and less error-prone.
– Bill Dubuque
yesterday
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
21 hours ago
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
21 hours ago
By saying finite field, i mean the polynomial of the field, which is x^8+ x^4+ x^3+x+1. So i have to find the inverse of the first polynomial modulus this one
– Mariam Mashuryan
18 hours ago
What do you mean by $x^8 + x^4 + x^3 + x + 1$ being the "polynomial of the field"?
– Tobias Kildetoft
16 hours ago
|
show 3 more comments
Do it this way - much less painful and less error-prone.
– Bill Dubuque
yesterday
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
21 hours ago
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
21 hours ago
By saying finite field, i mean the polynomial of the field, which is x^8+ x^4+ x^3+x+1. So i have to find the inverse of the first polynomial modulus this one
– Mariam Mashuryan
18 hours ago
What do you mean by $x^8 + x^4 + x^3 + x + 1$ being the "polynomial of the field"?
– Tobias Kildetoft
16 hours ago
Do it this way - much less painful and less error-prone.
– Bill Dubuque
yesterday
Do it this way - much less painful and less error-prone.
– Bill Dubuque
yesterday
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
21 hours ago
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
21 hours ago
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
21 hours ago
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
21 hours ago
By saying finite field, i mean the polynomial of the field, which is x^8+ x^4+ x^3+x+1. So i have to find the inverse of the first polynomial modulus this one
– Mariam Mashuryan
18 hours ago
By saying finite field, i mean the polynomial of the field, which is x^8+ x^4+ x^3+x+1. So i have to find the inverse of the first polynomial modulus this one
– Mariam Mashuryan
18 hours ago
What do you mean by $x^8 + x^4 + x^3 + x + 1$ being the "polynomial of the field"?
– Tobias Kildetoft
16 hours ago
What do you mean by $x^8 + x^4 + x^3 + x + 1$ being the "polynomial of the field"?
– Tobias Kildetoft
16 hours ago
|
show 3 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Mariam Mashuryan is a new contributor. Be nice, and check out our Code of Conduct.
Mariam Mashuryan is a new contributor. Be nice, and check out our Code of Conduct.
Mariam Mashuryan is a new contributor. Be nice, and check out our Code of Conduct.
Mariam Mashuryan is a new contributor. Be nice, and check out our Code of Conduct.
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
yesterday
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
21 hours ago
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
21 hours ago
By saying finite field, i mean the polynomial of the field, which is x^8+ x^4+ x^3+x+1. So i have to find the inverse of the first polynomial modulus this one
– Mariam Mashuryan
18 hours ago
What do you mean by $x^8 + x^4 + x^3 + x + 1$ being the "polynomial of the field"?
– Tobias Kildetoft
16 hours ago