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
2answers
46 views

Irreducible Polynomials $GF(2^4)$: Why is $x^4 + x^2 + 1$ reducible?

I am currently working with $GF(2)$, in particular with $GF(2^4)$. One task is to find all irreducible polynomials. I have found ways of reducing the list of all candidates drastically. In my current ...
1
vote
1answer
21 views

Boolean Polynomial Mutliplication modulo an irreducible polynomial

I am currently reading a paper on the Mathematics of RAID 6 by Peter Anvin and cannot get my head around the notation or results used describing multiplication by {02} (hexadecimal). Here is how he ...
1
vote
2answers
41 views

Distribution of Trace values

I try to prove that ${2^{n-1}}$ elements of the field $\mathbf{F}_{2^{n}}$ have a Trace with value 1, while the other ${2^{n-1}}$ elements have a Trace with value 0. I started to show that Trace(1) ...
1
vote
1answer
45 views

Irreducibility of polynomials over finite field

If I want to show that a certain polynomial is irreducible over a finite field, which methods do I have? In particular how can I show that $X^4-3$ is irreducible over $\mathbb F_5$ The idea which I ...
2
votes
1answer
21 views

resultants over finite fields vs resultants over their closure

I'm having a little trouble grokking the following line of argument. I have two monic, univariate polynomials $p(x)$ and $q(x)$ over $\mathbb{Z}/p\mathbb{Z}$ that share a common root, where $p$ is ...
0
votes
2answers
51 views

Show that if $n$ is not prime then $\mathbb{Z}/n\mathbb{Z}$ is not a field

I read book of Dummit and Foot Abstract algebra. I need some help with the following question. Show that if $n$ is not prime then $\mathbb{Z}/n\mathbb{Z}$ is not a field I know definitions of ...
1
vote
0answers
8 views

determining the multiple solutions for GF(2) discrete logarithms of polynomials with partially known coefficients

I have an LFSR, essentially $x^k \mod p(x)$ for some characteristic polynomial with coefficients in GF(2), as outlined in Clark and Weng's article: it has a period (= order of the associated finite ...
2
votes
1answer
46 views

Generating elements of a Galois Field using an irreducible polynomial

I am practicing some cryptography problems and I am having problems with one involving Galois Fields and irreducible polynomials. Here is the problem: Using the irreducible polynomial $f(x) = x^5 ...
2
votes
0answers
38 views

When does a field of for which a set of matrices is defined on become important?

I have already gone through several linear algebra related courses without any notion of a field and I am having trouble reading a serious linear algebra book that talks about infinite field, so and ...
2
votes
0answers
46 views

Value of a Moebius sum

Let $q$ be a power of a prime, let $n \in \mathbb{N}$. Is the value of the following sum known? $$ \sum_{d \mid q^n-1} \mu\left( \dfrac{q^n-1}{d} \right) q^{ord_d(q)}, $$ where $ord_d(q)$ denotes ...
1
vote
2answers
26 views

What is the general property a field in which addition can be “undone” by addition

For example, in GF(2) we can do the following: p = 110 k = 010 c = p+k = 110+010 = 100 If we want to calculate p or ...
1
vote
3answers
101 views

Construction of a field with $8$ elements.

Could someone tell me if one can build a field with $8$ elements?
2
votes
0answers
60 views

Picking codewords that are close

Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and number of minimum weight codewords $N_d$. How many ways can you select codewords $c_1,\dots,c_T$ (assume $T\ll q^k$) such ...
3
votes
0answers
39 views

When is a generalized Vandermonde matrix over a finite field invertible?

The generalized Vandermonde matrix that I am considering is one where the rows of a matrix correspond to the powers of different elements of the field, but the powers need not be consecutive integers ...
1
vote
0answers
35 views

Zeros of the Ramanujan sum for finite fields

Let $\mathbb{F}_q$ be a finite field with $q$ elements, let $N$ be a positive divisor of $q-1$, and let $\xi_N$ be an element of $\mathbb{F}_q^*$ of order $N$. One can similarly define the Ramanujan ...
1
vote
2answers
104 views

$F$ a field and $G$ finite subset of $F \setminus \{0\}$ with 1 & satisfying $a, b ∈ G$ then $ab^{−1} ∈ G$. Show that $G$ is cyclic

Let $F$ be a field and let $G$ be a finite subset of $F \setminus \{0\}$ containing $1$ and satisfying the condition that if $a, b ∈ G$ then $ab^{−1} ∈ G$. Show that there exists an element $c ∈ G$ ...
0
votes
0answers
59 views

Vector spaces over Z/2Z,countably many predicates added,invariant

Suppose we have a class of vector spaces over $Z/2Z$ with predicates $P_n,n\in N$ added for independent subspaces of co-dimension 2. (BTW, independent in which sense,$P_n$ is independent with ...
0
votes
0answers
33 views

Finding a polynom to construct finite field

I'm currently working on the following task: "State a polynom $f(x)\in F_4[x]$ with which you can construct $F_{2^6}$ as $F_4[x]/fF_4[x]$." What I know is, that a polynom $f$ is needed, which must ...
3
votes
1answer
97 views

Upper bounds for the dimension of a binary cyclic code

Let $\mathbb{F}_2 = \{0,1\}$ denote the field with two elements. Consider a binary $N$-tuple $a = a_0 a_1 \ldots a_{N-1}$, of elements $a_i \in \mathbb{F}_2$. The cyclic code $C_a$ corresponding to ...
1
vote
2answers
60 views

Factoring polynomial in prime field

How is a polynomial like $x^5-1$ be factorised in a prime field like $\mathbb{F}_{11}$ for example ? Any advice ? I was successful in trying all members of $\mathbb{F}_{11}$ to find the roots as ...
1
vote
2answers
51 views

Calculate the trace of all elements in $F_8$

I got the following exercise where you have to calc the trace of all elements in ${F_8}$ which is constructed as ${F_2}[x]$/(${x^3+x+1}$)${F_2}[x]$. Up to now I did those steps: 1) Find all elements ...
1
vote
3answers
46 views

Irreducible polynomials of degree $2$ over a finite field

By consider the nonquadratic residues, one has an irreducible polynomial of degree $2$ over ${\Bbb F}_p$ for $p$ being odd: $x^2+r$. Also we know that $x^2+x+1$ is irreducible over ${\Bbb{F}_2}$. How ...
0
votes
2answers
58 views

Factorization of $x^8-x$ over $F_2$ and $F_4$

How can I factorize $x^8-x$ over the fields $F_2$ and $F_4$?
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
61 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
55 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
52 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
46 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
83 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
69 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
54 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
52 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
48 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 ...