All Questions
Tagged with polynomials finite-fields
797
questions
83
votes
3
answers
13k
views
Polynomials irreducible over $\mathbb{Q}$ but reducible over $\mathbb{F}_p$ for every prime $p$
Let $f(x) \in \mathbb{Z}[x]$. If we reduce the coefficents of $f(x)$ modulo $p$, where $p$ is prime, we get a polynomial $f^*(x) \in \mathbb{F}_p[x]$. Then if $f^*(x)$ is irreducible and has the same ...
- 12k
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!
- 4,215
54
votes
3
answers
18k
views
Irreducible polynomial which is reducible modulo every prime
How to show that $x^4+1$ is irreducible in $\mathbb Z[x]$ but it is reducible modulo every prime $p$?
For example I know that $x^4+1=(x+1)^4\bmod 2$. Also $\bmod 3$ we have that $0,1,2$ are not ...
- 11.1k
41
votes
2
answers
2k
views
Shortest irreducible polynomials over $\Bbb F_p$ of degree $n$
For any prime $p$, one can realize any finite field $\Bbb F_{p^n}$ as the quotient of the ring $\Bbb F_p[X]$ by the maximal ideal generated by an irreducible polynomial $f$ of degree $n$. By dividing ...
- 102k
31
votes
6
answers
6k
views
Do we really need polynomials (In contrast to polynomial functions)?
In the following I'm going to call
a polynomial expression an element of a suitable algebraic structure (for example a ring, since it has an addition and a multiplication)
that has the form $a_{n}x^{...
- 5,255
26
votes
3
answers
29k
views
How can I prove irreducibility of polynomial over a finite field?
I want to prove what $x^{10} +x^3+1$ is irreducible over a field $\mathbb F_{2}$ and $x^5$ + $x^4 +x^3 + x^2 +x -1$ is reducible over $\mathbb F_{3}$.
As far as I know Eisenstein criteria won't help ...
- 555
26
votes
1
answer
629
views
The Caverns of Primitive Polynomial GF[2]
With primitive polynomials, it's not too hard to get all the polynomials of a particular power. For example, columns in the following represent the 18, 16, 48, and 60 primitive polynomials of GF[2^7],...
- 21.4k
19
votes
2
answers
765
views
How many pairs of nilpotent, commuting matrices are there in $M_n(\mathbb{F}_q)$?
As a follow-up to this question, I've been doing some work counting pairs of commuting, nilpotent, $n\times n$ matrices over $\mathbb{F}_q$. So far, I believe that for $n=2$, there are $q^3+q^2-q$ ...
- 31.7k
18
votes
3
answers
10k
views
Product of all monic irreducibles with degree dividing $n$ in $\mathbb{F}_{q}$?
In the finite field of $q$ elements, the product of all monic irreducible polynomials with degree dividing $n$ is known to be $X^{q^n}-X$. Why is this?
I understand that $q^n=\sum_{d\mid n}dm_d(q)$, ...
- 311
17
votes
3
answers
20k
views
How many irreducible polynomials of degree $n$ exist over $\mathbb{F}_p$? [duplicate]
I know that for every $n\in\mathbb{N}$, $n\ge 1$, there exists $p(x)\in\mathbb{F}_p[x]$ s.t. $\deg p(x)=n$ and $p(x)$ is irreducible over $\mathbb{F}_p$.
I am interested in counting how many such $...
- 23.2k
17
votes
2
answers
22k
views
Reed Solomon Polynomial Generator
I am developing a sample program to generate a 2D Barcode, using Reed-Solomon error correction codes. By going through this article, I am developing the program. But I couldn't understand how he ...
- 389
15
votes
2
answers
7k
views
Why $x^{p^n}-x+1$ is irreducible in ${\mathbb{F}_p}$ only when $n=1$ or $n=p=2$
I have a question, I think it concerns with field theory.
Why the polynomial $$x^{p^n}-x+1$$ is irreducible over ${\mathbb{F}_p}$ only when $n=1$ or $n=p=2$?
Thanks in advance. It bothers me for ...
- 151
13
votes
2
answers
17k
views
Understanding Primitive Polynomials in GF(2)?
This is an entire field over my head right now, but my research into LFSRs has brought me here.
It's my understanding that a primitive polynomial in $GF(2)$ of degree $n$ indicates which taps will ...
- 501
12
votes
2
answers
10k
views
When is a cyclotomic polynomial over a finite field a minimal polynomial? [duplicate]
When is the cyclotomic polynomial $f(x)$ over a finite field $\mathrm{F}_q$ also the minimal polynomial of some element $\alpha \in \mathrm{F}_q$?
- 428
12
votes
2
answers
2k
views
On irreducible factors of $x^{2^n}+x+1$ in $\mathbb Z_2[x]$
Prove that each irreducible factor of $f(x)=x^{2^n}+x+1$ in $\mathbb Z_2[x]$ has degree $k$, where $k\mid 2n$.
Edit. I know I should somehow relate the question to an extension of $\mathbb Z_2$ of ...
- 931