Xrfgtjtk

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!

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.