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)

0
votes
1answer
18 views

Proof of lemma about product of irreducible polynomials over finite fields

Reading this Wikipedia page while learning about polynomials over finite fields, I came upon the following lemma: For $i ≥ 1$ the polynomial $x^{q^i}-x \in \mathbf{F}_q[x]$ is the product of all ...
0
votes
0answers
13 views

Bound for degree of polynomial in finite field in order to be solved by common algorithms

For fixing ideas, suppose that we have a field $K$ of $p^n$ elements with (e.g.) $p=7$, $n=55$. Let $f(x)\in K[x]$. What is the maximum degree that $f$ can have in order to be solved by a common and ...
1
vote
0answers
99 views

Proof of Chevalley–Warning theorem

How to prove Chevalley–Warning theorem (http://en.wikipedia.org/wiki/Chevalley%E2%80%93Warning_theorem) by using Fulton's trace formula (#$|X(\mathbb{F}_p)| \equiv \sum (-1)^i Tr(Frob_p|H^i(X, ...
1
vote
0answers
22 views

The most general splitting of a field extension

Take $L/K$ an extension of the field $K$. I have questions on how we can "split" the extension $L/K$. (1) One knows that $L$ has a transcendence basis $(x_i)_{i\in I}$ over $L$, so that if $E := ...
2
votes
3answers
64 views

Counting the number of $\mathbb{F}_q$ points on a homogeneous polynomial

This is an area of number theory that I am not too familiar with and I would appreciate any assistance! Let $\mathbb{F}_q$ be a finite field of $q$ elements with characteristic not 2 or 3. I have the ...
2
votes
1answer
41 views

Why is $\sqrt{5}$ an element of every field of order $p^{2 e}$?

This was claimed in an answer to another question I asked but it's unclear to me why it's true. I'd also be happy with a reference that explains it. Thanks!
2
votes
3answers
37 views

$x^2+3$ has two zeros over ${\Bbb F}_p$ provided that $x^2+x+1\in{\Bbb F}_p[x]$ has two?

The following is an exercise in abstract algebra: If $p=1\pmod{3}$, then $x^2+x+1\in\Bbb{F}_p[x]$ has two zeros. Prove in this case that $-3$ is a quadratic residue mod $p$. Showing that ...
2
votes
2answers
32 views

a root of some polynomial over finite field

I think this is a really basic question, but it had been a little while since I dealt with this material and I was hoping to get a bit of assistance here. Let $q = p ^{2M}$ for some prime $p$ and $M ...
1
vote
3answers
56 views

Intermediate field extension

Consider de field $\mathbb F_2$ of two elements. Let $\theta$ be a zero of the irreducible polynomial $t^4+t+1$ and consider the extension $\mathbb F[\theta]$. May question is: Can we find an ...
2
votes
1answer
54 views

Every element of field $F_q$ has $k$th root if and only if $\gcd(q-1,k)=1$

Help me please to prove that: For any $k \in \mathbb{N}$ each element of field $F_q$ is the $k$-th power of some element from that field if and only if $GCD(q-1, k)=1$. My approach Let's look ...
2
votes
3answers
51 views

How to show the isomorphism

I'm not sure how to show this $$\mathbb{Z}_3[X]/(x^3 -x +1)\cong\mathbb{Z}_3[X]/(x^3 -x^2+x +1).$$ Any help or hint would be helpful.
1
vote
1answer
45 views

Question about polynomials in finite fields

No doubt I'm missing something obvious here (my finite field theory is quite rusty) but I'm reading a book that claims that 1) $f(x) = x^2 - x - 1$ is irreducible over $F_q$ where $q = p^e$ for an ...
1
vote
1answer
32 views

Covering of a vector space over a finite field

Let $k$ be a finite field and $V$ a finite-dimensional vector space over $k$. Let $d$ be the dimension of $V$ and $q$ the cardinal of $k$. Construct $q+1$ hyperplanes $V_1,\ldots,V_{q+1}$ ...
1
vote
3answers
81 views

How do I show that the polynomial $f(x) = x^2 + x + 3$ $∈$ $Z_7[x]$ is a primitive polynomial?

I understand that a primitive polynomial is a polynomial that generates all elements of an extension field from a base field. However I am not sure how to apply this definition to answer my question. ...
0
votes
0answers
40 views

Question about galois imaginary and modular arithmetic

Let $p$ be a prime of type $3\space mod \space 4$. Then there is no solution $x^2 = -1 \space mod \space p$. Therefore we can define the so-called Galois imaginary $i$. ( $i^2 = -1 \space mod \space ...
1
vote
1answer
45 views

proof factoring of $x^n-1$

I have a question about the proof of the theorem stating that $$x^n-1 = \prod_{i \in I} m^{(i)}(x)$$ is a factorisation in irreducible factors of $x^n-1$ over a field $\mathbb{F}_q$. Here $m^{(i)}$ is ...
0
votes
1answer
38 views

Rank notion of a matrix

$\newcommand{\rank}{\operatorname{rank}}$Divide $p-1$ ($p=q^k>2$ with $k>1$, $q$ prime) elements in $\Bbb F_p^\times$ into equal disjoint subsets $S_+,S_-$. Given square $0-1$ matrix $A$, ...
1
vote
1answer
59 views

Calculating Ranks

Given $ A=\begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22}\\ \end{pmatrix}$, a $2n\times 2n$ real matrix with each $A_{ij}$, a $n\times n$ matrix, take $A_1=\begin{pmatrix} A_{11} & 0 \\ ...
2
votes
1answer
28 views

What is $\{ f \in F_{p^m}[x_1, \ldots, x_n] : f(a) = 0, \forall a \in A^n\}$?

As the title suggests, I am interested in knowing if there is a neat description of the ideal of polynomials that vanish on affine $n$ space over a finite field with $p^m$ elements. Is there a way to ...
2
votes
0answers
23 views

Conversion from/to power form and polynomial basis is a finite field

I'm trying to figure out if there is a way better than $O(m^2)$ of converting between the power form $(\alpha^n)$ to polynomial basis. Right now, I'm just enumerating the entire field up to the $n$-th ...
0
votes
1answer
54 views

Why 2*3=6 in finite field?

In a finite field $F$, say of order 7. Suppose I didn't known that it must isomorphic to $\mathbb{F}_7$ By the definition of field, there exists $1 \in F$, and hence exists $1+1$ (denoted by $2$), ...
2
votes
2answers
67 views

Embed finite field in algebraic closed field

Let $\Omega$ be an algebraic closed field of characteristic $p$, then for any field $F$ of $q$ ($=p^a$) elements, $F$ can be embedded in $\Omega.$ I need above property to proof that every ...
2
votes
1answer
22 views

Determining subgroups of a finite field and their elements

I'm studying cryptography and while reading some lecture notes I found the following: $F$*37 has subgroups of order 2 ({20 , 218}), 3 ({20 , 212 , 224}), 4, 6, 9, 12, and 18. How to determine that ...
2
votes
1answer
52 views

Number of self-inverse matrices over prime field

Regarding the cryptosystem known as the Hill Cipher, my textbook by Douglas R. Stinson has an exercise asking you to find the number of involutory keys for $m=2$ over $\mathbb Z_{26}$. This means that ...
1
vote
1answer
51 views

Prove these quadractic forms are equivalent over $\mathbb{Z_5}$

Consider the following quadractic forms, defined in the field $\mathbb{Z_5}$, $$q(x, y, z, t) = 2y^2 + z^2 + 2t^2 + 4xy + 2xt + 4yt$$ $$q_0(x, y, z, t) = x^2 + y^2 + z^2 + dt^2$$ Prove they are ...
0
votes
0answers
19 views

What's the implication of the Frobenius automorphism to DLP

Given a field, e.g. GF(p^x), does the existence of a Frobenius automorphism affect the difficulty of calculating the discrete log in that field? How about other morphisms?
1
vote
1answer
46 views

Computing number of points in elliptic curve through frobenius endomorphism

I got the following question where I stuck at the moment. Given is the elliptic curve (EC) equation: $E: y^2+3xy+y=x^3+4x+4$ over the finite field ${\bf F}_5$ The first task is now to find out all ...
1
vote
1answer
28 views

Linear combination of Frobenius powers contains roots of polynomial

Let $F$ be an $n-$degree extension of $\mathbb{F}_q$ and let $f(x)\in F[x]$. Let $$g(x)=\sum_{i=0}^{n-1}a_if(x)^{q^i}$$ with $a_i\in F$. Let $\alpha\in F$ be a root of $g$, prove that $\alpha$ is ...
1
vote
2answers
84 views

Calculate all the generators in $\mathbb{Z}/61$

Here's the exact question I trying answer: "Calculate all the generators in $(\mathbb{Z}/61)^\times$ . You may assume that $g = 2$ is one such generator. " Does this question mean calculate the ...
7
votes
2answers
66 views

Prove $\mathbb{Z}_3[x]/(x^2+1)$ and $\mathbb{Z}_3[x]/(x^2+x-1)$ are isomorphic.

Prove $\mathbb{Z}_3[x]/(x^2+1)$ and $\mathbb{Z}_3[x]/(x^2+x-1)$ are isomorphic by finding an explicit isomorphism. My question is how I can define the map. Here are what I tried: ...
2
votes
0answers
35 views

Wiedemann for solving sparse linear equation

I am new member. I am researching in Wiedemann algorithm to find solution $x$ of $$Ax=b$$ Firstly, I will show a Wiedemann's deterministic algorithm (Algorithm 2 in paper Compute $A^ib$ for ...
1
vote
0answers
64 views

Orbits of Frobenius homomorphism in finite field extension

I'm trying to find the orbits of the Frobenius homomorphism $\phi_p: a \to a^p$ on $\mathbb{F}_{p^4} / \mathbb{F}_p$. I can see there are $p$ 1 orbits corresponding to the action on $\mathbb{F}_p$ but ...
5
votes
1answer
90 views

Algebraic closure of the rational inside a quotient of product of finite fields

I'm trying to solve the following exercise: " Consider the ring $R = \prod_{p} \mathbb{F}_p$, where $p$ runs over all prime numbers and $\mathbb{F}_p$ is a field with $p$ elements. Show that there ...
1
vote
0answers
40 views

trace of a matrix in $\mathbb{Z}_{227}$ [duplicate]

Let $A$ be a $227 \times 227$ matrix with entries from $\mathbb{Z}_{227}$. If A has distinct eigenvalues what is the trace of $A$? I am guessing the answer is zero. Since the eigenvalues of $A$ need ...
2
votes
0answers
66 views

Finite Ring with unity and no zero divisors is field [duplicate]

I would like to know if someone can help me with this. "Show that a finite ring $R$ with unity $1\neq 0$ and no divisors of 0 is a field." The original exercise asked me to show that it was a ...
0
votes
1answer
40 views

Primitive root of unity in finite fields

To find a primitive $n$-th root of unity in a field $F_q$ of size $q$, one takes the smallest positive integer $m$ such that $q^m \equiv 1 \bmod n$ and finds a primitive $n$-th root of unity in ...
1
vote
1answer
44 views

Field of polynomials mod n?

I have a few questions and i am looking for some clarification. 1) Is it correct that one can define a field $(Z_n, +, X)$ of integers mod $n$, where all the elements are integers $a$ such that ...
1
vote
1answer
41 views

Number of subalgebras of dimension $e$ of a finite dimensional algebra over $F_q$ of dimension $d$

Let $F_q$ be a finite field of order $q$. Let $A$ be a finite dimensional algebra over $F_q$ of dimension $d$ and let $e < d$ be some positive integer. Then what is the number of sub-algebras of ...
3
votes
2answers
76 views

$\Bbb F_p$ where $p$ is an odd prime has exactly half the non-zero elements as a square [duplicate]

I want to show that in $\Bbb F_p$ where $p$ is an odd prime, that half the non-zero elements are squares. Now I know that all fields $\Bbb F_p$ where $p$ is prime are isomorphic to $\Bbb Z / \Bbb p ...
2
votes
1answer
56 views

Finite field as a splitting field of some irreducible polynomial

In many texts that I've read regarding finite fields, it always appears to be simply stated that a finite field is a splitting field of some irreducible polynomial, without proof. What are some good ...
1
vote
3answers
75 views

annihilator polynomial of a multiplicative group in a Field?

Consider the annihilator polynomial of a multiplicative group $H$ of a field $\mathbf{F}_q$. $$A(x) = \prod_{\alpha\in H} (x-\alpha)$$ I read somewhere that this polynomial can be written as $A(x) ...
0
votes
0answers
33 views

Solution of the equation $x^r=a$

Let $F_{p^n}$ be the field with $p^n$ elements. Suppose $p^n-1=q_1^{a_1}...q_k^{a_k}$ where $q_i$ are distinct primes. Find the no. of integers $r\in\{0,1,...,p^n-2\}$ for which the equation $x^r=a$ ...
1
vote
1answer
163 views

On full rank matrix properties

$(1)$ What is number of rank $n$ $m\times n$ $0-1$ matrices when $m=n$ and $m>n$? Is there solutions closed forms? $(2)$ Over $\Bbb F_2$, does full rank of an $n\times n$ matrix imply determinant ...
2
votes
1answer
100 views

Galois group of $x^5 + x^2 + 1$ over the field $\mathbb{F}_{2}$

I'm uncertain if I am doing this problem correctly. This is an old algebra prelim problem regarding Galois theory. We have to find the Galois group of the irreducible polynomial (the problem already ...
1
vote
2answers
49 views

Show that the rings $R_1=F_5[x]/(x^2)$ and $R_2=F_5\times F_5$ are not isomorphic.

Show that the rings $R_1=F_5[x]/(x^2)$ and $R_2=F_5\times F_5$ are not isomorphic.($F_5$ is the field with $5$ elements.) My Work: Since $(0,1)$ does not have an inverse, $F_5\times F_5$ is not a ...
1
vote
2answers
50 views

An equation over $\Bbb F_{3^k}$

Does the equation $$x^2=2=-1$$ have solutions in any extension field of $\Bbb F_3$?
8
votes
2answers
182 views

How many solutions of the equation $x^2-y^2=1$ are there with $x,y\in\mathbb F_{p^n}$?

Let $p>2$ be an odd prime. Let $\mathbb F_{p^n}$ be the field with $p^n$ elements. How many solutions of the equation $x^2-y^2=1$ are there with $x,y\in\mathbb F_{p^n}$? My work: Char $F=p$. ...
1
vote
2answers
71 views

How to prove the polynomial $ x^{2011}-x\in \mathbb{Z}_{2011}[x] $ is separable?

I am trying to prove that the polynomial $ x^{2011}-x\in \mathbb{Z}_{2011}[x] $ is separable. Definition: Let K be a field and $f\in K[x]$ an irreducible polynomial. The polynomial $f$ is said to be ...
1
vote
1answer
107 views

Dummit and Foote page 591

Having trouble with something that Dummit and Foote is saying. On page 591 it says "Note that over $\mathbb{Q}$ or over a finite field (or, more generally, over any perfect field) the splitting field ...
1
vote
0answers
86 views

Factoring a polynomial over $\mathbb F_{2^8}$

How do you find the factors of $x^4+x+1$ in $GF(2^8)$ in terms of polynomials? Let me explain, We have primitive irreducible polynomial $p(x)=x^2+x+1$ in $GF(2^2)$ which has root $\alpha^2+\alpha$ in ...