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

5
votes
1answer
171 views

Discrete logarithm tables for the fields $\Bbb{F}_8$ and $\Bbb{F}_{16}$.

The smallest non-trivial finite field of characteristic two is $$ \Bbb{F}_4=\{0,1,\beta,\beta+1=\beta^2\}, $$ where $\beta$ and $\beta+1$ are primitive cubic roots of unity, and zeros of the ...
16
votes
2answers
4k views

Number of monic irreducible polynomials of 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$ can exist over $F$? Thanks!
5
votes
2answers
5k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
10
votes
1answer
1k views

Order of finite fields is $p^n$

Let $F$ be a finite field. .How do I prove that the order of $F$ is always of order $p^n$ where $p$ is prime?
7
votes
2answers
2k views

reducible polynomial 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 $\mod 2 $, $x^4+1=(x+1)^4$ . Also $\mod 3$,we have that $0,1,2$ are not ...
7
votes
2answers
635 views

Is there anything like GF(6)?

Are there any galois fields which consist of product of two primes, as in GF(2*3) = GF(6)?
1
vote
1answer
784 views

Irreducible representations of a cyclic group over a field of prime order

Consider $G$ a cyclic group of order $n$ with prime $p\not|n$. How do I construct all the irreducible representations over $\mathbb F_p$? How many irreducible representations are there and what are ...
23
votes
2answers
1k 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 ...
15
votes
3answers
1k views

Inner Product Spaces over Finite Fields

Inner product spaces are defined over a field $\mathbb{F}$ which is either $\mathbb{R}$ or $\mathbb{C}$. I want to know what happens if we try to define them over some finite field. Here's an ...
8
votes
2answers
166 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 ...
5
votes
1answer
1k 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 in ${\mathbb{F}_p}$ only when $n=1$ or $n=p=2$? Thanks in advance. It bothers me for ...
4
votes
3answers
147 views

Why must a field with a cyclic group of units be finite?

Let $F$ be a field and $F^* \subseteq F$ be its group of units. If $F^*$ is cyclic show that $F$ is finite. I'm a bit stuck. I know that I can represent $F^* = \langle u \rangle$ for some $u \in F^*$ ...
7
votes
1answer
388 views

Lack of understanding of the proof of the existence of an irreducible polynomial of any degree $n \geq 2$ in $\mathbb{Z}_p[x]$

In an optional course called "Finite Geometries", we most recently constructed the fields $$K_{p,n}[x] := \{\alpha \in K_p[x]\,| \deg(\alpha) < n\},$$ where $K = \mathbb{Z}$, $p$ is prime and $n ...
2
votes
2answers
370 views

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 values of $n$, does the finite field $\mathbb{F}_{5^{n}}$ with $5^{n}$ elements contain a non-trivial $93$rd root of unity? I don't know how to find the value of $n$.
5
votes
3answers
527 views

Roots of an irreducible polynomial in a finite field

Given a irreducible polynomial $f \in K[x]$ where $|K|=q$ is a finite field and $\deg(f)=n$. If $\alpha$ is a root of $f$ why are $\alpha, \alpha^q, \dots, \alpha^{q^{n-1}}$ the only possible ...
2
votes
2answers
1k views

Irreducible polynomial of $\mathrm{GF}(2^{16})$

I'm implementing some code for the Galois field $\mathrm{GF}(2^{16})$. Which irreducible polynomial do you recommend that I use?
15
votes
5answers
1k 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 ...
8
votes
4answers
821 views

Explicit examples of infinitely many irreducible polynomials in k[x]

My question is the following. Is it possible to give examples of infinitely many irreducible polynomials in a polynomial ring $k[x]$ with $k$ a field? I'm interested in this because I'm ...
6
votes
4answers
1k views

Do finite algebraically closed fields exist?

Let $K$ be an algebraically closed field ($\operatorname{char}K=p$). Denote $${\mathbb F}_{p^n}=\{x\in K\mid x^{p^n}-x=0\}.$$ It's easy to prove that ${\mathbb F}_{p^n}$ consists of exactly $p^n$ ...
6
votes
1answer
365 views

Irreducible cyclotomic polynomial

I want to know if there is a way to decide if a cyclotomic polynomial is irreducible over a field $\mathbb{F}_q$?
10
votes
4answers
279 views

Number of solutions of $x^2_1+\dots+x^2_n=0,$ $x_i\in \Bbb{F}_q.$

Let $\mathbb F$ be field with $q$ element and $\operatorname{char}(\mathbb F)\neq2$. I want to know about the number of solutions of this equation: $$x^2_1+x^2_2+\dots+x^2_n=0 \text{ where } x_i\in ...
4
votes
2answers
2k 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 ...
2
votes
1answer
186 views

Transition between field representation

In a number of papers related to efficient implementation of the AES Sbox, people are computing stuff (the multiplicative inverse for instance) in GF(($2^4$)$^2$) instead of GF($2^8$). In some cases ...
1
vote
0answers
82 views

Rank of Quadratic Form

Let $n,m, s \in \mathbb{Z}$ be integers satisying $n=s^2$ and $m=2n$. Let $\newcommand{\bigmatrix}[1]{ \begin{pmatrix} #1_1 & #1_2 & \cdots & #1_s \\ #1_{s+1} & #1_{s+2} & \cdots ...
8
votes
4answers
568 views

Why is the product of all units of a finite field equal to $-1$?

Suppose $F=\{0,a_1,\dots,a_{q-1}\}$ is a finite field with $q=p^n$ elements. I'm curious, why is the product of all elements of $F^\ast$ equal to $-1$? I know that $F^\ast$ is cyclic, say generated by ...
7
votes
2answers
245 views

Exponent of $GL(n,q)$.

Another exponent problem. $GL(n,q)$ is the group of invertible $n\times n$ matrices over the finite field $GF(q)$, where $q$ is a prime power. I am trying to figure out the exponent of this group. ...
7
votes
1answer
1k views

Existence of irreducible polynomials over finite field

Let $F$ be a finite field. How do we prove that for each $n \in \mathbb{N}$ there is an irreducible polynomial of degree $n$? One can assume that $F = \mathbb{F}_{p^m}$ where $p$ is prime. If $n \ge ...
6
votes
1answer
1k views

Splitting fields of polynomials over finite fields

I can't follow a statement in my notes: "Let $K$ be a finite field, with $f \in K[X]$ an irreducible polynomial of degree $d$. Then any finite extension $L/K$ is normal, and so if $L$ contains one ...
5
votes
1answer
298 views

Irreducible factors of $X^p-1$ in $(\mathbb{Z}/q \mathbb{Z})[X]$

Is it possible to determine how many irreducible factors $X^p-1$ in the polynomial ring $(\mathbb{Z}/q \mathbb{Z})[X]$ has and maybe even the degrees of the irreducible factors? ($p,q$ are a primes ...
4
votes
2answers
770 views

Factorize polynomial over $GF(3)$

I want to factorize $x^{11}-1$ over $GF(3)$ but I'm stuck at $(x-1)(x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1).$ I have tried to do it trial and error but failed. Is $$ ...
3
votes
2answers
757 views

Galois Field Fourier Transform

there are two definitions for Reed-Solomon codes, as transmitting points and as BCH code ( http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction ). On Wikipedia there is written that we ...
5
votes
3answers
158 views

Is the splitting field equal to the quotient $k[x]/(f(x))$ for finite fields?

maybe that's an idiot question. Given a finite field $k$ and some irreducible polynomial $f(x) \in k[x]$, then $k_f \cong k[x]/(f(x))$? I know that it's true if $k$ is the prime field and I think that ...
3
votes
4answers
4k views

Finding inverse of polynomial in a field

I'm having trouble with the procedure to find an inverse of a polynomial in a field. For example, take: In $\frac{\mathbb{Z}_3[x]}{m(x)}$, where $m(x) = x^3 + 2x +1$, find the inverse of $x^2 + ...
0
votes
1answer
26 views

Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...
6
votes
2answers
384 views

Are quartic minimal polynomials over $\mathbb{Q}$ always reducible over $\mathbb{F}_p$?

This situation arose while studying biquadratic extensions. Let $\mathbb{Q}(\alpha)$ is some biquadratic extension, with $m(x)$ the minimal polynomial of $\alpha$. Suppose that ...
4
votes
4answers
3k views

Can you construct a field with 4 elements?

Can you construct a field with 4 elements? can you help me think of any examples?
10
votes
1answer
703 views

On the order of elements of $GL(2,q)$?

There's a particular property of the elements of $GL(2,q)$, the general linear group of $n\times n$ matrices over a finite field of order $q$, that I don't understand. First, I know that the order of ...
7
votes
2answers
4k views

Finding irreducible polynomials over GF(2) with the fewest terms

I'm investigating an idea in cryptography that requires irreducible polynomials with coefficients of either 0 or 1 (e.g. over GF[2]). Essentially I am mapping bytes to polynomials. For this reason, ...
1
vote
2answers
738 views

Constructing Isomorphism between finite field

Consider $\mathbb{F}_3(\alpha)$ where $\alpha^3 - \alpha +1 = 0$ and $\mathbb{F}_3(\beta)$ where $\beta^3 - \beta^2 +1 =0$. I know these two fields are isomorphic but I have difficulty buliding an ...
5
votes
1answer
183 views

UPDATE: How to find the order of elliptic curve over finite field extension

I want to find the order of elliptic curve over the finite field extension $\mathbb{F}_{p^2}$, where $E(\mathbb{F}_{p^2}):y^2=x^3+ax+b $ I am using the method illustrated by John J. McGee in his ...
5
votes
3answers
457 views

Other ways to deduce Cyclicity of the Units of certain groups?

The group of units of the rings $\text{GF}(p^r)$ and $\mathbb{Z}/p^r\mathbb{Z}$ are both cyclic (except for the exception of prime powers are not cyclic when $p=2$ and $r\ge 3$). This is a strong ...
3
votes
1answer
216 views

Irreducible factors for $x^q-x-a$ in $\mathbb{F}_p$.

If $\mathbb{F}_q$ is a finite field with $q=p^m$ elements where $p$ is prime, if $a\in\mathbb{F}_p^\times$, ¿Which are the irreducible factors of $f_a=x^q-x-a$ ? Attempt: If $\alpha$ is a root for ...
3
votes
3answers
678 views

Primitive polynomials of finite fields

there are two primitive polynomials which I can use to construct $GF(2^3)=GF(8)$: $p_1(x) = x^3+x+1$ $p_2(x) = x^3+x^2+1$ $GF(8)$ created with $p_1(x)$: 0 1 $\alpha$ $\alpha^2$ $\alpha^3 = ...
1
vote
1answer
802 views

Question about LFSR

I am reading a paper and say this "The idea is to load $f(X)$ into LFSR to multiply by $X$ mod $g(X)$(primitive polynomial deg $g=n$). We next compute a polynomial h(X) whose coefficients are given ...
4
votes
1answer
215 views

Elements of $\mathbb{F}_p$ having cube roots in $\mathbb{F}_p$

Let $p$ be a prime number, and let $\mathbb{F}_p$ be the field with $p$ elements. How many elements of $\mathbb{F}_p$ have cube roots in $\mathbb{F}_p$? I had this question on an exam and after ...
3
votes
1answer
895 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 ...
2
votes
2answers
77 views

How hard is finding values such that

We can work with powers of some naturals $(x_k)^{m_k}$. Here we have $n$ naturals, and $m_k$ is an integer in the range $-r$ to $r$. My question is, how small can $p$ be so that ...
2
votes
1answer
86 views

Number of points on $Y^2 = X^3 + A$ over $\mathbb{F}_p$

Let $p\equiv 2\pmod{3}$ be prime and let $A\in\mathbb{F}^{∗}_p$ . Show that the number of points (including the point at infinity) on the curve $Y^2 = X^ 3 + A$ over $\mathbb{F}_ p$ is exactly $p + 1$ ...
2
votes
3answers
1k views

Explicit construction of a finite field with $8$ elements

Give an explicit contruction of the finite field $K$ containing $8$ elements, as a quotient of an appropriate polynomial ring. Include the multiplication table of the group $K^{*}=K\setminus ...
1
vote
2answers
292 views

Roots of polynomials over finite fields

I've been trying to find the decomposition of $x^2-2$ to irreducible polynomials over $\mathbf{F}_5$ and $\mathbf{F}_7$. I know that for some $a$ in $\mathbf{F}_5$ (for example), $x-a$ divides $x^2-2$ ...