Finite fields are structures arising in abstract algebra. 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)$.

learn more… | top users | synonyms (1)

6
votes
1answer
50 views

Is there an obvious reason why the number of binary Lyndon words is equal to the number of irreducible polynomials over GF(2)?

The title of Sloane's A001037 is: Number of degree-$n$ irreducible polynomials over $GF(2)$; number of $n$-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive ...
2
votes
1answer
76 views

How to compute in the multiplicative group of finite field “economically” and efficiently

Let $GF(p^n)$ be a finite field, then the additive group is isomorphic to $\mathbb Z / (p\mathbb Z)^n$, and it is simple to compute in that group. The multiplicative group is always cyclic (a standard ...
3
votes
2answers
49 views

Degree of splitting field for $x^3-3x-1$ over $\Bbb Q$ and $\Bbb F_5$

I want to find the degree of the splitting field for $x^3-3x-1$ over $\Bbb Q$ and $\Bbb F_5$. My attempt is contained below.
1
vote
3answers
42 views

Solving equations in fields.

How does one solve $\mathbf x^2-3$ and $\mathbf x^2+x-1$ in $F_7[x] / (x^2-5)$? Not sure how do do it, I know there is a solution for both, but I don't see how to get there. Thanks.
1
vote
1answer
48 views

Roots of polynomials of the form $x^q-x-\alpha$ over $\mathbb F_{q^m}$

Let $q$ be a prime power and $\mathbb F_q$ a finite field with $q$ elements. Moreover let $\mathbb F_{q^m}$ be an extension field. For every $\alpha \in \mathbb F_{q^m}$ define the polynomial $$ ...
0
votes
1answer
23 views

Proving a polynomial is irreducible over a field.

I would like to prove that x² + 2x - 1 is irreducible over ℤ/5ℤ. Not really sure how to go with that, it's probably related to finding roots in the field since it's already monic, right ? Thank ...
0
votes
1answer
42 views

Equations in fields.

So a) is simple, calculate the squares and cubes mod 7. However, for b) I know that Z7[x]/(f(x)) if f(x) is irreducible of degree 2 would work, but then how do I solve the equations ? I assume ...
23
votes
4answers
1k views

What's so special about characteristic 2?

I've often read about things which do not work in a field with a characteristic $2$, mainly things which have to do with factoring, or similar things. I'm not exactly sure why, but the only example of ...
1
vote
1answer
44 views

Convolution of indicator functions with values in a finite field

This is something I haven't seen online yet, indicator functions with values in a finite field. Probably for a good reason, but I would like to know why, and if there are still things that can be ...
2
votes
0answers
15 views

Field Trace Identities

Let $\mathbb{F}_q$ be the finite field with $p^n$ elements and consider the trace map $$\mbox{Tr}: \mathbb{F}_q\to \mathbb{F}_p,$$ where $$\mbox{Tr}(\alpha)=\alpha+\alpha^p+\alpha^{p^2}+\cdots ...
3
votes
3answers
132 views

Reducible polynomial over $\mathbb{F}_9$, but irreducible over $\mathbb{F}_{27}$

Show that $P=X^4+X+2$ is reducible over $\mathbb{F}_9$, but irreducible over $\mathbb{F}_{27}$. I would appreciate any hints. (I know $P$ is irreducible over $\mathbb{F}_3$ by brute force, and ...
2
votes
0answers
33 views

Parity of the number of '1's in subsets of the coefficients of irreducible polynomials of degree $n$ over $GF(2)$

Let $n > 2$ and let $S \subsetneq [n-1] = \{1, \ldots, n-1\}$. Has it been proven whether or not we can always find an irreducible polynomial $f(x)$ of degree $n$ over the binary field $GF(2)$ such ...
1
vote
1answer
45 views

Polynomial solutions in Quotient ring

I am wondering if someone can help me to look over the following; It is a question consisting of a few different but related parts. I was asked to consider the finite field with 7 elements, and to ...
0
votes
1answer
24 views

Division Algorithm and Polynomials.

By the Division Algorithm, I know I can reduce every polynomial in $\mathbb{Z}_2[x]$ to a polynomial $ax+b$ mod $x^2+1$. There are two possibilities for $a$ and two for $b$, a total of 4. It follows ...
1
vote
1answer
32 views

Galois Field to bits, implementation is fine, but the mathematics is not.

I am working on a hardware implementation of the SIMON cipher and the key expansion is based on GF(2). The original paper is here, https://eprint.iacr.org/2013/404 I have successfully created the ...
0
votes
0answers
26 views

For $f(x) \in \mathcal{F}_{q^r}[x]$, how to find all $p(x)f(x)$ s.t. its coefficients are $\mathcal{F}_q$-linear over coefficients of $f(x)$?

I want all the coefficients of $p(x)f(x) = \sum_{i=0}^{n-1} b_i x^i$ to be the $\mathcal{F}_q$-linear combinations of coefficients of $f(x) = \sum_{i=0}^{m-1} a_i x^i$, $m < n$. In another words, ...
1
vote
1answer
33 views

Why $\mathbb F_q/\mathbb F_p$ where $q=p^n$ is an extension of degree $n$ ? compute his Galois group.

Let $q=p^n$ where $p$ is prime. Q1) Why is $X^{q}-X\in \mathbb F_p[X]$ irreducible ? Don't we have $X^q-X=X(X^{q-1}-1)$ ? Q2) Suppose it is irreducible, his degree is $p^n$, then $[\mathbb ...
2
votes
0answers
58 views

Cuspform, elliptic curves and character sums

I was trying to read through some note by Kowalski (see https://people.math.ethz.ch/~kowalski/ik-ant-exp-sums.pdf). I was interested in trying to understand the following. The author states on page ...
1
vote
1answer
33 views

Splitting a polynomial into irreducible polynomials that all have the same degree

Let $q$ be a prime number and define $\Phi_q = X^{q-1} + \cdots + X^2 + X + 1 \in \mathbb{Z}[X] $. Let $p$ be a prime number and define $f_{q,p} = \Phi_q \bmod p \in \mathbb{F}_p[X]$. ...
1
vote
0answers
43 views

Product of elements in finite field

Let $q$ be a prime or primer power such that $\mathbb{F}_q$ is a finite field. Now consider the extension $\mathbb{F}_{q^m}$, which may be regarded as a vector space of dimension $m$ over ...
1
vote
0answers
43 views

Linear equations over finite field of size 2

Let $\alpha_1^1x_1+\ldots+\alpha_n^1x_n=1$ $\ldots$ $\alpha_1^mx_1+\ldots+\alpha_n^mx_n=1$ are equations in $\mathbb{F}_2^n$.(It is not system of equations). I am trying to prove that if every ...
1
vote
3answers
57 views

Is $\mathbb Z_3[x]$ isomorphic with $\mathbb Z$?

Is $\mathbb Z_3[x]$ isomorphic with $\mathbb Z$ ? (This question arose in trying to determine whether there is a commutative ring $R$ with unity such that $R[x]\cong\mathbb Z$ . It is easy to see ...
0
votes
0answers
21 views

What to do if your characteristic equation is not fully reducible over your field when solving a recurrence relation?

My problem is a little more difficult. However, essentially, my problem comes up when we're supposed to find the solution to: $R(n)=R(n-3)+1$, $R(0)=R(1)=R(2)=1$ (the initial conditions don't matter ...
0
votes
1answer
34 views

Prove that if $F$ is a finite field having q elements, then $a^{q-2}=a^{-1}$ for a nonzero $a \in F$ [duplicate]

This is a proposition from J.S.Golan's "The Linear Algebra a beginning graduate student ought to know". I can't understand why it's so. Obviously, the order of $a$ is finite - higher than $1$ and ...
2
votes
1answer
23 views

Group of units of a non-integral quotient ring

I would to like to know which product of cyclic groups the group $A^\times$ of units of the quotient ring $$ A = \mathbb F_5[X] / ((X^2-2)^2) $$ is isomorphic to. I know that $A$ is not an integral ...
0
votes
1answer
27 views

What is the isomorphism between the fields $(Z_2[x]^{<3},+_{x^3+x^2+1},\times_{x^3+x^2+1})$ and $(Z_2[x]^{<3},+_{x^3+x+1},\times_{x^3+x+1})$? [closed]

They are both Galois fields of order 8. I'm not exactly sure what the question means - how does one determine/describe an isomorphism?
2
votes
1answer
37 views

Group action on Finite Field

Suppose $F=\mathbb{F}_{p^n}$ is a degree-$n$ extension of $\mathbb{F}_p$. My questions concerns the action of the multiplicative group $(\mathbb{F}_p)^{\times}$ on $F$ by left multiplication. we can ...
1
vote
1answer
38 views

Proof that the Galois Field of order 8 is a field.

We know that the Galois Field of order 8 is isomorphic with $$\left( Z_2[x]^{< 3}, +_{d(x)}, \times_{d(x)}\right) $$ (Field of polynomials with coefficients in $Z_2$ and of grade smaller than 3, ...
3
votes
2answers
38 views

Finite field isomorphic to $\mathbb F_{p^n}$.

1) Let $p$ prime and $n\geq 1$ an integer. Show that there is a finite field of order $p^n$ in an algebraic closure $\mathbb F_p^{alg}$ and that all finite field is isomorphic to exactly one field ...
2
votes
1answer
88 views

Is there something similar to $\mathbb{R}^2$ for elliptic curve point representation?

Let $E$ be an elliptic curve over a finite field $\mathbb{F}_p$ and denote with $E(\mathbb{F}_p)$ its set of points over $\mathbb{F}_p$. Consider a coordinate system in $\mathbb{R}^2$. Every point is ...
2
votes
1answer
26 views

If char(K) is prime and $x\longmapsto x^p$ is bijective, then $L/K$ is separable.

Let $K$ a filed of characteristic $p$ a prime and $L/K$ a field extension. If $\varphi:x\longmapsto x^p$ is bijective, then $L/K$ is separable. Q1) First of all, where is $\varphi$ defined ? on $L$ ...
2
votes
1answer
67 views

Sum of eight squares over a finite field.

Consider the split-octonions $\mathbb{O}$ with coefficients in $\mathbb{F}_q$. Suppose $a \in \mathbb{F}_q$ and $b \in \mathbb{F}_q^*$. I want to find the amount of elements $x \in \mathbb{O}$ such ...
0
votes
2answers
18 views

Factorisation of a polynomial in $\left(R\left[x\right],+,\cdot\right)$, $\left(Z\left[x\right],+,\cdot\right)$, …

I am given the following question: "Given a random polynomial in $Z\left[x\right]$. We factorise this polynomial in the polynomial rings $\left(R\left[x\right],+,\cdot\right)$, ...
1
vote
0answers
16 views

solving quadratic equation in GF(2^m)

I am trying to implement Elliptic Curve Cryptography on software in GF(2^m). To do this, I need to be able to solve a quadratic equation, namely $x^2 + x = c$. After a lot of research, I know the ...
0
votes
1answer
48 views

Finite integral domain

I encountered a problem: Every finite integral domain is isomorphic to $ \mathbb{ Z }_{p} $. I know that finite integral domain is isomorphic to a field, but I have no idea on how to construct ...
0
votes
1answer
28 views

What are the roots and conjugates of a minimum polynomial?

I have an exam coming up on coding theory stuff and I'm stumped on how to find the minimum polynomial. A study guide I was given is here: ...
6
votes
1answer
65 views

$SL_2(\mathbb{F})$, decomposing $\mathbb{C}\{X\}$ into irreducible $G$-representations and dimensions

Let $\mathbb{F}$ be a finite field with $q$ elements and $H = \mathbb{F}^\times$, the multiplicative group of $\mathbb{F}$. It is known that $H$ is a cyclic group of order $q - 1$, so $\widehat{H} = ...
0
votes
0answers
43 views

Can $x^{p^n} - x - a$ be factored in a finite field $\mathbb{F}_{p^n}$?

I'm fairly confident that $x^p - x - a$ is irreducible in a field of $\mathbb{F}_p$ when $p$ is prime, but I'm having difficulty extending the argument in a general field of size $p^n$, where $n \ge ...
2
votes
1answer
29 views

Solving linear system over finite field

Suppose I want to solve a linear system $Ax=b$ over some finite field $GF(p)$ where $p$ is prime. If I know the correct solution $x$ for $Ax=b$ over $\mathbb R$, is it true that the answer to the ...
1
vote
1answer
33 views

Show that $\mathbb F_q/\mathbb F_p$ is Galoisienne where $q=p^n$.

Show that $\mathbb F_q/\mathbb F_p$ is Galoisienne where $p$ is prime and $q=p^n$ and find his Galois group. I recall that $\mathbb F_p=\mathbb Z/p\mathbb Z$. I can't find any separable ...
2
votes
0answers
24 views

Question about the nature of a Galois group over 2 successive field extensions

Given finite field extensions $K\subset E \subset F$, let $p\in E[x]$. Given any $\theta\in Gal(F/E)$, I know that $p(\theta(u))=0$ for any root $u$ of $p$ in $E$, i.e., $\theta$ permutes the roots of ...
2
votes
1answer
24 views

Equation $ux^2+vy^2=w$ has at least one solution in $\Bbb{Z}/p\Bbb{Z}.$

Let $p$ a prime number $>2.$ Using a morphism between $\Bbb{Z}/p\Bbb{Z} ^*\to\Bbb{Z}/p\Bbb{Z}^*$ and the fact that it's an abelian group of order $p-1$ and a field, we have $\frac{p+1}{2}$ ...
1
vote
2answers
32 views

Showing that a polynomial is a unit in a quotientring

In this exercise I have a polynomial ring over a finite field $F_2$:$(F_2[X],+,*)$ There is then given an ideal : I $=<X^3+X+1>$. I am then trying to show that $X^2+X+1 + I$ is a unit in ...
2
votes
2answers
89 views

Determine all of the monic irreducible polynomials in $\mathbb Z_3 [x]$ of degree $4.$

Determine all of the monic irreducible polynomials in $\mathbb Z_3 [x]$ of degree $4$. Prove that you have found them all and that the ones you found are irreducible. I am looking for some sort ...
1
vote
1answer
50 views

Orbits of Natural Galois Group Action

Let $m\mid n$ and let $G$ be the Galois group of $\mathbb{F}_{p^n}$ over $\mathbb{F}_{p^m}$. Write $G=\langle \pi^m\rangle$, where $\pi(t)=t^p$ is the Frobenius automorphism. I want to understand the ...
0
votes
2answers
67 views

Show that the only elements equal to their own inverses are $1$ and $p-1$.

Let $p$ be a prime number and $U_p$ be the Abelian group of numbers $\{1, 2, 3, 4, \dots, p-2, p-1\}$ where the binary operation is multiplication $\mod p$. Show that the only elements that are equal ...
2
votes
0answers
48 views

Given the roots of polynomial over finite field, what is the count of its distinct nonzero coefficients?

Let $f(x) = \prod_{i=0}^{n-1}(x - \alpha_i)$ be a polynomial over finite field. Assume there exists $0 \leq j < n$ s.t. $\operatorname{ord}(\alpha_j) > n$. Given only roots $\alpha_i$ being ...
3
votes
2answers
64 views

Solve $ x^2 = 2$ over $ F_5 $.

Since $ F_5 $ is isomorphic to $ \Bbb Z_5 $, I tried to solve this equation over $ \Bbb Z_5 $. Since $ gcd(2,5)=1 $, $ \Bbb Z_5 $ contains a primitive $2$nd root of unity. So if $ \omega $ is the ...
1
vote
0answers
16 views

Euler function for polynomials over finite fields

I need to prove the following result: For a monic polynomial $f \in \mathbb{F}_{q}[x]$, define $$\phi(f) = \# \left(\dfrac{\mathbb{F}_{q}[x]}{f\mathbb{F}_{q}[x]}\right)^*$$ $$N(f) = \# ...
0
votes
1answer
37 views

Prove that for a nonzero element $a$ of a field $F$ with $q$ elements $a^{-1} = a^{q-2}$

This is a statement from "The Linear Algebra a Beginning Graduate Student Ought to Know" by Jonathan S. Golan. Let $F$ be a field having $q$ elements and let $a$ be it's nonzero element. Then $a^{-1} ...