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)

29
votes
2answers
8k 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$ do exist over $F$? Thanks!
0
votes
1answer
52 views

Odd degree of extension field in Couveignes Square root method

I was reading the Couveignes method to find square root for Number Field Sieve(reference here page 4 first line). It says that for this method the degree of extension K/Q must be odd so that Norm(-x)=-...
1
vote
3answers
76 views

What is the meaning of $\Bbb{Q}[x]/f(x)$?

I am very confused with the meaning of $\Bbb{Q}(x)/f(x)$. Does it mean the set of all polynomials modulo $f(x)$? If it does then how can we say that $\Bbb{R}[x]/(x^2+1)$ is isomorphic to set of ...
0
votes
0answers
50 views

Sum of the divisors of polynomials in $\mathbb{Z}_2[x]$

Let $A$ be a polynomial in $\mathbb{Z}_2[x]$ and $\sigma(A)$ denote the sum of divisors of $A$. Let $A=x^h(x+1)^kP^lQ^{2n-1}$, where $P,Q$ are irreducible polynomials with degree $\geq 2$, $l\neq 2^r-...
1
vote
1answer
46 views

A question on finite fields.

Suppose you have a finite field $\mathbb{F}$, where $|\mathbb{F}|=p^n$ and $p$ is a prime number. Also suppose that $f(x)=x^2+b\in \mathbb{F}[x]$ is an irreducible polynomial over $\mathbb{F}$ and $r$ ...
2
votes
2answers
33 views

Construction of field extension for $[E:\mathbb F_{11}]=3$

Let $\mathbb F_{11}\subset E$. Construct a field extension $E$ of $\Bbb{F}_{11}$ such that $[E:\mathbb F_{11}]=3$ Answer: Let $f(x)=x^3+1 $ be a polynomial in $\mathbb F_{11}[x]$ with $deg(f)=3$. ...
-2
votes
1answer
25 views

Field extension $\mathbb F_p\subset E$ [on hold]

Suppose there exists a field extension $\mathbb F_p\subset E$. Question: Is it possible that the degree is $[E:\mathbb F_p]=2$. And how many elemnts are in E then? How can I proof such a question?...
2
votes
0answers
38 views

Probability that vectors in two GF($q=2^s$) linear spaces sum to zero

This is a simplified version of a more general question. Assume we have two GF($q=2^s$) matrices $A_1$ and $A_2$, of dimensions $m \times n_1$ and $m \times n_2$ ($n_2 \ge n_1$), respectively. For ...
1
vote
0answers
47 views

Finding square root of polynomial in extension field (Number field sieve)

I was reading this paper, on page number 29, 2nd paragraph it is written that "take the coefficients of $ \gamma $ modulo q and applying an algorithm for taking square roots in the finite field Z[ $ \...
0
votes
0answers
47 views

Geometric and arithmetic Frobenius

I read in Serre's "Lectures on $N_X(p)$" that when $X$ is a scheme defined over $\mathbb{F}_q$ (a finite field), the geometric Frobenius $F: X \mapsto X$ is defined by fixing every element of the ...
4
votes
4answers
80 views

Show that $\mathbb{F}_9 \not \subset \mathbb{F}_{27}$

The usual answer will go like this: Since $2 \not | \ 3$ and $\mathbb{F}_{p^r} \subset \mathbb{F}_{p^s}$ if and only if $r | s$, then $\mathbb{F}_9 \not\subset \mathbb{F}_{27}$. However, I'm ...
6
votes
4answers
76 views

Is $\mathbb{Z}_p$ a field? (p prime)

I was wondering if $\mathbb{Z}_p$ ($p$ prime) was a field, because in some notes I read there's written that $\mathbb{F}_p = \mathbb{Z}_p = \mathbb{Z}/p\mathbb{Z}$ is a "prime subfield" But I was ...
1
vote
2answers
37 views

irreducibility of a bivariate polyonimal over a finite field

Let $\mathbb{F}_q$ be the finite field with $q$ elements. Consider the bivariate polynomial $$P(x,y)=y^2- x(x-1)(x-a)(x-b),$$ where $a\neq b$, and $a,b \neq 0,1$ are some arbitrary elements of $\...
7
votes
1answer
67 views

Number of even irreducible monic polynomials of a given degree over a finite field

It is well-known that the number of irreducible monic polynomials of degree $n$ over the finite field of $q$ elements is given by the formula $$\frac{1}{n}\sum_{d\mid n}\mu\left(\frac{n}{d}\right)q^{d}...
0
votes
0answers
55 views

Examples of irreducible polynomials over a finite field with prescribed coefficients [on hold]

I came to know that it is an open problem, but I am not able to find any simple example to explain it properly. Can some one help me with some simple explanation regarding what this problem is about?...
-3
votes
1answer
37 views

Irreducible polynomial on $\mathbb{Z}_2$-field

I've found a theorem in the book "Linear Groups" (Dickson, 1901, p.16.): "In $\mathbb{Z}_2$, the degrees of the irreducible divisors of $x^{2^m}-x$ are divisors of $m$." I've read the prove in this ...
4
votes
1answer
31 views

Characterising maximal ideals in $\mathbb F_p[x]$, $\mathbb Z[x]$

I'm interested in characterising maximal ideals in $\mathbb F_p[x,y]$. More precisely, my problem is: Find all possible cardinalities for fields of the kind $A/I$, where $A=\mathbb Z[x,y]/(x^2+y^2)...
1
vote
1answer
50 views

Primes is in P, proof of hendrik Lenstra Jr. lemma

In the paper describing AKS primality test : http://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf On page no. 8 Lemma 4.7 last paragraph, I cannot understand how number of ...
0
votes
2answers
44 views

Why $\mathbb{Z}_p$ can't have proper subfields?

From the notes I'm studying from I read that " $\mathbb{Z}_p=\mathbb{F}_p$ has no proper subfield." The rationale is: "assuming $\mathbb{K}$ is a subfield of a finite field $\mathbb{Z}_p= \mathbb{F}...
1
vote
0answers
22 views

Find the condition of $h$ satisfy $x^3+1$ divides $x^{2h+1}+1$ over $\mathbb{Z}_2$.

Find the condition of $h$ satisfy $x^3+1$ divides $x^{2h+1}+1$ over $\mathbb{Z}_2$ and find the quotient polynomial. (Sorry for my bad English)
1
vote
2answers
57 views

What happens if I take a quotient over a reducible polynomial?

I know that for adjoinging roots to a field, I need to find irreducible polynomials so that the ideal I am taking the quotion with will be maximal, hence the resut being a field. Imagine I am working ...
1
vote
1answer
47 views

prove that $x^{2\cdot 3^n}+x^{3^n}+1$ is not primitive (mod 2)

I'm new to the finite field theory, however after doing some trivial search on primitive polynomials, It seems that there are no primitive polynomial of the form $$x^{2k}+x^{k}+1\quad k>1$$ and I'...
1
vote
0answers
38 views

Hasse-Weil bound for even degree polynomial

Consider the equation $y^2 = f(x)$, in the finite field $\mathbb{F}_q$($q$ is a prime power) where $f(\cdot)$ is a monic polynoimal of even degree (greater than or equal to $4$) with integer ...
2
votes
2answers
104 views

Field extensions and monomorphisms

I am working through some algebra exercises and got stuck with the following problem: I am working in the finite field $\mathbb{Z}_5$. Let $f \in \mathbb{Z}_5[x]$ and $f(x) = x^2 + 2$. By simple ...
4
votes
3answers
90 views

Factorization of polynomials over $\mathbb{Z}_3$

I have been given these two polynomials $$f(t)=t^3+2t+1 \text{ & }g(t)=t^3+t^2-t+2$$ the problem says, decide if both factorization fields are isomorphic. For the second polynomial I got that $$g(...
1
vote
0answers
54 views

Simplification of a double summation in a polynomial ring over a finite field

I am looking out to simplify the following double summation in $\mathbb{F}_q[x_1,x_2]$, where $p$ is a prime and $q=p^k$ for some positive integer $k$ and a positive integer $r$ such that $0 \leq r \...
1
vote
2answers
38 views

Reducibility of $x^q -x -1$ in $\mathbb{F}_{q}$

I came across the following excercise and do not know how to go about this. Given the polynomial $x^q -x -1$ in $\mathbb{F}_{q}$. Consider $q=8$. Show this polynomial is reducible by considering an ...
1
vote
0answers
24 views

Irreducible polynomial of every degree over finite field

The existence of polynomials in title has been asked as a problem on MathStack many times; some answers were using existence of finite bigger fields, and some answers concern Mobius function with ...
2
votes
0answers
48 views

Counting linearly independent columns over GF($q=2^s$) with constraint

Assume that we have $M$ columns, $\boldsymbol{c}_i$ ($i=1,2,...M$), each of $n$ entries. I want to count the number of ways, denoted $W$, to assign GF($q=2^s$) field elements to these $M$ columns such ...
1
vote
1answer
39 views

Why are these two calculations in $GF(2^5)$ not equal [closed]

I have a quick question about Galois fields, since there seems to be something I have misunderstood way back in university. Addition and subtraction in Galois fields are both done using XOR ...
3
votes
1answer
49 views

Nilpotence and conjugacy in $M(p,\mathbb F_p)$

I have to solve the following problem: Characterize matrices $X\in M(p,\mathbb F_p)$ (note that $p$ is the dimension and the characteristic of the field) such that there exists $Y$ with the ...
1
vote
1answer
47 views

Intermediate fields of a finite field extension that is not separable

Let $\mathbb{F}_p$ be the finite field with $p$ elements, where $p$ is a prime number. Let $x$ and $y$ be transcendental and algebraically independent over $\mathbb{F}_p$. The extension $\mathbb{F}_p(...
1
vote
3answers
170 views

On every other finite field at least one of −1, 2 and −2 is a square, because the product of two non squares is a square

[Except on field extensions of $\mathbb{F}_2$] On every other finite field at least one of $−1$, $2$ and $−2$ is a square, because the product of two non squares is a square. I don't see why this is ...
1
vote
1answer
42 views

A tip to verify property of a finite field in Linear Algebra

Let $m$ be a prime number with the following operations in the set $\mathbb{Z}_m = \{\bar{0}, \bar{1}, \dots, \bar{m - 1}\}$: $\bar{a} + \bar{b} = \bar{c}$, where $c$ is the modulus of $a + b$ by $m$...
4
votes
1answer
93 views

A combinatorial question

Let us look on a $p\times p$ board (the $(\mathbb{F}_p)^2$ plane) with a single piece on the down left corner $(0,0)$. This is a special piece that has $3$ legal moves: Moving one step up $\pmod p$ ...
0
votes
1answer
25 views

Problem in solving a question related to field isomorphism. [duplicate]

How many fields are there (upto isomorphism) of order 6. I dont know how to proceed. I don't know how to proceed. Please help me. Thank you in advance.
2
votes
3answers
76 views

Proving $(\alpha + \beta)^{p^n} = \alpha^{p^n} + \beta^{p^n}$ in a finite field

Prove that if $F$ is a field with $p^n$ elements and $\alpha,\beta \in F$, then $$(\alpha + \beta)^{p^n} = \alpha^{p^n} + \beta^{p^n}$$ From Newton identity, we have that $$(a + b)^n = \sum_{i = 0}...
2
votes
1answer
27 views

Sums involving binomial coefficients in a finite field

Consider the field $\mathbb{F}_q$ where $q=p^k$ for some prime $p$. I have some identities related to binomial coefficients over such a field, which I wish to prove. So, can someone tell me a source ...
1
vote
2answers
46 views

Automorphism group of $F=F_3[x]/(x^3+2x-1)$, where $F_3$ is a field.

Given Automorphism group of $F=F_3[x]/(x^3+2x-1)$, where $F_3$ is a field of $3$ elements then, $F$ is a field with $27$ elements. $F$ is separable but not a normal extension of $F_3$. The ...
1
vote
0answers
25 views

Why are finite field elements polynomials

Finite fields are split up into two parts. Prime fields, arithmetic is simply mod p.A prime fields takes the form $GF(p)$, where $p$ is prime. Why for extension fields, eg, of the form $GF(p^m),m>1$...
14
votes
3answers
3k views

Irreducible polynomial which is reducible 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 $x^4+1=(x+1)^4\bmod 2$. Also $\bmod 3$ we have that $0,1,2$ are not ...
1
vote
1answer
37 views

Zech Logarithms

Let $a$ be a primitive element of $\mathbb{F}_{16}$ that satisfies the equation $a^4=1+a$. The logarithm of $1+a+a^2$ in $\mathbb{F}_{16}$ with base $a$ is the integer $i$ such that $0≤i<15$ ...
2
votes
1answer
56 views

Characters on rings of residue classes modulo polynomials over finite fields

First recall the following orthogonality relation on $\mathbb{Z}/n\mathbb{Z}$. Fix $n \in \mathbb{Z}$, $n \neq 0$. For $r \in \mathbb{Q}$, let $e(r) := e^{2 \pi i r}$. Let $x \in \mathbb{Z}$. Then ...
2
votes
1answer
34 views

Show $L$ can be extended to $M$ with $M/F$ cyclic

Suppose that $F$ has characteristic $p$ and $L/F$ is a cyclic extension of degree $p$. I'm trying to show that $L$ can be extended to $M$ where $F\subset L\subset M$ with $M/F$ cyclic of degree $p^2.$ ...
7
votes
0answers
167 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
2
votes
2answers
39 views

Splitting field in relation to finite fields

I'm trying to prove that the subfields of a Galois Field $GF$ of order $p^n$ are isomorphic to a Galois field of order $p^r$ where $r|n$, and that there exists a unique subfield for each such $r$. I ...
4
votes
1answer
65 views

Prove the polynomial $P_a=X^5 + a$ is reducible over a field

Let $(K, +, \cdot)$ a finite field so that the polynomial $P=X^2-5$ is irreducible. Prove that: a) $1+1 \ne 0$ b) The polynomial $P_a=X^5 + a$ is reducible $\forall a \in K$ a) ...
3
votes
1answer
30 views

Probability that a random polynomial has a linear factor?

What is the probability that a random degree $d$ polynomial in $\Bbb F_p[x]$ has a linear factor (root in $\Bbb F_p$) for cases $d>p$ and $d<p$? Lower bound is $\frac1p$ but definitely seems ...