All Questions
Tagged with polynomials finite-fields
797
questions
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