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

6
votes
2answers
115 views

Show that there is no surjective ring homomorphism from $\mathbb Z_2[x]$ to $\mathbb Z_2 \times \mathbb Z_2\times \mathbb Z_2$

I saw this question as a bonus from a past exam, and here's my solution for verification. I argued like so. I said suppose there is such a surjective homomorphism $f$, then $f(0)=(0,0,0)$, $f(1)= ...
0
votes
3answers
36 views

Finding the order of elements in a Galois Field

Does there exist a Galois field GF(4)? GF(4)={0,1,2,3}; If we take this Galois field, then the element '2' is not having any degree..? So is it possible to construct GF(4) ?
1
vote
1answer
31 views

Algorithm to multiply nimbers

Let $a,b$ be nimbers. Is there an efficient algorithm to calculate $a*b$, the nim-product of $a$ and $b$? The following rule seems like it could be helpful: $$ 2^{2^m} * 2^{2^n} = \begin{cases} ...
4
votes
3answers
102 views

What do the elements of the field $\mathbb{Z}_2[x]/(x^4+x+1)$ look like? What is its order?

Background: I'm looking at old exams in abstract algebra. The factor ring described was described in one question and I'd like to understand it better. Question: Let $F = \mathbb{Z}_2[x]/(x^4+x+1)$. ...
6
votes
3answers
114 views

Splitting $\Phi_{15}$ in irreducible factors over $\mathbb{F}_7$

I have to split $\Phi_{15}$ in irreducible factors over the field $\mathbb{F}_7$. It has been a while that I did this kind of stuff, and to be the honest, I've never really understood this matter. I'd ...
1
vote
0answers
26 views

Computation of the 2-torsion group of an elliptic curve

I have some troubles solving the following problem: Let $E$ be the elliptic curve $E:y^2+2y=x^3+x+9$ over $\mathbb{F}_{16}$. Compute the 2-torsion group $E[2]$, i.e. find all the points of order $2$ ...
1
vote
5answers
75 views

The inverse of $2x^2+2$ in $\mathbb{Z}_3[x]/( x^3+2x^2+2)$

What is the independent coefficient in the inverse of $2x^2+2$ in $\mathbb{Z}_3[x]/(x^3+2x^2+2)$ ? I have been calculating some combinations, but I don't know how I can calculate the inverse.
0
votes
1answer
16 views

Prove the number of unordered pairs of linearly independent elements

Let $V$ be a vector space over $K$. Let $K={\mathbb{Z}}/{p\mathbb{Z}}$, and $\dim V=3$. We know that $V$ has $p^3$ elements. I need to show that the number of unordered pairs of linearly ...
4
votes
2answers
55 views

Show that if $\mathrm{Tr}(y)=0$ then there exists a $x$ such that $x^p-x=y$.

We have the Trace map defined by: $$ \mathrm{Tr}\colon \mathbb{F}_q\rightarrow\mathbb{F}_q\colon x\mapsto x+x^p+x^{p^2}+\cdots+x^{p^{n-1}}, $$ where $q=p^n$. Now I have to prove that if ...
1
vote
1answer
41 views

Proving that either $x $ or $2x$ is a generator of the cyclic group $(\mathbb Z_3[x]/\langle f(x) \rangle)^*$

if $f(x)$ is a cubic irreducible polynomial over $\mathbb Z_3$, prove that either $x $ or $2x$ is a generator of the cyclic group $(\mathbb Z_3[x]/\langle f(x) \rangle)^*$ Attempt: $f(x) = \alpha ...
0
votes
0answers
31 views

Presence of non square elements in $GF(p)$

I came across a problem which had a line of explanation as follows : Let $a \in GF(p). a$ is a non square in $GF(p),~ p \neq 2 \implies \nexists~ b\in GF(p)~~|~~a =b^2 $. But, is it really possible ...
4
votes
2answers
66 views

Every irreducible polynomial of degree $m$ over $\mathbb F_p$ divides $x^{p^m}-x$

We consider $F=\mathbb F_p$ for $p$ prime, $f(x)$ an irreducible polynomial of degree $m$ over $F$ and $g(x)=x^{p^m}-x$. I want to show that $f(x)\mid g(x)$. From the fact that the field ...
1
vote
2answers
59 views

Why is $1 + 1 = 0$ in $\{0, 1\}$ (binary field) and not 1 or 2?

Stuck on the simplest case in my foray into fields... I know there is a really similar question out there, but I can't find any contradiction with the field axioms if 1 + 1 = 1 instead of 0. Can ...
1
vote
1answer
53 views

Counting the roots of a polynomial over a finite field

Let $\mathbb{F}_{11}$ be the field of 11 elements and let $\mathcal{K}$ be the splitting field of $x^{3} - 1$ over $\mathbb{F}_{11}$. How many roots does $(x^{2} - 3)(x^{3} - 3)$ have in ...
5
votes
1answer
172 views

Simplify exponential sum over $\mathbb{F}_p$ to prove identity

I have a sum involving $p$-th roots of unity (where $\frac{1}{t}$ is to be understood as the field inverse $t^{-1} \bmod p$ etc.) of the form $\begin{align*} &d_{j,k}=\sum_{a,b,c \in ...
0
votes
0answers
28 views

What is rational point on elliptic curve over Galois field

It is clear what is a rational point on elliptic curve, when the curve is defined over real numbers. But if it is defined over Galois field, what is a rational point? If necessary, supply an example, ...
0
votes
0answers
21 views

find an example for an equation in finite field

Consider the extension field $F_{q^n}$ as a vector space over $F_q$, find two linearly independent elements $\alpha_1$ and $\alpha_2$ in $F_{q^n}$, such that $\alpha_{i}\neq1$, for $i=1,2$, and : ...
1
vote
0answers
37 views

Showing the existence of sub fields of a finite field

For each divisor $m$ of $n$, $GF(p^n)$ has a unique sub field of order $p^m$ . The proof of this theorem in Gallian goes like this : Suppose that $m$ divides $n$. Then, since : $(p^n-1) = ...
1
vote
1answer
55 views

Inclusion of Fields whose order is a prime power

Blue was correct, I need to fix my understanding of this: Finite fields have cardinality of a prime order because they have a prime subfield that has finite characteristic. I do not completely ...
3
votes
2answers
108 views
1
vote
3answers
53 views

Automorphisms of splitting field of $x^p-x-a$

Let $p$ be a prime and consider the splitting field of $f(x) = x^{p} - x - a$ over $\mathbb{F}_{p}$. I have worked out that the splitting field is $\mathbb{F}_{p}(\beta)$, where $\beta$ is a root of ...
1
vote
1answer
53 views

order of $x \operatorname{mod} p(x)$ in $\mathbb Z_2$

I am writing a software that analyze the behavior of an LFSR given its feedback polynomial. At some point, I need to compute the order of $x \operatorname{mod} p(x)$ in $\mathbb Z_2$. In mathematical ...
1
vote
1answer
36 views

Every field with characterisitic $p$ contains the field $\mathbb{Z}_p$

I seem to hold a very loose grasp of the concept of fields - I've encountered this question: Show that every finite field with characteristic $p$ contains $\mathbb{Z}_p$ (i.e. $\mathbb{Z}_p = ...
1
vote
1answer
28 views

Associative properties with two numbers

I am working through a number theory text and I am given a set $S=\{A,B\}$ and it has the properties: 1) $A+A=A$ 2) $B+B=A$ 3) $A+B=B+A=B$ 4) $A(A)=A$ 5) $A(B)=B(A)= A$ 6) $B(B)=B$ I am to verify ...
1
vote
0answers
46 views

Galois Group of $x^p-x+a$ over $\mathbb{F}_p$ for prime $p$ and $a\neq 0\in \mathbb{F}_p$

Question is to find Galois group of $f(x)=x^p-x+a$ over $\mathbb{F}_p$ for prime $p$ and $a\neq 0\in \mathbb{F}_p$ What i have done so far is : I could see that $f(x)$ is Irreducible and ...
1
vote
0answers
63 views

GCD of high order polynomials(modulo large prime)

I want to solve the following question: Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to ...
2
votes
2answers
50 views

Raising to the power over finite fields ??

Are there any tricks with raising an element from a finite field to power. For example let $ a \in GF(p^n)$ and I want to compute $a^m$ for some $m \in \mathbb{Z}$. Is there a nice trick to do this ...
1
vote
1answer
52 views

a square in a finite field of odd order

GF(q) is a finite field of order q, where q is odd. Prove that $a\in GF(q), a\neq0$ has a root in $GF(q)$ iff $a^{(q-1)/2}=1$. I tried to prove it this way: Suppose a has a root in ...
3
votes
1answer
58 views

An elementary question regarding a multiplicative character over finite fields

Reading Chapter 2 of Koblitz's Introduction to Elliptic Curves and Modular Forms, I got stuck on the following question. I would like to proceed my reading, so I would appreciate any hint to this. I ...
1
vote
1answer
54 views

Absolute value of a cubic Gauss sum (over Field $\mathbb{F}_p$ )

I'm interested in the quantity $|\sum_{x \in \mathbb{F}_p} \omega^{ax^3+bx^2+cx}|$ where $a \in \mathbb{F}_p^*,b,c \in \mathbb{F}_p$ and $\omega$ is a primitive $p$-th root of unity i.e. ...
0
votes
1answer
25 views

$2^{p}\equiv1$ mod $2p+1$ for certain $p$

Let $p$ be a prime number such that $p\equiv3$ mod $4$ and $2p+1$ is also a prime number. It is well known that $2^{p}\equiv1$ mod $2p+1$, but I haven't been able to prove it.
1
vote
1answer
43 views

Zeros of $317x^{2}-151xy+40y^{2}$ over $\mathbb{F}_{31}$

Let $K:=\mathbb{F}_{31}$ and $f(x,y):=317x^{2}-151xy+40y^{2}$. I have to find out if there exists any point $(a,b)\in K^{2}$ such that $f(a,b)=0$ and $a\neq0$ or $b\neq0$.
1
vote
1answer
69 views

Sequences length for LFSR in the general case

An LFSR with a reducible polynomial can generate several sequences, depending on the initial value. My goal is to have an algorithm to compute those length without going through the enumeration of all ...
1
vote
4answers
86 views

multiplication in Galois Fields

I don't know much about Galois fields. My question is the following Assume we are working with GF(8). Let say for example I want to multiply 2 by 4 in GF(8). Then it should be equal to $2*4 \text{ ...
0
votes
2answers
29 views

Subtraction in GF(2^8) Giving Incorrect Results

Let me preface this by stating that I'm not normally a math person, but I'm currently dabbling in finite fields to help wrap my head around certain cryptographic topics (specifically those based ...
2
votes
2answers
43 views

diagonalization of a matrix over finite fields

I'm having a problem with determine whether a matrix is diagonalizable over $\mathbb F_{2}$, over $\mathbb F_{3}$, etc. for example, for the following matrix: $$ \begin{bmatrix} 1 ...
1
vote
1answer
40 views

Maps preserving roots of a polynomial function over finite fields

Let $P(x_{1},\ldots,x_{n}):\mathbb{F}_{2}^{n}\rightarrow \mathbb{F}_{2}$ be a polynomial function with degree $d$ and with variables $x_{1},\ldots,x_{n} \in \mathbb{F}_{2}$. Let $S(P)=\{ ...
0
votes
0answers
26 views

the number of cube roots in a finite field [duplicate]

Let $p$ be a prime number, and let $\mathbb F_p$ be the field with $p$ elements. How should I choose $p$ such that all elements of $\mathbb F_p$ have cube roots in $\mathbb F_p$?
1
vote
1answer
77 views

Sequences length for LFSR when polynomial is reducible

An LFSR with polynomial 1+x4+x5 = (1+x+x2)(1+x+x3) can generate several sequences, depending on the initial value. If I did not made any mistake enumerating them, the sequences length are 3, 7 and 21. ...
2
votes
0answers
24 views

Blocking set for cosets of codimension $2$

In this paper following theorem is proved: If $V$ is vector space of dimension $n$ over a finite field $F$ of $q$ elements then any subset of $V$ which meets every hyperplane of $V$ contains at least ...
1
vote
0answers
31 views

Version of Chevalley's Theorem proving $\mathbb{F}_q$ is a $C_1$-field for $\mathbb{Z}/p^n\mathbb{Z}$?

Let $k=\mathbb{F}_q$ Chevalley's theorem states that if $f(x_i)\in k[x_1,...,x_n]$ is such that $f(0,...,0)=0$ and $deg(f)<n$, then there is a non-trivial $a_i\in k^n$ such that $f(a_i)=0$. Is ...
3
votes
0answers
129 views

Find minimal set of cosets $C$, so that each $2$ vectors in $A_n$ are in one coset in $C$

Let $F_2^n$ be the set of all vectors of length $n$ with values of $0$ or $1$ and $A_n$ = $F_2^n \setminus(11\ldots1)$. Set $A_n$ contains all vectors except one with all $1$s. We can consider cosets ...
0
votes
1answer
22 views

system of equations with coefficients in finite field

Suppose we have three simultaneously equations with $4$ variables with coefficients in finite fields, i.e. $$\alpha_1A_1 + \beta_1B_1+\gamma_1C_1 + \theta_1D_1=x$$ $$\alpha_2A_1 + ...
3
votes
0answers
92 views

zeros of a simple polynomial

For $x, y \in GF[2^n]$, consider the two-parameter polynomial $P(x,y) = x \cdot y + f(x) + g(y)$, where $f$ and $g$ are arbitrary polynomials on $GF[2^n]$. Can we say anything about the number of ...
1
vote
0answers
15 views

irreducible quadratic trinomial over finite field

In p130 of 《finite field 》 by Lidl et al. : For a trinomial x^2 +x +a over a finite field F_q of odd characteristic it is easily seen it is irreducible over F_q if and only if a is not of the form a = ...
6
votes
2answers
91 views

Euclid and finite fields

In 300 BC or so Euclid pointed out that if $S$ is any finite set of prime numbers then the prime factors of $1+\prod S$ are not in $S$, so that $S$ can always be extended to a larger finite set. Much ...
2
votes
1answer
38 views

Which powers of a primitive element of a finite field yield a generator of a finite field extension?

Let $F_{q^m}$ denote the finite field with $q^m$ elements. Let $\gamma$ be a primitive element of $F_{q^m}$. What are the powers $i$ such that $F_q(\gamma^i)=F_{q^m}$? Note that the following ...
2
votes
2answers
69 views

If $k>0$ is a positive integer and $p$ is any prime, when is $\mathbb Z_p[\sqrt{k}] =\{a + b\sqrt k~|~a,b \in\mathbb Z_p\}$ a field.

If $k>0$ is a positive integer and $p$ is any prime, when is $\mathbb Z_p[\sqrt{k}] =\{a + b\sqrt k~|~a,b \in\mathbb Z_p\}$ a field? Find necessary and sufficient condition. Attempt: Since we ...
5
votes
2answers
409 views

Let F be a field of order 32. Show that the only subfields of F are F itself and {0,1}.

$F$ is a field of order $32$. $F$ and {$0,1$} are trivial subfields of $F$. But how can we show that these are the only subfields of $F$? Can someone give me a direction to this question?
1
vote
1answer
61 views

If $X^{p^d}\equiv X\text{ mod }f$ for prime numbers $p,d$, then $f\in\mathbb{F}_p[X]$ with $\deg f=d$ is irreducible over $\mathbb{F}_p$

Let $p$ and $d$ be prime numbers and $f\in\mathbb{F}_p[X]$ with $\deg f=d$ and no roots over $\mathbb{F}_p$. I want to show $$X^{p^d}\equiv X\text{ mod }f\;\;\;\Rightarrow\;\;\;f\text{ is irreducible ...