Degrees in Monomials
$begingroup$
I am looking over the Joux-Vitse algorithm paper whereby they present an algorithm that seems to outperform exhaustive search and some state-of-the-art algorithms. However, it only works with polynomials in $B[X_0,...,X_{n-1}]$ whereby $B$ stands for boolean, meaning that we are working in $GF(2)$.
One of the steps is to calculate the total degree of a polynomial in $X_{k},...,X_{n-1}$. This is where my doubts arise.
Consider the following polynomial
$f = x_0x_4 + x_1x_4 + x_3$
whereby $n$, the number of variables = 5 and $k = 3$. This means that we want to calculate the total degree of $f$ in $x_3, x_4, x_5$.
My issue is that I am not sure whether the total degree of $f$ in these variables is equal to 3 (since $x_4$ occurs twice and $x_3$ occurs once) or whether it is 2 since the maximum degree of $x_4$ is 1 and $x_3$ is also 1.
My question boils down to: how would I count the total degree of a monomial in a specific set of variables?
Thank you for the help!
abstract-algebra polynomials commutative-algebra finite-fields
edited Dec 3 '18 at 20:41
user26857
39.3k124183
asked Dec 3 '18 at 19:04
João DuarteJoão Duarte
63
$endgroup$
add a comment |
$begingroup$
I am looking over the Joux-Vitse algorithm paper whereby they present an algorithm that seems to outperform exhaustive search and some state-of-the-art algorithms. However, it only works with polynomials in $B[X_0,...,X_{n-1}]$ whereby $B$ stands for boolean, meaning that we are working in $GF(2)$.
One of the steps is to calculate the total degree of a polynomial in $X_{k},...,X_{n-1}$. This is where my doubts arise.
Consider the following polynomial
$f = x_0x_4 + x_1x_4 + x_3$
whereby $n$, the number of variables = 5 and $k = 3$. This means that we want to calculate the total degree of $f$ in $x_3, x_4, x_5$.
My issue is that I am not sure whether the total degree of $f$ in these variables is equal to 3 (since $x_4$ occurs twice and $x_3$ occurs once) or whether it is 2 since the maximum degree of $x_4$ is 1 and $x_3$ is also 1.
My question boils down to: how would I count the total degree of a monomial in a specific set of variables?
Thank you for the help!
abstract-algebra polynomials commutative-algebra finite-fields
edited Dec 3 '18 at 20:41
user26857
39.3k124183
asked Dec 3 '18 at 19:04
João DuarteJoão Duarte
63
$endgroup$
add a comment |
$begingroup$
I am looking over the Joux-Vitse algorithm paper whereby they present an algorithm that seems to outperform exhaustive search and some state-of-the-art algorithms. However, it only works with polynomials in $B[X_0,...,X_{n-1}]$ whereby $B$ stands for boolean, meaning that we are working in $GF(2)$.
One of the steps is to calculate the total degree of a polynomial in $X_{k},...,X_{n-1}$. This is where my doubts arise.
Consider the following polynomial
$f = x_0x_4 + x_1x_4 + x_3$
whereby $n$, the number of variables = 5 and $k = 3$. This means that we want to calculate the total degree of $f$ in $x_3, x_4, x_5$.
My issue is that I am not sure whether the total degree of $f$ in these variables is equal to 3 (since $x_4$ occurs twice and $x_3$ occurs once) or whether it is 2 since the maximum degree of $x_4$ is 1 and $x_3$ is also 1.
My question boils down to: how would I count the total degree of a monomial in a specific set of variables?
Thank you for the help!
abstract-algebra polynomials commutative-algebra finite-fields
edited Dec 3 '18 at 20:41
user26857
39.3k124183
asked Dec 3 '18 at 19:04
João DuarteJoão Duarte
63
$endgroup$
I am looking over the Joux-Vitse algorithm paper whereby they present an algorithm that seems to outperform exhaustive search and some state-of-the-art algorithms. However, it only works with polynomials in $B[X_0,...,X_{n-1}]$ whereby $B$ stands for boolean, meaning that we are working in $GF(2)$.
One of the steps is to calculate the total degree of a polynomial in $X_{k},...,X_{n-1}$. This is where my doubts arise.
Consider the following polynomial
$f = x_0x_4 + x_1x_4 + x_3$
whereby $n$, the number of variables = 5 and $k = 3$. This means that we want to calculate the total degree of $f$ in $x_3, x_4, x_5$.
My issue is that I am not sure whether the total degree of $f$ in these variables is equal to 3 (since $x_4$ occurs twice and $x_3$ occurs once) or whether it is 2 since the maximum degree of $x_4$ is 1 and $x_3$ is also 1.
My question boils down to: how would I count the total degree of a monomial in a specific set of variables?
Thank you for the help!
abstract-algebra polynomials commutative-algebra finite-fields
abstract-algebra polynomials commutative-algebra finite-fields
edited Dec 3 '18 at 20:41
user26857
39.3k124183
asked Dec 3 '18 at 19:04
João DuarteJoão Duarte
63
edited Dec 3 '18 at 20:41
user26857
39.3k124183
asked Dec 3 '18 at 19:04
João DuarteJoão Duarte
63
edited Dec 3 '18 at 20:41
user26857
39.3k124183
edited Dec 3 '18 at 20:41
user26857
39.3k124183
edited Dec 3 '18 at 20:41
user26857
39.3k124183
39.3k124183
asked Dec 3 '18 at 19:04
João DuarteJoão Duarte
63
asked Dec 3 '18 at 19:04
João DuarteJoão Duarte
63
asked Dec 3 '18 at 19:04
João DuarteJoão Duarte
63
63
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The degree of the polynomial you've given in the variables you care about, $x_3,x_4,x_5$ is 1. Though the presence of $x_0$ is confusing given that you indicate variable indices start at 1 earlier.
Here's a slightly more general definition of degree for polynomials that should be helpful to you.
Given a weighting of the variables, which assigns to each variable $x_i$ a (lets say nonnegative) integer, $|x_i|$, (notation more or less unrelated to absolute values) called its weight. The degree of a monomial $prod_i x_i^{k_i}$ with respect to this weighting is $sum_i k_i|x_i|$. Then we define the degree of a polynomial with respect to this weighting to be the maximum degree of the monomials in the polynomial.
Hence in your situation, you have $|x_0|=|x_1|=|x_2|=0$ and $|x_3|=|x_4|=|x_5|=1$. Thus the degree of $x_0x_4+x_1x_4+x_3$ is
$$max {0+1,0+1,1}=1.$$
Edit
To be a bit more clear, if $S$ is a set of indices indicating variables that you care about, then you have a weighting of the variables with $|x_i|=0$ if $inotin S$ and $|x_i|=1$ if $iin S$. Then the degree of a monomial/polynomial in these variables with respect to this weighting is calculated as above.
answered Dec 3 '18 at 19:31
jgonjgon
13.5k22041
$endgroup$
$begingroup$
Hi! That makes sense, thank you very much. And yes, sorry, I meant to write $X_0$ till $X_{n-1}$.
$endgroup$
– João Duarte
Dec 3 '18 at 20:35
$begingroup$
However, this does seem weird in the context of the paper, so maybe they are looking for a different way of doing things. I'll just have to have another look
$endgroup$
– João Duarte
Dec 3 '18 at 20:41
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%2f3024518%2fdegrees-in-monomials%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The degree of the polynomial you've given in the variables you care about, $x_3,x_4,x_5$ is 1. Though the presence of $x_0$ is confusing given that you indicate variable indices start at 1 earlier.
Here's a slightly more general definition of degree for polynomials that should be helpful to you.
Given a weighting of the variables, which assigns to each variable $x_i$ a (lets say nonnegative) integer, $|x_i|$, (notation more or less unrelated to absolute values) called its weight. The degree of a monomial $prod_i x_i^{k_i}$ with respect to this weighting is $sum_i k_i|x_i|$. Then we define the degree of a polynomial with respect to this weighting to be the maximum degree of the monomials in the polynomial.
Hence in your situation, you have $|x_0|=|x_1|=|x_2|=0$ and $|x_3|=|x_4|=|x_5|=1$. Thus the degree of $x_0x_4+x_1x_4+x_3$ is
$$max {0+1,0+1,1}=1.$$
Edit
To be a bit more clear, if $S$ is a set of indices indicating variables that you care about, then you have a weighting of the variables with $|x_i|=0$ if $inotin S$ and $|x_i|=1$ if $iin S$. Then the degree of a monomial/polynomial in these variables with respect to this weighting is calculated as above.
answered Dec 3 '18 at 19:31
jgonjgon
13.5k22041
$endgroup$
$begingroup$
Hi! That makes sense, thank you very much. And yes, sorry, I meant to write $X_0$ till $X_{n-1}$.
$endgroup$
– João Duarte
Dec 3 '18 at 20:35
$begingroup$
However, this does seem weird in the context of the paper, so maybe they are looking for a different way of doing things. I'll just have to have another look
$endgroup$
– João Duarte
Dec 3 '18 at 20:41
add a comment |
$begingroup$
The degree of the polynomial you've given in the variables you care about, $x_3,x_4,x_5$ is 1. Though the presence of $x_0$ is confusing given that you indicate variable indices start at 1 earlier.
Here's a slightly more general definition of degree for polynomials that should be helpful to you.
Given a weighting of the variables, which assigns to each variable $x_i$ a (lets say nonnegative) integer, $|x_i|$, (notation more or less unrelated to absolute values) called its weight. The degree of a monomial $prod_i x_i^{k_i}$ with respect to this weighting is $sum_i k_i|x_i|$. Then we define the degree of a polynomial with respect to this weighting to be the maximum degree of the monomials in the polynomial.
Hence in your situation, you have $|x_0|=|x_1|=|x_2|=0$ and $|x_3|=|x_4|=|x_5|=1$. Thus the degree of $x_0x_4+x_1x_4+x_3$ is
$$max {0+1,0+1,1}=1.$$
Edit
To be a bit more clear, if $S$ is a set of indices indicating variables that you care about, then you have a weighting of the variables with $|x_i|=0$ if $inotin S$ and $|x_i|=1$ if $iin S$. Then the degree of a monomial/polynomial in these variables with respect to this weighting is calculated as above.
answered Dec 3 '18 at 19:31
jgonjgon
13.5k22041
$endgroup$
$begingroup$
Hi! That makes sense, thank you very much. And yes, sorry, I meant to write $X_0$ till $X_{n-1}$.
$endgroup$
– João Duarte
Dec 3 '18 at 20:35
$begingroup$
However, this does seem weird in the context of the paper, so maybe they are looking for a different way of doing things. I'll just have to have another look
$endgroup$
– João Duarte
Dec 3 '18 at 20:41
add a comment |
$begingroup$
The degree of the polynomial you've given in the variables you care about, $x_3,x_4,x_5$ is 1. Though the presence of $x_0$ is confusing given that you indicate variable indices start at 1 earlier.
Here's a slightly more general definition of degree for polynomials that should be helpful to you.
Given a weighting of the variables, which assigns to each variable $x_i$ a (lets say nonnegative) integer, $|x_i|$, (notation more or less unrelated to absolute values) called its weight. The degree of a monomial $prod_i x_i^{k_i}$ with respect to this weighting is $sum_i k_i|x_i|$. Then we define the degree of a polynomial with respect to this weighting to be the maximum degree of the monomials in the polynomial.
Hence in your situation, you have $|x_0|=|x_1|=|x_2|=0$ and $|x_3|=|x_4|=|x_5|=1$. Thus the degree of $x_0x_4+x_1x_4+x_3$ is
$$max {0+1,0+1,1}=1.$$
Edit
To be a bit more clear, if $S$ is a set of indices indicating variables that you care about, then you have a weighting of the variables with $|x_i|=0$ if $inotin S$ and $|x_i|=1$ if $iin S$. Then the degree of a monomial/polynomial in these variables with respect to this weighting is calculated as above.
answered Dec 3 '18 at 19:31
jgonjgon
13.5k22041
$endgroup$
The degree of the polynomial you've given in the variables you care about, $x_3,x_4,x_5$ is 1. Though the presence of $x_0$ is confusing given that you indicate variable indices start at 1 earlier.
Here's a slightly more general definition of degree for polynomials that should be helpful to you.
Given a weighting of the variables, which assigns to each variable $x_i$ a (lets say nonnegative) integer, $|x_i|$, (notation more or less unrelated to absolute values) called its weight. The degree of a monomial $prod_i x_i^{k_i}$ with respect to this weighting is $sum_i k_i|x_i|$. Then we define the degree of a polynomial with respect to this weighting to be the maximum degree of the monomials in the polynomial.
Hence in your situation, you have $|x_0|=|x_1|=|x_2|=0$ and $|x_3|=|x_4|=|x_5|=1$. Thus the degree of $x_0x_4+x_1x_4+x_3$ is
$$max {0+1,0+1,1}=1.$$
Edit
To be a bit more clear, if $S$ is a set of indices indicating variables that you care about, then you have a weighting of the variables with $|x_i|=0$ if $inotin S$ and $|x_i|=1$ if $iin S$. Then the degree of a monomial/polynomial in these variables with respect to this weighting is calculated as above.
answered Dec 3 '18 at 19:31
jgonjgon
13.5k22041
answered Dec 3 '18 at 19:31
jgonjgon
13.5k22041
answered Dec 3 '18 at 19:31
jgonjgon
13.5k22041
answered Dec 3 '18 at 19:31
jgonjgon
13.5k22041
13.5k22041
$begingroup$
Hi! That makes sense, thank you very much. And yes, sorry, I meant to write $X_0$ till $X_{n-1}$.
$endgroup$
– João Duarte
Dec 3 '18 at 20:35
$begingroup$
However, this does seem weird in the context of the paper, so maybe they are looking for a different way of doing things. I'll just have to have another look
$endgroup$
– João Duarte
Dec 3 '18 at 20:41
add a comment |
$begingroup$
Hi! That makes sense, thank you very much. And yes, sorry, I meant to write $X_0$ till $X_{n-1}$.
$endgroup$
– João Duarte
Dec 3 '18 at 20:35
$begingroup$
However, this does seem weird in the context of the paper, so maybe they are looking for a different way of doing things. I'll just have to have another look
$endgroup$
– João Duarte
Dec 3 '18 at 20:41
$begingroup$
Hi! That makes sense, thank you very much. And yes, sorry, I meant to write $X_0$ till $X_{n-1}$.
$endgroup$
– João Duarte
Dec 3 '18 at 20:35
$begingroup$
Hi! That makes sense, thank you very much. And yes, sorry, I meant to write $X_0$ till $X_{n-1}$.
$endgroup$
– João Duarte
Dec 3 '18 at 20:35
$begingroup$
However, this does seem weird in the context of the paper, so maybe they are looking for a different way of doing things. I'll just have to have another look
$endgroup$
– João Duarte
Dec 3 '18 at 20:41
$begingroup$
However, this does seem weird in the context of the paper, so maybe they are looking for a different way of doing things. I'll just have to have another look
$endgroup$
– João Duarte
Dec 3 '18 at 20:41
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%2f3024518%2fdegrees-in-monomials%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
