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)

2
votes
1answer
87 views

Showing $x^n=\alpha$ has $n$ solutions in a field extension of degree $n$.

Suppose $F$ is a field of cardinality $q$, and $n$ is an integer such that $n\mid q-1$. Now let $K$ be an extension of degree $n$ over $F$. Why does $x^n=\alpha$ have $n$ solutions in $K$ for any ...
1
vote
2answers
444 views

'shifted' polynomial preserves validity of Eisenstein irreducibility criterion of original, in finite fields?

This is not really research level, but I know not where else to ask it. The Eisenstein criterion for polynomial irreducibility over rationals or integers permits shifting the original (primitive) ...
4
votes
1answer
88 views

number of 1-to-1 linear functions on vectorspaces over finite fields

This is not a homework. I just ask this question myself and thought it would be easy to figure out. But I did not get the solution. Let $\mathbb{F}$ be a finite field with $|\mathbb{F}|=q$. Consider ...
0
votes
2answers
67 views

Structure of the field $\mathbb F_{p^n}(y)$

As the question says , i am confused about the notation above . At first glance it looks like i can compare it with something like $\mathbb R(i)$ . But i am still confused how the field $\mathbb ...
2
votes
1answer
132 views

Products of linearly independent sets in finite fields

Let $\mathbb F_q$ be the finite field with $q$ elements, $q=2^n$. This is a vector space over $\mathbb F_2$. My question is rather general: given two linearly independent sets of vectors of the same ...
2
votes
2answers
193 views

The structure of a vector space

I am stuck reading the proof that the size of every finite field is a power of a prime number, and want to get unstuck. The lecturer's notes are here. On the second page of his notes, he gives the ...
3
votes
1answer
2k views

How to find Matrix Inverse over finite field?

How to find matrix Inverse over finite field? I am using MATLAB, and I know gf() in MATLAB can enable me to do linear algebra operations over finite field $F_{2^m}$ for some m. However, if I want to ...
-1
votes
3answers
438 views

Why a full-rank matrix in a finite field is also full-rank in a expanded finite field?

For example, matrix MAT is full-rank in $GF(2^8)$, why MAT is also full-rank in $GF(2^{16})$ and $GF(2^{32})?$ Thanks
7
votes
1answer
170 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}.$$ ...
3
votes
1answer
147 views

Over which finite fields $x^p-x-b$ is irreducible?

Let $p$ be a prime and $b$ is a non-zero element of the prime field $\mathbb{F}_p$. Then what are the finite fields $\mathbb{F}_q$ of characteristic $p$ over which the trinomial $x^p-x-b$ is ...
5
votes
2answers
197 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 ...
2
votes
1answer
363 views

Questions about a vector space over a finite field with a bilinear symmetric form.

This is an extension of a previously asked question: Inner Product Spaces over Finite Fields. Inner product spaces in the typical undergraduate linear algebra course are stressed to be over ...
2
votes
1answer
315 views

Finding the total number of proper subfield of $F$?

I was thinking about the following problem: Let $F$ be a field with $5^{12}$ elements.Then how can i find the total number of proper subfield of $F$? Can someone point me in the right direction? ...
1
vote
2answers
118 views

This map $f(x)=x^{-1}$ is an automorphism if and only if $F$ has at most four elements

I'm trying to solve this question: If $K$ is a field and $f:K\to K$ is defined by $f(0)=0$ and $f(x)=x^{-1}$ for $x\neq 0$, show $f$ is an automorphism of $K$, if and only if, $K$ has at most ...
1
vote
1answer
221 views

Non-trivial 93rd roots of unity in finite fields [duplicate]

Possible Duplicate: Finding the values of $n$ for which $\mathbb{F}_{5^{n}}$, the finite field with $5^{n}$ elements, contains a non-trivial $93$rd root of unity For which of the following ...
2
votes
3answers
294 views

how to find $|GL_2(F_p)|$

I need to find $|GL_2(F_p)|$, I am very very uncomfortable in counting, so please help here I proceed, $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ be such an invertible matrix, so we need and ...
1
vote
1answer
49 views

$a(x) \bmod m(x)$ for $m(x) > a(x)$?

Suppose we have polynomials over $GF (2^8)$. $a(x) = x^8$. $m(x) =x^8+x^4+x^3+x+1$ A textbook says that. $x^8 \bmod m(x) = [m(x) - x^8]=(x^4+x^3+x+1)$ So I would like to understand, how do we ...
2
votes
0answers
51 views

Different elliptic curves over given $\mathbb{F}_q$ can have different orders?

As the title says: For a given $q \in \mathbb{N}$, in $\mathbb{F}_q$, is it true that different curves on it can have different group orders? I assume yes. Let $q:=5$. Wikipedia gives $9$ points for ...
0
votes
1answer
535 views

Fastest Way to Find order of element in Finite Fields?

Two questions: I use Miller-Rabin to find a prime, p, close to an arbitrary input number (this is very fast). Then I use Floyd's cycle finding algorithm to find the order of a randomly chosen element ...
1
vote
1answer
167 views

Can every periodic binary sequence be expressed as the output of a Linear or Non-Linear Feedback Shift Register?

Quick background: The output of a Linear Feedback Shift Register (LFSR) with $n$ taps is a binary sequence which is periodic of length dividing $2^n-1$. From a mathematical point of view, such a ...
0
votes
1answer
47 views

Multiplication over $F_{2^{31}-1}$ by power of $2$

I'm reading the source code of a stream cypher (zuc): I cannot understand properly why they define the multiplication by power of 2 in this way: ...
1
vote
1answer
102 views

Arbitrary number of algebraically independent elements of prime field: when is that possible?

If we consider the prime field $\mathbb{Q}$, and the field extension $\mathbb{Q}\subseteq\mathbb{C}$, then for any natural $n$ we can find $a_1,...,a_n\in\mathbb{C}$ algebraically independent over ...
1
vote
2answers
362 views

Isomorphism for optimization of GF256 implementation in AES S-Box using intermediary finite fields

I've questions about the implementation of The S-Box in the AES cipher. In this cipher, the Finite Field GF256 is implemented as a quotient $\mathbb{F}_2[X]/(X^8+X^4+X^3+X+1$). The operations can be ...
2
votes
1answer
127 views

Is the modular multiplicative inverse of $a$ equal to that of $-a$?

In javascript, I am implementing Lagrange interpolation over a finite field $GF_p$ for some prime $p$. I only need to compute the value of the $y$-intercept of the Lagrange interpolation polynomial ...
2
votes
2answers
330 views

Generators of Finite Fields and Quadratic Extensions

I want to show that if an element in $\beta \in K$ where $|K|=p^n$ is a generator for $K^*$, i.e. has order $p^n-1$, then there is a generator $\alpha\in L$, $[L,K]=2$ i.e. of order $(p^n)^2-1$, such ...
2
votes
3answers
499 views

Quadratic Extension of Finite field

Suppose $K,L$ are finite fields with $|K|=p^n$ and the $L$ is a quadratic extension over $K$, i.e. $|L| = p^{2n}$. I am trying to show that for any element in the extension $\alpha\in L$ that ...
2
votes
1answer
126 views

Using characters in finite fields to find number of solutions to polynomials.

I am trying to use the theorem below to show that if $d_i=(m_i,p-1)$ then $\sum_ia_ix_i^{m_i}=b$ and $\sum_ia_ix_i^{d_i}=b$ have the same number of solutions. So far, I have been able to prove that if ...
0
votes
1answer
48 views

why using irriducible polinomial for galois field?

To construct the finite field $GF(2^{3})$ we need to choose an irreducible polynomial of degree $3$. Why we should choose an irreducible polynomial? I don't understand this lemma
2
votes
2answers
428 views

arithmetic operations in Galois Field

I didn't undestand how this values, that are values in galois field $GF(2^{3})$. in thes below tables are obtained. Someone could explain me?
0
votes
1answer
245 views

Nonzero trace in finite fields and proving irreducibility.

If we define trace to be $x+x^p+\cdots+x^{p^{n-1}}$. How do we know there is an element of nonzero trace? Clearly if $a\in F_p$ then its trace is zero as $a^{p^i}=a$ so ...
1
vote
1answer
88 views

Show the polynomial $(x-\alpha)(x-\alpha^p)\cdots(x-\alpha^{p^{n-1}})$ is in $F_p[x]$ if $\alpha\in F_{p^n}$

I need help proving that the polynomial $f(x)=(x-\alpha)(x-\alpha^p)\cdots(x-\alpha^{p^{n-1}})$ is in $F_p[x]$ if $\alpha\in F_{p^n}$. This assertion is trivial for $\alpha$ already in $F_p$. So we ...
1
vote
1answer
225 views

Field construction

Explain how to construct a field of order $343$ not using addition and multiplication tables. I understand that every finite field has order $p^n$ for some prime $p$. Since $343$ is $7^3$, let ...
1
vote
2answers
156 views

System of equation over GF(211) (corrected)

I have this system of equation. $a+b+c=171, a+2b+4c = 46, a+3b+9c = 170$. My task is to solve this system over $GF(211)$. Is there any special process? Thanks for advice.
5
votes
1answer
101 views

Irreducible polynomials over $F_q$ with exponents of the form $q^k - 1$.

Let $q$ be some prime power. Is there an explicit family of irreducible polynomials in $F_q[X]$ of the form $\sum_j a_j X^{q^j - 1}$? Thanks!
3
votes
2answers
118 views

Group does not contain any elements of order $p^2$?

I am trying to show that the group of $3 \times 3 $ upper triangular matrices over the field $ \mathbb{F}_p $ with diagonal entries 1 does not contain any elements of order $p^2$ when $ p \geq 3$. ...
0
votes
1answer
157 views

Problem related polynomial ring over finite field of intergers

if $f(x)$ is in $F[x]$. $F$ is field of integer mod $p$. $p$ is prime and $f(x)$ is irreducible over $F$ of degree $n$ . prove that $F[x]/(f(x))$ is a field with $p^n$ elements.
0
votes
1answer
139 views

Prove that there are $p+1$ points on the elliptic curve $y^2 = x^3 + 1$ over $\mathbb{F}_p$, where $p > 3$ is a prime such that $p \equiv 2 \pmod 3$.

Let $p > 3$ be a prime such that $p \equiv 2 \pmod 3$. Define the elliptic curve $E$ over $\mathbb{F}_p$ by $y^2 = x^3 + 1$. Prove that $E(\mathbb{F}_p)$ consists of $p+1$ points. Using Fermat's ...
1
vote
2answers
75 views

Find the inverse of $\alpha^{38}$ in $\mathbb F = \mathbb Z_2[x]/\left<x^4+x+1\right>$

Let $\alpha$ be a root of $x^4+x+1$ and we are given some powers of $\alpha$ as linear combinations of $1,\alpha,\alpha^2$ and $\alpha^3$ $\alpha^4=\alpha+1$ $\alpha^5=\alpha^2+\alpha$ ... (the rest ...
2
votes
2answers
115 views

Encode the message $[1,1,0,1,1,0,1]$ in BCH code based on the field $\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1}$

So here's what I understand so far: $\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1} = GF(16)$ The code is written as $[x^{14},x^{13},x^{12},x^{11},x^{10},x^{9},x^{8}$ $|$ ...
1
vote
2answers
63 views

Express each power of the root $\alpha$ of $\frac{\mathbb Z_2[x]}{\langle x^3+x^2+1\rangle}$ as linear combinations of $1, \alpha$ and $\alpha^2$

There are $8$ elements in $\frac{\mathbb Z_2[x]}{\langle x^3+x^2+1\rangle} = GF(8)$ and this generates the set $\{0,1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1\}$ We're required to express $\alpha^1$ all the ...
1
vote
1answer
252 views

A Finite Field of Order $125$ has a Subfield of order $25$?

How to prove that every finite field of order $125$ has a subfield of order $25$. In general what is the strategy to attack such kind of problems?
0
votes
1answer
471 views

Finite Fields of Order 3

I have been trying to learn Real Analysis, though I'm having trouble with a problem. Show that there exists one and (essentially) only one field with three elements. Any help will be appreciated.
6
votes
1answer
200 views

factorization of the cyclotomic $\Phi_n(x)$ over $\Bbb F_p$

One can prove that the $\Phi_n(x)$ are irreducible over $\Bbb Z$. Where $\Phi_n(x)=\prod _{(a,n)=1}\zeta_n^a$ (i.e the product of the primitive n-rooth of unity). I want to find a factorization of ...
0
votes
1answer
27 views

Showing that the oder of the group and all the element is the same.

If $f=x^n-1 \in K[x]$, $L$ splitting field of $f$ and $\gamma\in L$ the generator of $H= \{\alpha \in L \mid \alpha^n=1\} , m=|H|$, how can I show that $m|n$, should it depend on the characteristic ...
1
vote
2answers
60 views

Ideals of the ring $\mathbb{F}_q[X]/(X^n-1)$

I need little help in proving the following result : Consider the ring $R:=\mathbb{F}_q[X]/(X^n-1)$, where $\mathbb{F}_q$ is a finite field of cardinality $q$ and $n\in\mathbb{N}$. Then any ideal $I$ ...
1
vote
1answer
259 views

LFSR (Linear Feedback Shift Register)

Given polynomial $P(x)=x^6+x^3+1$ belonging to $\mathbb{Z}_2[x]$. Build an $LFSR$ corresponding to $P(x)$. Then find the maximal period of its output sequence and the initial state that could lead to ...
1
vote
2answers
143 views

Showing that Trace($ax$) = $0$ for all $x$ in field $F$ of order $2^N$ implies $a = 0$.

How can I show that Trace $(ax) = 0$ implies that $a = 0$ in a field $F$ (over F2) of order $2^N$? I get that I can something like the following: Trace($ax_1)=$ Trace($ax_2$) $\implies$ ...
1
vote
1answer
210 views

A question on the irreducible divisors and splitting field of $x^{p^n} - x\in \mathbb F_p[x]$.

I need to prove that any irreducible polynomial $f$ of degree $d\,\big|\,n$ over $\mathbb F_p$ devides $x^{p^n} - x$. I know that the splitting field of the latter is the finite field with $p^n$ ...
2
votes
1answer
2k views

How do i calculate a multiplication table for GF(8)?

Could you please provide the steps involved in calculating a multiplication table for GF(8)?
3
votes
3answers
1k views

Characterization of irreducible polynomials over finite fields

How much is known about irreducible polynomials over finite fields? I have seen the formula (a result of Möbius inversion) that gives the number of such polynomials, but I am looking for something ...