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)$.

Filter by
Sorted by
Tagged with
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: ...
pshmath0's user avatar
  • 10.6k
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 ...
Robert Cardona's user avatar
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 $...
liesel's user avatar
  • 869
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 \...
Tib's user avatar
  • 786
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 $$\...
ilovebulbasaur's user avatar
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 ...
J.-E. Pin's user avatar
  • 40.1k
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^...
dh16's user avatar
  • 1,418
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 ...
Lullaby's user avatar
  • 2,361
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 $...
Dominik's user avatar
  • 14.4k
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 (...
Dimitri's user avatar
  • 1,939
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 $\...
Geigercounter's user avatar
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[...
user avatar
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 ...
user80108's user avatar
  • 322
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 (...
hatch22's user avatar
  • 1,076
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 ...
penguin359's user avatar
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; ...
Maxime Ramzi's user avatar
  • 43.6k
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 ...
user110219's user avatar
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 ...
tharris's user avatar
  • 1,804
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}.$$ ...
Alexander Gruber's user avatar
  • 26.9k
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$. ...
Elchanan Solomon's user avatar
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})^...
BharatRam's user avatar
  • 2,497
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.
qwenty's user avatar
  • 1,540
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) ...
GDumphart's user avatar
  • 2,250
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 ...
Maman's user avatar
  • 3,300
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 ...
user avatar
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 $\...
Aydin's user avatar
  • 333
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 ...
user avatar
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. ...
Batominovski's user avatar
  • 49.6k
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, ...
pjox's user avatar
  • 505
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}{...
anon's user avatar
  • 152k
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\}...
user141753's user avatar
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}(...
Soroush Salehin's user avatar
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 ...
Chris H's user avatar
  • 6,530
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+...
user avatar
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 ...
user93353's user avatar
  • 466
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 ...
palio's user avatar
  • 11k
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?
Chandan Das's user avatar
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 ...
user avatar
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 ...
TheNumber23's user avatar
  • 3,304
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?
ensbana's user avatar
  • 2,277
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 ...
Luca's user avatar
  • 1,616
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{...
azimut's user avatar
  • 22.7k
7 votes
2 answers
2k views

How does Mathematica solve $f(x)\equiv 0\pmod p$?

I input ...
lsr314's user avatar
  • 15.8k
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 ...
A. Goodier's user avatar
  • 10.9k
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?)...
Zuriel's user avatar
  • 5,331
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 ...
user557's user avatar
  • 11.9k
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 ...
Andy's user avatar
  • 1,109
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 ...
Jonathan's user avatar
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 ...
CitizenSnips's user avatar
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$ ...
anonymous's user avatar
  • 892

1
3 4
5
6 7
107