All Questions
Tagged with polynomials finite-fields
797
questions
0
votes
0
answers
16
views
AES S-box as simple algebraic transformation
The next matrix represents the Rijndael S-box according to wikipedia and other sources
$$\begin{bmatrix}s_0\\s_1\\s_2\\s_3\\s_4\\s_5\\s_6\\s_7\end{bmatrix} =
\begin{bmatrix}
1 & 0 & 0 &...
- 463
0
votes
0
answers
20
views
How to understand 'the problem of determining the exact number of monomials in P(x) given by a black box is #P-Complete'
In this paper:https://dl.acm.org/doi/pdf/10.1145/62212.62241, what's given is $P(x)$ a (sparse) multivariate polynomial with real(or complex) coefficients.
The author claimed two things.
It is known ...
- 61
1
vote
1
answer
32
views
Equivalent polynomials over a finite field
Disclamer. I'm not good at math, and the last time I did it in school was 10 years ago, so I'm writing everything in my own words.
Suppose we are working with polynomials in the space of remainders ...
- 13
1
vote
0
answers
54
views
Does there exists something like the BKK Theorem for polynomials over finite fields?
I'm trying to count the number of common $\mathbb{F}_q^\times$-zeros of some polynomials $f,g \in \mathbb{F}_q[x,y]$. I thought I had a solution using the BKK theorem but I reread the theorem ...
- 41
0
votes
1
answer
92
views
Extended euclidian algorithm
I'm trying to understand how the matrix form of the extended euclidian algorithm for polynomials works for a BCH code with coefficients from $GF(2^4)$ in https://en.wikipedia.org/wiki/BCH_code
for ...
- 315
2
votes
2
answers
85
views
In polynomial quotient rings over $\mathbb{F}_2$, how to use Chinese Remainder Theorem to solve equations?
Suppose I work over the polynomial quotient ring $\mathbb{F}_2[x,y]/\langle x^m+1,y^n+1\rangle$, and I want to solve for polynomials $s[x,y]$ that simultaneously solve the equations
\begin{equation}
a[...
- 133
1
vote
0
answers
86
views
Number of irreducible polynomials of degree at most n over a finite field
We know that the number $N(n,q)$ of irreducible polynomials of degree $n$
over the finite field $\mathbb{F}_q$
is given by Gauss’s formula
$$N(n,q)=\frac{q-1}{n} \sum_{d\mid n}\mu(n/d)q^d.$$
The number ...
1
vote
0
answers
29
views
Order of $\mathbb F _p [x] / (f)$.
I could use some help with the following exercise:
Find the number of reducible monic polynomials of degree $2$ over $\mathbb F_p$. Show this implies that for every prime $p$ there exists a field of ...
- 485
0
votes
0
answers
28
views
What's the point of the local zeta function?
I'm currently reading through Ireland and Rosen's "A Classical Introduction to Modern Number Theory", and I feel I'm missing the point of Chapter 11 on (local) zeta functions. When I see ...
- 584
0
votes
2
answers
82
views
Is this $f(x) = x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$ irreducible in GF(5)?
Perhaps one can somehow apply Eisenstein's sign here by considering $f(x+1)$, but by default it is formulated for the expansion over $\mathbb{Q}$ of a polynomial from $\mathbb{Z}[x]$. Here we have $GF(...
- 15
0
votes
1
answer
77
views
Show that GF(81) is an $x^{26}+x^{8}+x^{2}+1$ decomposition field
I tried decomposing the polynomial, but after taking out $(x^{2}+1)$ you have to break the remainder into polynomials of degree 4, which is manually hard. Perhaps this is solved by using Frobenius ...
- 15
3
votes
0
answers
67
views
Is this connection between prime numbers, prime polynomials, and finite fields true?
I recently learned of the following connection between prime numbers and prime polynomials in the field of cardinality $2$. Namely, you take a natural number $n$, and use the digits of the base $2$ ...
- 21.4k
2
votes
1
answer
73
views
Why should a splitting field of a polynomial over $\mathbb{F}_p[X]$ be a cyclotomic extension?
I have just been doing a Galois theory exercise and one part of the exercise requires me to explain why, if $f \in \mathbb{F}_p[X]$ is a polynomial of degree $n$, its splitting field $L$ is a ...
- 474
0
votes
0
answers
54
views
When is $f = X^4 -1 \in \mathbb{F}_p[X], p $prime, irreducible and/or seperable? [duplicate]
I'm having some trouble figuring out a solution to this. I understand that $f$ is separable, iff all its roots are distinct, however I'm completely clueless about how to investigate that criterion......
- 17
6
votes
2
answers
151
views
Irreducible polynomial in $\Bbb{Z}_2[x]$
Suppose $2k + 1 \equiv 3 \mod 4$ in $\Bbb{Z}_{\geq 1}$.
Is the polynomial: $p_k(x) = x^{2k + 1} + x^{2k - 1} \dots + x + 1$ irreducible in $\Bbb{Z}_2[x]$?
I do not know whether it is true or not...
(...
- 515
0
votes
0
answers
37
views
Degree of factors of the Artin–Schreier polynomial in $\mathbb{F}_q$. [duplicate]
Consider the field $\mathbb{F}_q$, where $q$ is a power of $p$, say $q=p^n$. Let $f=x^q-x-a\in\mathbb{F}_q[x]$, with $a\in\mathbb{F}_q$.
I'm trying to determine the degree of the irreducible factors ...
- 329
1
vote
0
answers
31
views
Cardinality of the zero locus of a degree 2 homogeneous polynomial on Z/2Z: avoiding Chevalley-Warning
I have never developed sufficient knowledge in algebraic geometry but I ran into an apparently easy problem, so I apologise in advance if my question sounds naive.
Suppose to have a degree $2$ ...
- 123
1
vote
1
answer
68
views
Irreducible polynomials in $\mathbb F_q[T]$
Let $q$ be a power of a prime $p$. Is there an infinite set $S$ of $\mathbb N$ such that for every $l\in S$, the polynomial $T^{q^l}-T-1$ is irreducible in $\mathbb F_q[T]$.
It looks like Artin-...
- 1,157
0
votes
1
answer
93
views
Factorize $x^4 + 4x^2 +1$ over $\mathbb{F}_{29}$
How do I factorize $x^4 + 4x^2 +1$ over $\mathbb{F}_{29}$?
I checked that the discriminant $D = 16 -4 = 12$ is not a square ($12^{14} = -1 \mod 29$) so this polynomial has no roots. Therefore it's ...
- 2,636
1
vote
1
answer
30
views
Distinct derivations of polynomial over finite field
I am a student studying algebra and cryptography.
I wonder below question is possible.
Can I make some polynomials $f(x)$ over finite field that all derivations $f^{(k)}(x)$ are distinct when x is ...
- 13
1
vote
1
answer
89
views
Calculating the gcd of two polynomials in integers using a prime field
Let $f, g \in \mathbb{Z}[x]$. Let also $h \in \mathbb{Q}[x]$ be the $\gcd(f,g)$ found by the Euclidean algorithm. Now, for $p$ an odd prime, let $h^* \in \mathbb{Z}/p\mathbb{Z}[x]$ be the $\gcd(f,g)$ ...
- 172
1
vote
1
answer
45
views
Find $m$ degree $q^{m-1}$ polynomials which give a bijection $\mathbb{F}_{q^m}\cong \mathbb{F}_{q}^m$ with the map $x\mapsto (p_1(x),\dots,p_m(x))$
Let $q$ some prime power. Now take the field $\mathbb{F}_{q^m}$.
We need to find polynomials $p_1(x),p_2(x),\dots,p_m(x)\in \mathbb{F}_{q^m}[x]$ such that $\deg{p_i(x)}=q^{m-1}$ and they also satisfy ...
- 19
2
votes
2
answers
130
views
Number of solutions to $x^2−y^2=a$ over a finite field.
Consider F is a finite field with $ q$ elements, where $q=p^n$, p prime, and n is an integer. Give the number of solutions of pairs (x,y) for the equation $$ x^2-y^2=a $$ according to the value of $ q ...
3
votes
0
answers
109
views
Roots of a irreducible polynomial are linearly independent over a finite field.
Question. When does a irreducible polynomial contains linearly independent roots over a finite field?
Motivation. For a finite cyclic Galois extension $E/F$, if $\alpha\in E$ generates a normal basis, ...
- 2,503
2
votes
1
answer
64
views
Fields of characteristic $p$ where there exists an element $a$ that is not a p:th power.
Suppose $K$ is a field of characteristic $p$, but that $K \neq K^p$, that is, there exists an element $a \in K$ such that there is no $b \in K$ so that $b^p = a$. We want to prove that this implies ...
- 1,276
0
votes
1
answer
44
views
Factorize $x^3-1$ in $F_3[x]$ into irreducible polynomials
I'm fairly new to this topic:
We can see that $x^3-1=(x-1)(x^2+x+1)$
But what I don't understand is how $(x^2+x+1)$ can be further reduced to $(x-1)^2$
Many thanks
- 109
4
votes
0
answers
54
views
Partial fraction decomposition over $\mathbb{F}_{n}[x]$
Consider the rational function $\dfrac{f(x)}{g(x)} \in \mathbb{F}_{n}[x]$ such that $g(x) = p(x) \cdot h(x)$. If $\gcd\left(p(x), h(x)\right) = 1$, then $$\dfrac{f(x)}{g(x)} = \dfrac{f(x)}{p(x) \cdot ...
user1236748
0
votes
0
answers
32
views
A faster way to check irreducibility of quartics in finite fields
A quadratic or a cubic can be shown to be irreducible in $\mathbb{F}_p$ by showing that none of $0, \dots,p-1$ are roots (or more generally all the elements of $\mathbb{F}_{p^n}$). This does not work ...
- 3,940
4
votes
1
answer
99
views
Does $\gcd(x^{p^2+p+1}-1, (x+1)^{p^2+p+1}-1)\neq 1$ in $\mathbb{F}_p[x]$ for all primes $p$?
It seems that for every prime $p$, $x^{p^2+p+1}-1$ and $(x+1)^{p^2+p+1}-1$ are not coprime in $\mathbb{F}_p$. In other words, it seems that there is always a $(p-1)$-th power $x$ in $\mathbb{F}_{p^3}^\...
- 1,923
0
votes
1
answer
90
views
Why can't individual terms of a summation not cancel each other in the 2nd case?
Below is from a paper.
$F(.)$ is a low-degree multivariate polynomial over $\mathbb F$ in $s$ variables.
Checking if $\sum_{x \in \lbrace0,1\rbrace^s} F(x) = 0$ will not prove that that $F(x) = 0\...
- 486
3
votes
1
answer
153
views
Characterization of irreducible polynomials over finite fields - alternative proof?
By accident I have found the following characterization of irreducible polynomials over $\mathbb{F}_p$.
Lemma. Let $g \in \mathbb{F}_p[T]$ be a monic polynomial of degree $m \geq 1$. Then, $g$ is ...
- 165k
1
vote
1
answer
43
views
Quadratic residues of low degree polynomials in $\mathbb{F}_p$
Let $(\frac{a}{p})$ denote the Legendre symbol. Let $P$ be a polynomial over $\mathbb{F}_p$ of degree $d$. I would like to upper bound
$$\Big\lvert\,\mathbb{E}_a \Big(\frac{P(a)}{p}\Big)\Big\rvert$$
...
- 175
0
votes
0
answers
54
views
Reed-solomon coding: question on proof of minimum distance
In the "coefficient view" of Reed-Solomon encoding, the message is interpreted to be coefficients of a polynomial m(x). The code word is $c(x) = m(x)*g(x)$ where $g(x)$ is a generator ...
- 151
1
vote
1
answer
111
views
Fibonacci LFSR - Multiplication in the dual of the polynomial basis
/!\ Warning: long post!
I would like to understand the link between the multiplication in dual of the polynomial basis and the Fibonacci LFSR. I found that things are 'mirrored' so far in their ...
- 11
1
vote
0
answers
48
views
Interpolation of permutation polynomials
Consider the finite field $\mathbb F_q$ where $q=2^n$ and $n \to \infty$. Now given $t = O(1)$ and $x_1,\ldots,x_t,y_1,\ldots,y_t$ where $\forall i \ne j,x_i \ne x_j,y_i \ne y_j$, do one has a ...
- 21
1
vote
0
answers
72
views
Is $\{x^3, x+b\}$ a generating set of $\mathrm{Sym}(\mathbb F_q)$?
Let $q=2^n$ where $n$ is a sufficiently large odd number. Consider the fintie field $\mathbb F_q$ and the symmetric group $\mathrm{Sym}(\mathbb F_q)$ over it.
I use $x^3$ to denote the permutation $x \...
- 21
0
votes
1
answer
155
views
Polynomials GCD over finite field [duplicate]
I'm trying to find the GCD of $x^3+2x^2+3x+4$ and $x+2$ over $\Bbb Z _5[x]$
I tried to use GCD euclidean algorithm and got the folowing:
$x^3+2x^2+3x+4 = (x^2+3)(x+2)+3$
$(x+2) = (2x)3+2$
$3=3\cdot2 + ...
- 158
1
vote
1
answer
69
views
$p$ a prime satisfying $p \equiv 3 \mod 4 $. Then, the quotient field $ F_p [x] / (x^2 + 1)$ contains $\bar{x}$ that is a square root of -1
I know that $x^2 + 1$ is irreducible in $F_p[x]$ if and only if $-1$ is not a square in $F_p$. Otherwise, $x^2 + 1$ could be factored out.
$-1$ not being a quadratic residue in $F_p$ is equivalent to ...
- 155
3
votes
1
answer
210
views
Structure of multiplicative subgroup of a finite field
Consider a finite field $GF(q)$. We refer to $GF(q)^{\times }$ as the multiplicative group of $GF(q)$. Given that $\left| GF(q)^{\times }\right| =q-1$ and $GF(q)^{\times } \cong \mathbb{Z}_{q-1}$ ...
- 51
1
vote
0
answers
45
views
Which are all polynomials in $\mathbb{F}_p[x]$ which are a sum of two squares?
Let $p$ be a prime. Determine all polynomials $f(x) \in \mathbb{F}_p[x]$ for which there exist polynomials $A(x), B(x) \in \mathbb{F}_p[x]$ such that $f(x) = A(x)^2 + B(x)^2$.
If we were working with $...
- 2,733
-1
votes
3
answers
180
views
"Low degree Polynomials do not have too many roots" - what exactly does this mean?
I am watching this video from a playlist on Algebraic Coding theory - https://www.youtube.com/watch?v=XH7npgKN93k&list=PLkvhuSoxwjI_UudECvFYArvG0cLbFlzSr&index=16 - this particular video in ...
- 486
4
votes
0
answers
39
views
Zeta function for Powerful Polynomials over Finite Field
I am currently working on a problem that requires me to get find a simpler expresion for:
$$\sum_{f \in \mathcal{S}_h} \frac{1}{|f|^s} $$
Where $\mathcal{S}_h$ is the set of $h$-full polynomials (i.e. ...
0
votes
1
answer
143
views
Factorization of $x^{38} - 1$ in $F_5$
I am looking for a way to factorize $x^{38} - 1$ polynomial in $F_5$ . So far I have:
$x^{38} - 1 = (x^{19} - 1)(x^{19} + 1) = (x - 1)(x^{18} + x^{17}... + 1)(x + 1)(x^{18} - x^{17} + ... + 1)$
I can ...
2
votes
1
answer
73
views
$𝜑(𝑥) = 𝑥^{𝑛−1} + 𝑥^{𝑛−2} + ⋯ 𝑥 + 1$ then $(𝜑(𝑥))^2 = 𝑛𝜑(𝑥)$ in $𝔽[𝑥]/⟨ 𝑥^𝑛 − 1 ⟩$
If $𝔽$ is a finite field with $q$ elements an $n$ . I need to prove that if $𝜑(𝑥) = 𝑥^{𝑛−1} + 𝑥^{𝑛−2} + ⋯ 𝑥 + 1$ then $(𝜑(𝑥))^2 = 𝑛𝜑(𝑥)$ in $𝔽[𝑥]/⟨ 𝑥^𝑛 − 1 ⟩$
I tried to prove it ...
- 23
0
votes
0
answers
19
views
Explicit bivariate resultant example
I have two polynomials modulo a prime $p$ with a common root $(x_0,y_0)$ with $|x_0|,|y_0|<\sqrt{p}$ and there are no other roots in $\mathbb F_p$ or no other roots of this size in $\mathbb F_p$ (...
- 6,245
1
vote
0
answers
96
views
Schonhage-Strassen algorithm for multiplication of polynomials over a finite field (additive vs multiplicative complexity)
Trying to understand the Schonhage-Strassen algorithm for multiplying two polynomials $f(X)$, $g(X)$ of degree $n$ over a finite field $\mathbb{F}_q[X]$ with $q$ a prime such that $q-1$ does not have ...
- 181
0
votes
0
answers
73
views
Decomposition of bivariate polynomials over finite fields as a sum of univariate products
Let $p$ be a prime. Given a bivariate polynomial $f(X,Y)\in \mathbb{F}_p[X,Y]$ with degrees $d_1,d_2$ in $X,Y$ respectively, what is the lowest known upper bound on the smallest integer $k$ such that $...
- 181
1
vote
0
answers
63
views
If a function interpolates as a polynomial on arithmetic progressions, is it a polynomial function?
Let $F$ be a finite field of size $q$, and let $d<q$. It is well known that for every sequence $x_0,x_1,\ldots, x_{d+1}$ of distinct elements in $F$, there is a sequence $a_1,\ldots,a_d$ of ...
- 111
0
votes
1
answer
201
views
Splitting field of $x^3 +x +1$ over $\mathbb F_{11}$
This is a HW problem for an algebra course.
Determine the splitting field of $f(x)=x^3+x+1$ over $\mathbb F_{11}$.
I tried to use the answers from this question and this question to help me, but want ...
- 2,454
1
vote
0
answers
58
views
Cubic polynomials over finite fields
I was watching an introduction video on "Tangent conics and tangent quadrics" by Prof. Norbert Wildberger , where the following Taylor polynomial was introduced:
$$p_r(x) = (a+br+cr^2 + dr^3)...
- 2,132