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)

8
votes
4answers
924 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 ...
0
votes
1answer
413 views

Nilpotent matrices over finite fields

What sort of criterion is there for determining whether a matrix is nilpotent? Specifically, I'm interested in the nilpotent matrices over finite fields. I realize that any such matrix will have to ...
1
vote
1answer
73 views

Variation over univariate Schwartz–Zippel lemma

Let $n\in\mathbb{N}$ and let $q\in[n,2n]$ be a prime number. In addition, let $s,s':\mathbb{F}_q\to\mathbb{F}_q$ be polynomials of degree $\sqrt{n}$ such that $s\neq s'$. From the ...
2
votes
1answer
93 views

Extending a boolean function to a finite field

Let $f:\{1,2,\ldots,n\}\to\{-1,1\}$ be a boolean function. Can I extend $f$ to a polynomial of degree at most $n$ over $\mathbb{F}_q$, where $q\in[n,2n]$ is a prime number. i.e., is there a ...
0
votes
2answers
259 views

Real norms on vector spaces over finite fields

I am interested in functions of the form $\psi: F^n \to \mathbb{R}^+$, where $F$ is a finite field, that have norm-like properties, e.g., $\psi(x+y) \le \psi(x) + \psi(y)$. Does anybody know if there ...
2
votes
1answer
306 views

What happens when you mod out by a non-primitive irreducible polynomial over $F_q$?

What is the difference between modding out by a primitive polynomial and modding out by a non-primitive irreducible polynomial in a finite field $F_q$? From what I understand either one should ...
1
vote
2answers
305 views

Generators of the multiplicative group of GF(2)

GF(3) can be constructed as follows by polynomial $p(x)=x+1$: $0=0$ $1=1$ $\alpha=2$ GF(5) can be constructed as follows by polynomial $p(x)=x+2$: $0=0$ $1=1$ $\alpha=3$ ...
2
votes
3answers
166 views

Some iterate of a linear operator over $\mathbf F_q$ is a projection

If $T$ is an endomorphism of a finite-dimensional vector space $V$ over a finite field, then how can I show that there exists a positive integer $r$ such that $T^r$ is a projection operator?
5
votes
3answers
308 views

Roots of $x^2 + 2x + 2$

I'm trying to show that there are infinitely many values of $p$ such that $x^2 + 2x + 2$ has no roots over $\mathbb{F}_p$. Is this easily solvable? (I kind of came up with it myself so I don't ...
1
vote
1answer
644 views

Derivative of polynomial in GF(9)

I'd like to calculate derivative of polynomial in $GF(9)\equiv GF(3^2)$. For polynomials in fields of characteristic of $2$ it is quite easy, because operations are modulo 2 which means that there are ...
7
votes
2answers
1k views

Two finite fields with the same number of elements are isomorphic

Fraleigh(7ed) Theorem33.12. Let $p$ be a prime and let $n\in\mathbb{Z}^+$. If $E$ and $E'$ are fields of order $p^n$, then $E \simeq E'$. Proof in the text: Both $E$ and $E'$ have ...
7
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$ ...
0
votes
1answer
420 views

How many orthogonal matrices are there over a given finite ring or field?

I want to know how many $2\times 2$ orthogonal matrices exist over the ring $\mathbb{Z}_n$ or the field $\mathbf{F}_p$. And how many $2\times 1$ orthogonal vectors exist over the ring $\mathbb{Z}_n$ ...
5
votes
1answer
372 views

Find the isomorphism between two table representations of the same finite field

I am given two multiplication and addition tables for a finite field (i.e. the tables are for different naming of the elements of the field) and I want to find the isomorphism between the two ...
2
votes
3answers
179 views

Multiplicative inverses for elements in field

How to compute multiplicative inverses for elements in any simple (not extended) finite field? I mean an algorithm which can be implemented in software.
7
votes
2answers
737 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)?
2
votes
1answer
86 views

Distinguishing vector distributions induced by polynomials

I am given two sequences of multivariate polynomials $\overline{p}=(p_1,p_2,\dots,p_k)$ and $\overline{q}=(q_1,q_2,\dots,q_k)$, all of them on the variables $x_1,\dots,x_n$ over some finite field ...
2
votes
1answer
100 views

Independence of Roots

Let $f \in F_p[x]$ be an irreducible polynomial of degree $n$, where $p$ is prime. Prove that its roots are independent over $F_p$. EDIT: It was pointed in the answers that this claim is true only ...
4
votes
2answers
745 views

Degree of splitting field of $x^6-3$ over $\mathbb{Q}((-3)^{1/2})$ and also over $\mathbb{F}_5$

I am trying to find the degree of the splitting field of this polynomial over these two fields. For the degree over $\mathbb{Q}((-3)^{1/2})$ I got 3. I am pretty sure this is correct. For ...
11
votes
1answer
342 views

Constructing a finite field

I'm looking for constructive ways to obtain finite fields, for any given size $q=p^n$. For example, I know it suffices to find an irreducible polynomial of degree $n$ over $\mathbb{Z}_p$ (and then ...
5
votes
2answers
349 views

Factoring $X^{16}+X$ over $\mathbb{F}_2$

I just asked wolframalpha to factor $X^{16}+X$ over $\mathbb{F}_2$. The normal factorization is $$ X(X+1)(X^2-X+1)(X^4-X^3+X^2-X+1)(X^8+X^7-X^5-X^4-X^3+X+1) $$ and over $GF(2)$ it is $$ ...
7
votes
3answers
566 views

Intuition regarding Chevalley-Warning Theorem

Three versions of the theorem are stated on pages 1-2 in these notes by Pete L. Clark: http://math.uga.edu/~pete/4400ChevalleyWarning.pdf Could anyone offer some intuitive way to think about this ...
3
votes
2answers
165 views

Number of fields with characteristic of 3 and less than 10000 elements?

it's exam time again over here and I'm currently doing some last preparations for our math exam that is up in two weeks. I previously thought that I was prepared quite well since I've gone through a ...
6
votes
0answers
448 views

Hardness of finding eigenvalues over finite fields

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?) How ...
16
votes
3answers
2k 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 ...
1
vote
1answer
163 views

How to nicely extend finite field?

I'm working on an implementation of Miller's algorithm that computes the Weil pairing (elliptic curves, cryptography). In order to do that, I have to implement finite fields. So far I have managed to ...
1
vote
1answer
110 views

Mathematical names of the sets and elements of standard computer numbers

In standard computer arithmetic, there are two sets of numbers. N-bit unsigned numbers. The elements are natural numbers in $(0, 2^N]$. Arithmetic operations is defined as for the natural numbers ...
5
votes
2answers
1k views

Finite fields as vector spaces

I'm having great difficulty understanding this topic. Can someone concretely explain what it is meant by thinking of $GF(q^2)$ ($q$ a prime power) as a two-dimensional vector space over its subfield ...
4
votes
4answers
4k 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?
1
vote
1answer
171 views

Uniqueness and Equations of Tangent Lines in a Finite Projective Plane

I'm trying to follow a proof of Segre's Theorem, and I'm unsure of how some of the results are obtained. In $PG(2,q)$, $q$ odd, we have an oval ($q+1$ points, no three collinear). We pick $3$ of ...
17
votes
2answers
5k 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!
4
votes
2answers
823 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 ...
0
votes
2answers
90 views

Binomial formula in $GF(2^m)$

there is a binomial formula: $$(x+y)^n=\displaystyle\sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$$ When operations are done in $GF(2^m)$ then all positive integers are reduced $\bmod2$, so binomial formula ...
3
votes
3answers
737 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 = ...
0
votes
1answer
80 views

Field extension

there is for example field $GF(2^4)=GF(16)$. Is $GF(16)$ a subfield of itself? Following this definition http://mathworld.wolfram.com/Subfield.html there is nothing written that subfield must contain ...
1
vote
1answer
263 views

Can a primitive root of a polynomial over $GF(2)$ ever not generate a multiplicative group?

Can a primitive root of a polynomial over $GF(2)$ ever not generate a multiplicative group? I have some notes from my review of finite field extensions a while ago that I've been rereading. It's the ...
-1
votes
1answer
184 views

Finite extension of $\mathbb Q_p$

Let $\mathbb K/\mathbb Q_p$ be a finite extension of $p-$adic field $\mathbb Q_p$. Let ${\mathcal O}=\{x\in K\;:\;|x|\leq1\}$ and ${\mathcal P}=\{x\in K:\;|x|<1\}$, here $|\cdot|$ is the absolute ...
2
votes
1answer
387 views

The field of Laurent series on finite fields

Well, it is hard to find a good references on The field of Laurent series on finite fields. Let $F_q$ be any finite field, and denote $F_q((t))$ is the field of Laurent series on $F_q$. Please show ...
1
vote
1answer
321 views

Numbers of vectors in a vector space over a finite field, with different multiplication

I had a recent question in an assignment that I couldn't complete. We are given the following: $q$ is an odd prime power. $(F,+,\cdot)=\text{GF}\left(q^2\right)$. $K$ is the $q$ element subfield of ...
5
votes
1answer
978 views

primitive root of a finite field

This is a problem similar to one of my homework problems, but not on the homework. The problem states that: Find a primitive root $\beta$ of $F_2[x]/(x^4+x^3+x^2+x+1)$. Questions: I know what a ...
3
votes
1answer
345 views

meaning of $GF(2)[x]/(x^3-1)$

What does $GF(2)[x]/(x^3-1)$ mean? I know $GF(2)$ is the Galois field with 2 elements, but what does the forward slash mean? Also, what's the meaning of the entire expression? Thanks!
4
votes
2answers
1k views

Field Norm Surjective for Finite Extensions of $\mathbb{F}_{p^k}$

I'd rather not have the answer, because I feel like this should be a relatively easy question, and I'm just missing some key step, but could anyone give me a hint on showing that the norm (defined as ...
2
votes
2answers
920 views

Subtraction and division with integers modulo 3

(The integers modulo 3) permit unrestricted subtraction (so that, for example, $1-2=2$), and they permit division restricted only by the exclusion of the denominator 0 (so that, for example, ...
2
votes
0answers
95 views

What's the fastest way to solve these equations with powers in a field?

This is for an algorithm I'm working on. Perhaps we can work together! We can consider the integers modulo a prime $p$. They form a field with arithmetic operations modulo $p$. I'd like to find ...
5
votes
2answers
244 views

For which prime $p$ are the additive groups $\mathbb{F}_p$ and $\mathbb{F}_p^2$ $\mathbb{Z}[i]$-modules?

Homework for my algebra class. Chapter 14, Exercise 7.8 in Artin's Algebra, Second Edition: Let $F = \mathbb{F}_p$. For which prime integers $p$ does the additive group $F^1$ have a structure ...
2
votes
1answer
256 views

If $[F : F_p] = n$, does $F$ have $p^n$ elements?

If $[F : F_p] = n$, does $F$ have $p^n$ elements? My book seems to be implying that this is true but I'm not sure why. Thanks!
4
votes
2answers
303 views

Irreducible polynomials

What is the number of irreducible polynomials, $p(x)$, of degree $2$ over $F_q$, $q=p^n$?
18
votes
5answers
2k views

Every Function in a Finite Field is a Polynomial Function

From a bank of past master's exams I am going through: Let $F$ be a finite field. Show that any function from $F$ to $F$ is a polynomial function. I know that finite fields are fields of $p$ ...
1
vote
1answer
64 views

Multiplying matrix by random vectors in $\mathbb{Z}_2$

Is it correct that for any uniformly, independently chosen vectors $r,s \in \mathbb{Z}_2^m$ and for any $0 \neq D \in \mathbb{Z}_2^{m \times m}$, we have that $Pr_{r,s}\left[r^T\cdot D \cdot s \neq 0 ...
5
votes
3answers
499 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 ...