All Questions
Tagged with polynomials finite-fields
797
questions
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
8
votes
2
answers
267
views
How to factor a polynomial quickly in $\mathbb{F}_5[x]$
I was doing an exercise in Brzezinski's Galois Theory Through Exercises and needed to factor the polynomial
$x^6+5x^2+x+1=x^6+x+1$ in $\mathbb{F}_5[x]$. Is there a quick way to do this?
I can see it ...
- 11k
0
votes
1
answer
72
views
Why is my equation not true on all elements?
Consider a finite field $F_{17}$. In this, $\omega = 4$ is the primitive $4$th root of unity.
So there is a subgroup $\Omega = \{1, \omega, \omega^2, \omega^3\}$
Consider a polynomial $f \in F_{17}[x]$...
- 486
1
vote
3
answers
99
views
Number of roots of $f=x^5-x-1$ in $\mathbb{F}_4$
According to David Cox’s ‘Galois Theory’ (Proposition 11.1.5.),
If $f \in \mathbb{F}_p[x]$ is nonconstant and $n \geq 1$, then the
number of roots of $f$ in $\mathbb{F}_{p^n}$ is the degree of the
...
- 1,788
0
votes
1
answer
286
views
XOR-Product Modulo Prime
Every natural number seems to map to a polynomial in binary field GF(2). For example, $11 = 1011_2 \mapsto x^3 + x + 1$, and $x^3 + x + 1 \mid_{x=2}$ gives 11. How naturally can I go between natural ...
- 10.9k
0
votes
1
answer
43
views
$(\mathbb{F}[T] \ / \ P^2 \mathbb{F}[T])^*$ cyclic if and only if $\text{deg}(P)=1$ where $P$ is an irreducible polynomial over a finite field [duplicate]
I am asked to prove that if $\mathbb{F}$ is a finite field of size $p$ prime and $P\in \mathbb{F}[T]$ is an irreducible polynomial over $\mathbb{F}$ then $(\mathbb{F}[T] \ / \ P^2 \mathbb{F}[T])^*$ is ...
0
votes
1
answer
75
views
Weird result in a finite field
Consider the field $\mathbb{Z}_{5}[x]_{x^2 + x + 1}$. In this field, the polynomial $x^3$ is equal to
$$
\begin{align}
x^3
&\equiv_{x^2 + x + 1} x^3 - x(x^2 + x + 1) \\
&\equiv_{x^2 + x + 1} x^...
- 193
2
votes
1
answer
67
views
Some class of *piecewise linear* map on finite field $\mathbb{F}_{2^n}$ [closed]
Let $\mathbb{F}_{2^n}$ be a finite field of $2^n$ elements.
$H<\mathbb{F}_{2^n}^*$ and $\mathbb{F}_{2^n}^* = \cup^{r-1}_{i=0}H_i$ is splitting into cosets of the nontrivial (multiplicative) ...
- 21
2
votes
1
answer
78
views
Prove that element is a square (follow up).
I asked the following question and got some awesome answers:
Suppose that $x^5 + ax + b \in \mathbb{F}_p[x]$ is irreducible over $\mathbb{F}_p$. Is it true that $25b^4 + 16a^5$ is a square in $\...
- 169
2
votes
1
answer
76
views
Zeros of characteristic polynomial over field $\mathbb{Z}_5$
I need to find the eigenvalues of the matrix
$$
A = \begin{bmatrix}
1 & 0 & 0 \\
2 & 3 & 3 \\
1 & 1 & 0
\end{bmatrix} \in \mathbb{Z}_5^{3 \times ...
1
vote
0
answers
145
views
Schwartz–Zippel lemma tight bound
As we know by Schwartz–Zippel lemma for $p\in F[x_1 , x_2 , ... , x_n] $ of degree $d$ over a finite field $F$ and for $ r_1,r_2,...,r_n $ uniformly samples from it:
$Pr[P(r_1,...,r_n) = 0 ] \le \frac ...
