1
$\begingroup$

I am currently enrolled in a computer algebra class for engineers, and while I have some background in discrete algebra from a previous course, it's quite limited. I'm seeking assistance with understanding the application of the trace operation in the context of polynomials defined over the field $X = \mathbb{F}_p[x]/(f(x))$, where $f(x)$ is an irreducible polynomial of degree $n$. The base field is based on an uneven prime $p$.

Specifically, I'm attempting to construct a bound of the trace for the polynomial $m + 2r$. Both $m$ and $r$ are polynomials in the defined field $X$. The polynomial $m$ and has coefficients in the set $\{0,1\}$ and $r$ has coefficients in $\{-1,0,1\}$, and both $m$ and $r$ are of order $n-1$. I was advised to refer to a certain paper that introduced the concept. This was the paper by Dipayan Das and Antoine Joux (On the hardness of the finite field isomorphism problem, Available at https://eprint.iacr.org/2022/998).

In addition, we are also working with a special form of $f(x)$, considering a monic irreducible polynomial where the other coefficients are sampled from the $\{-1,0,1\}$ - distribution. Hence, the coefficients $a_{0},\cdots, a_{n-1}$ are sampled from $\{-1,0,1\}$ such that the polynomial is irreducible.

$f(x)=x^n + a_{n-1}x^{n-1} + \cdots + a_{1}x + a_{0}$

However, the polynomial used here is assumed to be sparse whereas we are still dealing with the $m$ and $r$ described earlier which are very much not sparse.

For people who are not familiar with this kind of operation. In the context of finite fields, the symbol "Tr()" typically represents the trace function. The trace function in finite fields maps an element of the field to its trace, which is a measure of the sum of its iterated conjugates over the field.

More formally, let's consider an element $ \alpha $ in a finite field $ \mathbb{F}_q $, where $ q $ is a prime power (in this case $p^n$). The trace of $ \alpha $, denoted by $ \text{Tr}(\alpha) $, is defined as the sum of all the conjugates of $ \alpha $ over the base field $ \mathbb{F}_p $, where $ p $ is the characteristic of the field:

$\text{Tr}(\alpha) = \alpha + \alpha^p + \alpha^{p^2} + \cdots + \alpha^{p^{n-1}}$

Here, $ n $ is the degree of the field extension, and the sum consists of all the distinct elements obtained by raising $ \alpha $ to the powers of $ p $ modulo the irreducible polynomial $f(x)$ defining the field extension.

The trace function has several important properties, including linearity and invariance under field automorphisms.

However, despite my efforts, I am struggling to understand how to apply the linearity of the trace operation in this context. My attempted approach was to use the property $\text{Tr}(m+2r) = \text{Tr}(m) + 2\text{Tr}(r)$, but I have been unable to find any resources that relate the trace to the specific coefficients in the polynomials.

I would greatly appreciate any guidance or assistance you can provide on this matter.

Thank you.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

First,

I have been unable to find any resources that relate the trace to the specific coefficients in the polynomials

This is expected. The trace of a field element is independent of the particular representation of that field element. This is actually the property used in the paper you linked to break the finite field isomorphism problem. So it seems unlike the trace of a field element can be connected to the particular coefficients of that field element in a straightforward way, as this would have to be true in all possible basis simultanously, which seems unlikely.

That all being said, you can apply linearity to $m, r$ to upper bound them as $\mathsf{Tr}(m) = \sum_i m_i \mathsf{Tr}(x^i)$. The expression for $\mathsf{Tr}(x^i)$ can be found in your linked paper I think.

That all being said, I think your biggest point of confusion is probably

However, the polynomial used here is assumed to be sparse whereas we are still dealing with the $m$ and $r$ described earlier which are very much not sparse.

While you are right that $m, r$ are not sparse, neither is the polynomial in Das-Joux. An example result that discusses a sparse polynomial (say Lemma 1 of the paper) is about the sparsity of $f(x)$, the defining polynomial of $X$. This is a conceptually different polynomial than $m$ or $r$. For example, in the Das-Joux paper, they are bounding the trace of polynomials $A_i(y)$, which are the image under a change-of-basis of polynomials $a_i(x)$ such that $\lVert a_i(x)\rVert\leq \beta$ is of bounded norm. This bounded norm (Section 2.1) is the $\ell_\infty$ norm, e.g. their polynomials look very similar to yours. This is all to say that your question sounds very similar to the question investigated by Das-Joux, and I would suggest you reread their paper (after disambiguating the role of the defining polynomial $f(x)$, required to be sparse, and the polynomials they bound the trace of $a_i(x)$, of bounded $\ell_\infty$ norm).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ok, I will do this. Thank you for addressing any possible points. My colleagues pointed out that I forgot to mention a crucial detail since you pointed out that a special form of $f(x)$ might change things. In the case of the application we are viewing we are considering a monic irreducible polynomial where the other coefficients are sampled from the $\{-1,0,1\}$ - distribution. $\endgroup$ Commented Apr 1, 2024 at 8:22
  • $\begingroup$ The main thing I think you need is a bound on $\mathsf{Tr}(x^i)$ for such $f$ (and I thing your entire question essentially reduces to estimating this). It might make sense to try computing this experimentally to see what types of bounds it is reasonable to expect to hold. It should be fairly straightforward to compute such a quantity using sagemath for any given $f$, and then compute the distribution of $\Pr[i] = \mathsf{Tr}(x^i)$ for $f$ sampled as you have specified. $\endgroup$ Commented Apr 1, 2024 at 17:29
0
$\begingroup$

When f(x) is (half) sparse and ternary, we have a very special form of the traces of the powers of x (Lemma 1). However, as the sparsity decreases, the traces of the powers of x increase. This is essentially due to the equation (1) in the lemma. This can be illustrated by small examples:

n=32, q=1009, f(x)=X^32 + 1008X^16 + X^14 + X^13 + X^12 + X^11 + X^9 + 1008X^7 + 1008X^5 + X^3 + 1008*X^2 + X + 1008, trace(x^i)=(32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, -18, -19, -20, -21, 0, -23, 0, 25, 0, 27, 0, -29, 30, -31)

n=32, q=1009,f(x)=X^32 + 1008X^20 + X^19 + 1008X^18 + 1008X^17 + X^16 + X^15 + 1008X^12 + X^11 + X^10 + 1008X^8 + X^7 + X^6 + 1008*X^5 + X^2 + 1008, trace(x^i)=(32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, -13, 14, 15, -16, -17, 0, 0, 20, -21, -22, 0, 36, -50, 13, 27, -42, 29, -15, -62)

n=32, q=1009, f(x)=X^32 + 1008X^27 + X^26 + 1008X^25 + 1008X^23 + 1008X^20 + X^18 + 1008X^17 + 1008X^14 + X^9 + 1008X^8 + 1008X^7 + 1008X^6 + X^5 + X^4 + 1008*X^2 + 1008, trace(x^i)=(32, 0, 0, 0, 0, 5, -6, 7, 0, 9, 5, -11, 30, -13, 7, 5, 0, 51, -33, 57, -15, 28, 55, -115, 198, -70, 143, 9, -133, 406, -331, 465)

n=32, q=1009, f(x)=X^32 + X^31 + X^29 + 1008X^28 + X^27 + X^24 + 1008X^23 + X^21 + 1008X^19 + X^18 + 1008X^16 + X^15 + X^14 + X^9 + 1008X^6 + X^5 + X^3 + 1008, trace(x^i)=(32, -1, 1, -4, 9, -16, 22, -36, 57, -94, 166, -287, 462, 267, 231, -86, 502, 205, -420, 31, -349, -436, -19, -140, -31, -347, -365, -101, 7, 164, -265, -300)

Improve this answer
$\endgroup$
1
  • $\begingroup$ We have $\LaTeX$/ MathJax installed in our site. $\endgroup$ Commented Apr 4, 2024 at 18:05

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.