Questions tagged [finite-fields]
Finite fields are fields (number systems with addition, subtraction, multiplication, and division) with only finitely many elements. They arise in abstract algebra, number theory, and cryptography. The order of a finite field is always a prime power, and for each prime power $q$ there is a single isomorphism type. It is usually denoted by $\mathbb{F}_q$ or $\operatorname{GF}(q)$.
5,327
questions
8
votes
2
answers
4k
views
Number Theoretic Transform (NTT) example not working out
I'm reading up on the NTT, which is a generalisation of the DFT. I'm working in $\mathbb{F}_5$ with primitive root $w=2 \mod 5$. Suppose I want to compute the NTT of $x=(1,4)$. So far I have obtained:
...
8
votes
2
answers
9k
views
Determine the number of irreducible monic polynomials of degree 3 in $\mathbb F_p[x]$
Determine the number of irreducible monic polynomials of degree 3 in $\mathbb F_p[x]$ where $p$ is a prime.
I'd like to start off by acknowledging that I know there are many posts relating to similar ...
8
votes
2
answers
976
views
A property of finite field of order $2^n$
Suppose $a$ and $b$ are elements of a finite field of order $2^n$ with $n$ odd and $a^2+ab+b^2=0$. Is it necessary that both $a$ and $b$ must be zero ?
I understand that the field has characteristic $...
8
votes
2
answers
305
views
Given a list of $2^n$ nonzero vectors in $GF(2^n)$, do some $2^{n-1}$ of them sum to 0?
Let $G=(\mathbb{Z/2Z})^n$ written additively, $n>1$. (you can think of it as $\mathbb{F}_{2^n}$ but I didn't find that useful... yet)
Let $v_i$ be nonzero elements of $G$ for $i \in \{1 \dots 2^n \...
8
votes
2
answers
1k
views
Finding a primitive element in a field with 27 elements. [duplicate]
I am trying to construct a field with 27 elements, and find a primitive element in that field. I considered the irreducible polynomial $f(x)=x^3+2x+1$ over $\mathbb{Z}_3[x]$. Then I considered
$$\...
8
votes
2
answers
312
views
Rank of a matrix of binomial coefficients
This question arose as a side computation on error correcting codes.
Let $k$, $r$ be positive integers such that $2k-1 \leqslant r$ and let $p$ a prime number such that $r < p$. I would like to ...
8
votes
2
answers
2k
views
Prove $\mathbb{Z}_3[x]/(x^2+1)$ and $\mathbb{Z}_3[x]/(x^2+x-1)$ are isomorphic.
Prove $\mathbb{Z}_3[x]/(x^2+1)$ and $\mathbb{Z}_3[x]/(x^2+x-1)$ are isomorphic by finding an explicit isomorphism.
My question is how I can define the map. Here are what I tried:
$\mathbb{Z}_3[x]/(x^...
8
votes
3
answers
814
views
The group of invertible elements of $\mathbb F_{p}[x]/(x^m)$ is not a cyclic group.
I am stuck in a question about finite fields and would like to ask you for some help.
Given an integer $m\geq 2$ and $p$ a prime number, show that $(\mathbb F_{p}[x]/(x^m))^{\times}$ (the group of ...
8
votes
1
answer
371
views
A first order theory whose finite models are exactly the $\Bbb F_p$
Is there a first order theory $T$ in the language of rings such that its finite models are exactly the fields $\Bbb F_p$ with $p$ prime (but no $\Bbb F_q$ with $q$ a proper prime power is a model of $...
8
votes
1
answer
581
views
Principal divisors
How can i calculate the principal divisor $(f)$ where
$$f = \frac{(x^{3}-1)}{(x^{4}-1)}$$
with $f\in\mathbb{F}_2(x)$. I am recently reading about the subject, so i am looking for a simple solution (...
8
votes
1
answer
4k
views
Algebraic closure of $\mathbb F_p$ [duplicate]
I'm proving that $\overline{\mathbb{F}}_p = \bigcup\limits_{i=1}^{\infty} \mathbb{F}_{p^i}$ is an algebraic closure of $\mathbb{F}_p$ where $p$ is a prime. I think I've gotten down how to prove that $\...
8
votes
1
answer
840
views
The prime number theorem over a finite field - Lang's *Algebra*, Chapter V, Exercise 23(b)
This is Exercise 23(b) of Chapter V (Algebraic Extensions) from Lang's Algebra.
Let $k$ be finite field with $q$ elements, and let $\pi_q(n)$ be the number of monic irreducible polynomials $p \in k[...
8
votes
2
answers
735
views
Linear independence of Galois conjugates
Suppose we have an irreducible degree $n$ polynomial in $\mathbb{F}_{q}[x]$ whose roots
$$ \alpha, \alpha^q, \alpha^{q^2}, \dots, \alpha^{q^{n-1}} $$
over the extension field $\mathbb{F}_{q^n}$ do not ...
8
votes
1
answer
1k
views
How does trigonometry in a Galois field work?
This is a follow-up to this question. I'm interested in doing trigonometry in finite fields on a computer. I do not understand precisely how trigonometric functions are supposed to work in a finite (...
8
votes
1
answer
665
views
Why or why not use an irreducible polynomial for a cyclic redundancy check?
I understand the need for using an irreducible polynomial for a prime power finite field when doing multiplication with numbers in those fields. For certain applications, such as the Q parity bytes ...
8
votes
2
answers
184
views
Is there/can there be a model-theoretic proof of this theorem of arithmetic ?
I read on MO that if an integer $a$ is a square mod $p$ for sufficiently large primes $p$, then $a$ is a square. Now that's a statement that looks awfully like a Lefschetz-principle-type statement; ...
8
votes
1
answer
228
views
Proving $f = x^8+x^7+x^3+x+1$ to be irreducible over $\mathbf{F}_2$.
I am taking all the irreducible polynomials over $\mathbf{F}_2$ of degree 1 to 4 inclusive and using the long division to determine whether the given $f$ is divisible by anyone of them and it is not ...
8
votes
1
answer
616
views
Symmetric groups and the "field with one element"
I have heard several times that one may regard the symmetric group on $n$ letters as the general linear group in dimension $n$ over the "field with one element". In particular this heuristic would ...
8
votes
1
answer
324
views
What does this notation mean: $\displaystyle\lim_{\leftarrow} \,\mathbb{Z}/n\mathbb{Z}$?
Just a small notation question from this Wikipedia page:
The absolute Galois group of a finite field $K$ is isomorphic to the group $$\hat{\mathbb{Z}}=\lim_{\leftarrow} \mathbb{Z}/n\mathbb{Z}.$$
...
8
votes
1
answer
957
views
Finite Field Extensions and the Sum of the Elements in Proper Subextensions (Follow-Up Question)
I recently posted the following question, to which this question is a follow-up. Regardless, my question here will be self-contained.
Let $F$ be a finite field, and let $u,v$ be algebraic over $F$. ...
8
votes
1
answer
1k
views
Multiplicative group modulo polynomials
When working over $\mathbb{Z}$, it is well known what the structure of the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ exactly is:
If $n=p$ for a prime $p$, then $(\mathbb{Z}/p\mathbb{Z})^...
8
votes
1
answer
630
views
Irreducibility of $x^{2n}+x^n+1$
I want to know for what $n$, $$x^{2n}+x^n+1$$ is irreducible modulo 2.
I think for $n=3^k$ but have no idea how to prove it.
8
votes
1
answer
252
views
Arithmetic background of this RNG code
I am trying to figure out the mathematical background of the random number generation of an old video game. It does iterations where it updates a 33-bit state consisting of the variables z (32-bit) ...
8
votes
2
answers
230
views
How to prove that $x^{-1}+y^{-1}+z^{-1} \ne 0$?
Let $m$ odd integer, $m\ge 3$ and $x,y,z\in \mathbb{F}_{2^m}^*$ such that $x+y+z=0$. I have to prove that $x^{-1}+y^{-1}+z^{-1} \ne 0$.
Hint : by absurd suppose that $z^{-1}=x^{-1}+y^{-1}$ and ...
8
votes
2
answers
993
views
Splitting Field of the polynomial $x^4+x+1$ over $\mathbb{F}_2$.
What is the splitting field $\mathbb{F}_q$ of the polynomial $x^4+x+1$ over $\mathbb{F}_2$?
I already knew the polynomial $x^4+x+1$ is irreducible and its roots are distinct in some extension field of ...
8
votes
1
answer
987
views
Roots of random polynomials.
Assume $P(x)$ is a random polynomial of degree $d$, where its coefficients are picked uniformly at random from $\mathbb{F}_p$, and $p$ is a large prime number. So the polynomial is defined over $\...
8
votes
1
answer
410
views
Only finitely many genus $g$ smooth projective curves over a finite field
In this tag Exercise 101.56.7 says:
Let $k$ be a finite field. Let $g > 1$. Sketch a proof of the
following: there are only a finite number of isomorphism classes of
smooth projective curves ...
8
votes
1
answer
299
views
Determine all $P(X)\in K[X]$ such that $P\big(X^2+1\big)=\big(P(X)\big)^2+1$, for fields $K$ of any characteristic.
This question is inspired by this thread. However, in this question, I take an arbitrary field instead of $\mathbb{R}$ and drop the assumption that $P(0)$ must be $0$.
Let $K$ be a field. ...
8
votes
1
answer
1k
views
Ultraproduct of the algebraic closure of finite fields
Ok, I have done a little research on the next problem, and there are simple proofs of it using model theory, logic and the Łoś's theorem. But here, the idea is to prove it using only Field Theory, ...
8
votes
1
answer
508
views
Enumerative interpretation of generalized $q$-hockey stick identity
Pascal's rule
$$ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k} \tag{1} $$
may be used recursively to obtain the hockey stick identity
$$ \binom{n+1}{k+1}=\binom{n}{k}+\binom{n-1}{k}+\cdots+\binom{k}{...
8
votes
1
answer
119
views
Existence of root of a polynomial over $\mathbb F_p$.
I came accross the following question and I can't find an easy proof of this fact :
Let $p\geq 17$ be a prime number such that $p\equiv 1 \pmod 4$.
Show that for any $z\in \mathbb F_p\backslash\{0\}...
8
votes
0
answers
204
views
Galois group of a function field over finite field
I have a question about the structure of this Galois group that I can't understand:
suppose that $p>2$ is prime and $q$ is any power of p, and we have these two function fields:
$$K=\mathbb{F}_{p}(...
8
votes
0
answers
1k
views
What is the frobenius map really?
I know what the frobenius map is the naive sense, just the $p$th power map on an $\mathbb{F}_p$ algebra, and that this can be upgraded somewhat to the generator of the monoid of natural ...
7
votes
4
answers
24k
views
How to find all irreducible polynomials in Z2 with degree 5? [duplicate]
I am totally lost on how to do this one. I am supposed to accomplish the following:
Find all irreducible polynomials in $\mathbb{Z}_2[x]$ with degree $5$.
I may use the fact that x, $x+1$ and $x^2+x+...
7
votes
4
answers
1k
views
What is an extension field? Covered differently in math & in cryptography.
In his book on Cryptography, Paar has this theorem
Theorem 4.3.1 A field with order m only exists if m is a prime
power, i.e., m = p^n, for some positive integer n and prime integer
p. p is called ...
7
votes
2
answers
15k
views
characteristic of a finite field
knowing that the characteristic of an integral domain is $0$ or a prime number, i want to prove that the characteristic of a finite field $F_n$ is a prime number, that is $\operatorname{char}(F_n)\not ...
7
votes
1
answer
2k
views
Is there a finite field in which the additive group is not cyclic?
Is there a finite field whose additive group is not cyclic?
7
votes
1
answer
14k
views
Construct a finite field of 16 elements and find a generator for its multiplicative group.
Construct a finite field of 16 elements and find a generator for its multiplicative group. Find all generators of multiplicative group.
Very obvious Construction of a field with 16 elements according ...
7
votes
3
answers
565
views
irreducibility of $x^{5}-2$ over $\mathbb{F}_{11}$.
I am tasked to show that $x^{5}-2$ is irreducible over $\mathbb{F}_{11}$ the finite field of 11 elements. I've deduced that it has no linear factors by Fermat's little theorem. But showing it has no ...
7
votes
3
answers
11k
views
Addition and Multiplication in $F_4$ [duplicate]
Could anyone explain the example below? Why is $F_4 = $ {$0,1,x,x+1$}? (I was learning that it should be $F_4 = $ {$0,1,2,3$}). And how do we get the two tables?
7
votes
2
answers
3k
views
Frobenius Morphism on Elliptic Curves
I am having some confusion concerning the Frobenius morphism of an elliptic curve over a finite field $\mathbb{F}_q$ with $q = p^r$ and $p$ prime.
I am working with Silverman's "Arithmetic of Elliptic ...
7
votes
2
answers
1k
views
Any two Singer cyclic subgroups of GL(n,q) are conjugate
Cyclic subgroups of $\operatorname{GL}(n,q)$ of order $q^n - 1$ are called Singer cyclic subgroups. The following statement seems to be well-known:
Any two Singer cyclic subgroups of $\operatorname{...
7
votes
2
answers
2k
views
7
votes
2
answers
253
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 ...
7
votes
2
answers
97
views
When does the underlying map of a polynomial induce a permutation on $\mathbb{Z}/p\mathbb{Z}$?
For example, the underlying function of the polynomial
$$f(x)=4x^2-3x^7$$ induces a permutation on $\mathbb{Z}/11\mathbb{Z}$, though I only know the proof by "brutal force" (is there a cleverer proof?)...
7
votes
4
answers
2k
views
Existence of homomorphisms between finite fields
Let $F$ and $E$ be the fields of order $8$ and $32$ respectively. Construct a ring homomorphism $F\to E$ or prove that one cannot exist.
Any element $x$ of $F$ satisfies $x^8=x$ and any nonzero ...
7
votes
2
answers
951
views
Field $\mathbb{Q}(\alpha)$ with $\alpha=\sqrt[3]7+2i$
(1) Prove that $\alpha=\sqrt[3]7+2i$ is algebraic over $\mathbb{Q}.$
(2) Prove that both $\sqrt[3]7, 2i$ are elements of $\mathbb{Q}(\alpha)$.
(3) Compute $[\mathbb{Q}(\alpha):\mathbb{Q}]$.
(4) Find ...
7
votes
2
answers
6k
views
Constructing an explicit isomorphism between finite extensions of finite fields
Suppose $K$ is a finite field, $K = \mathbb F_{p^s}$. If we take an irreducible polynomial $f$ of degree $d$ over $K$, then the splitting field $L$ of $f$ is $K(\alpha)$ where $f$ is the minimal ...
7
votes
3
answers
112
views
Over $\mathbb{F}_2$, find a $5\times 5$ matrix of order 31.
So I found that $x^5+x+1$ is irreducible over $\mathbb{F}_2$ and produced the quotient, a field of order $32$. Now, I need to find a $5\times 5$ matrix of order 31 over $\mathbb{F}_2$. I don't see the ...
7
votes
3
answers
2k
views
Sum of the values of a polynomial over a finite field
I’ve come across this problem in a coding theory course, and neither I nor several of my colleagues could solve it to our satisfaction.
Let $F:=\mathrm{GF}{\left(q\right)}$ denote the field with $q$ ...