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 &...
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 ...
3
votes
2
answers
3k
views
Factor $x^5-1$ into irreducibles in $\mathbb{F}_p[x]$
I have to factor the polynomial $f(x)=x^5-1$ in $\mathbb{F}_p[x]$, where $p \neq 5$ is a generic prime number.
I showhed that, if $5 \mid p-1$, then $f(x)$ splits into linear irreducible.
Now I ...
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 ...
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 ...
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 ...
2
votes
0
answers
245
views
Applications of the Hermite's criterion?
I found this statement on permutation polynomials and I was wondering in which domain we can find applications and what is its aim.
Here is the criterion : «If $q=p^n$ with $p$ a prime number then $f\...
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[...
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 ...
68
votes
2
answers
33k
views
Number of monic irreducible polynomials of prime degree $p$ over finite fields
Suppose $F$ is a field s.t $\left|F\right|=q$. Take $p$ to be some prime. How many monic irreducible polynomials of degree $p$ do exist over $F$?
Thanks!
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 ...
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 ...
3
votes
2
answers
2k
views
$x^p-x \equiv x(x-1)(x-2)\cdots (x-(p-1))\,\pmod{\!p}$
I got a question to show that :
If $p$ is prime number, then
$$x^p - x \equiv x(x-1)(x-2)(x-3)\cdots (x -(p-1))\,\,\text{(mod }\,p\text{)}$$
Now I got 2 steps to show that the two polynomials ...
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(...
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 ...