Questions tagged [finite-fields]

Finite fields are fields (number systems with addition, subtraction, multiplication, and division) with only finitely many elements. They arise in abstract algebra, number theory, and cryptography. 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)$.

Filter by
Sorted by
Tagged with
1
vote
1answer
32 views

showing $x^4+x^2+x+1$ is reducible in $GF(81)=GF(3^4)$

I am trying to show that in $GF(81)=GF(3^4)$, $$x^4+x^2+x+1$$ is reducible I proved that it was irreducible in $\mathbb{Z}_3$ How can I prove this ? More generally, how to prove if a polynomial ...
0
votes
1answer
15 views

Modulus operation for polynomials over GF(2)

If I treat the coefficients as an array of boolean values, I would achieve multiplication by using the AND operator and addition by using XOR. How would I go about finding the remainder? Is there, ...
0
votes
1answer
41 views

Degree of extension over finite fields with two elements having same degree irreducible

I get that Q(√2,√3) has degree 4 over Q. Now consider finite field F and a,b lying in an extension of F having same degree irreducible polynomial over F, let it be 'd'. Is the extension F(a,b), of ...
0
votes
1answer
33 views

Splitting fields of polynomials over finite fields of prime-power order

Suppose $\mathbb{F}_{p^k}$ is the finite field of size $p^k$, where $p$ is prime and $k$ is a positive integer. Also $m$ is a positive integer such that $p \nmid m$, with $K$ being the splitting field ...
1
vote
0answers
39 views

Find the least prime $p$ such that $x^{22} + x^{21} + \cdots + x + 1$ irreducible over $F_p$.

I unable to proceed. Anyone please help me. Problem from the book: Finite Fields and their application by Lidl and Niederreiter (#2.55 & #2.56). Find the least prime $p$ such that $x^{22} + x^{21}...
0
votes
0answers
31 views

Splitting field over Z_2

Let $$f(x)=(x^3+x+1)(x^2+x+1)$$ and E is splitting field over $Z_2$ And how can i get $[E:Z_2]$ ? I used to find the the splitting field of $(x^3+x+1)$ of $f(x)$ over $GF(2)$ is $GF(2^3)$ but i don'...
1
vote
2answers
55 views

Cardinality of polynomial ring over a finite field

My questions is relative to the cardinality. Consider $\mathbb{F}$ a field of characteristic $p$, so it has the elements $\{0,1,\dots,p-1\}$. Now consider the polynomials with variable $x$ and ...
1
vote
1answer
36 views

Proof of sub field and polynomial ring

My following task is: Let $\mathbb{K}$ be a field und be $\mathbb{K}^{\prime}$ a subfield of $\mathbb{K} . \mathbb{K}[t]$ and $\mathbb{K}^{\prime}[t]$ are polynomial rings over the respective fields ...
1
vote
2answers
29 views

Confusion about the choice of primitive root/multiplicative generator in Diffie-Hellman Key Exchange.

I was reading "Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, An Introduction to Mathematical Cryptography, Second Edition". I understand the basic Diffie-Hellman Key Exchange. Though, I was ...
0
votes
1answer
14 views

Does $xA=x$ is true for any $x\ne 0\in\mathbb{F_q}^{1\times n}$ imply that $A=I$ where $A\in \mathbb{F_q}^{n\times n}$?

Does $xA=x$ is true for any $x\ne 0\in\mathbb{F_q}^{1\times n}$ imply that $A=I$ where $A\in \mathbb{F_q}^{n\times n}$ and $\mathbb{F_q}$ is the finite field? If it's true, how it can be shown ...
1
vote
1answer
27 views

Monic irreducible reversible polynomial

This is Exercise 245 of the book "Fundamentals of Error-Correcting Codes" by W. C. Huffman and V. Pless, page 145. Show that a monic irreducible reversible polynomial of degree greater than 1 ...
1
vote
1answer
28 views

The automorphism of splitting field of x^p-x+a over Z_p.

I'd like to solve the question. Let $L$ the splitting field of $f(x)=x^p-x+a$ ($a\neq 0$) over $\mathbb Z_p$. $g : L \rightarrow L$, $g(\alpha)=\alpha+1$ where $\alpha$ is a root of $f(x)$ is ...
1
vote
1answer
36 views

Pairs $(a,b)\in F^2$ such that $a^6+b^6=1$ where $F$ is a finite field of 25 elements

Let $F$ be a field of 25 elements, and consider the group $G$ of all $2\times 2$ matrices $A$ with entries in $F$ satisfying $A_5A=I$, where $I$ is the identity matrix and $A_5=\begin{pmatrix} a^...
1
vote
1answer
23 views

Number of elements in $ \{(x,y)\in \Bbb F_q^2:y^p+y=x^{p+1} \} $ where $p>2$ is a prime and $q=p^2$

Let $p$ be a prime number $>2$ and $q=p^2$. Let $\Bbb F_q$ be a field of $q$ elements. Then it is easily shown that $\Bbb F_q=\{a+b\alpha : a,b\in \Bbb F_p, \alpha^2=u\}$, where $u$ is an element ...
0
votes
2answers
42 views

Inverse of a complex number in finite field

I am working with a finite field $\mathbb{F}_p(i)$ for $p = 431$. The elements of this field are of the form $u + vi$ where $u, v \in \mathbb{F}_p$. I have a confusion with the inverse operation in ...
1
vote
0answers
36 views

Distribution of polynomial after projections

I asked a somewhat similar question here, but I believe this one is different enough for its own post. Let $p : \{1,2 \}^n \rightarrow \mathbb{Z}_3$ be a polynomial chosen uniformly at random (every ...
-1
votes
1answer
31 views

Roots of an irreducible polynomial in an extension field

So I have just got into Algebra and I intuitively understand the idea of an extension. However, I am struggling in answering this certain question. In $GF(2)$, it is known that $x^2+x+1$ is ...
3
votes
1answer
87 views

Expected number of monomials in a random function over finite fields

Let $f : \{1,2\}^n \rightarrow \mathbb{Z}_3$ be a function from the multiplicative subgroup of order $2$ of $\mathbb{Z}_3$ over $n$ variables ($\{1,2\}^n$) to $\mathbb{Z}_3$, such that each coordinate ...
0
votes
0answers
47 views

Generators of $SL_2 (F_q)$

I am working on the following problem. Let $\mathbb{F}_q$ be a finite field with $q \neq 9$ elements and $a$ be a generator of the cyclic group $\mathbb{F}_q^{\times}$. Show that $\mathrm{SL}_2(\...
3
votes
1answer
35 views

Number of $2 \times 2$ matrices over the finite field $\mathbb{F}_q$ whose minimal polynomial is divisible by $X-1$.

I want to calculate the number of $2 \times 2$ matrices over the finite field $\mathbb{F}_q$ whose minimal polynomial is divisible by $X-1$. The characteristic polynomial must be $(X-1)(X-a)$ for ...
3
votes
3answers
99 views

Find $(1 + 2α)^{−1}$ in $F_{27}$.

Given : $f=X^3+2X+1 \in \mathbb Z_3[X]$ I have that deg $f$ = $3$ and it is irreducible in $\mathbb Z_3$ as $f$ has no roots in $\mathbb Z_3$: $f(0)=1, f(1)=1, f(2)=1$ in $\mathbb Z_3$: My Question:...
2
votes
2answers
51 views

Number of invertible elements in $\mathbb{F}_q[X]/\langle X^p-1\rangle$ with $p=\operatorname{char} \mathbb{F}_q$

I need to find the number of invertible elements in $\mathbb{F}_q[X]/\langle X^p-1\rangle$ with $p=\operatorname{char} \mathbb{F}_q$, which is equal to the number of invertible $p\times p$ circulant ...
0
votes
0answers
13 views

Calculate j-Invariant over $F_{p^2}$

I am studying the SIKE protocol and found a nice exposition in this link. On the second page of the link, the author lists the j-invariants in $\mathbb{F_{p^2}}$ for prime $p = 431$. I am trying to ...
0
votes
1answer
28 views

Can one construct a ${\rm GF}(p^m)$ without using Polynomials?

I am just learning about the finite field theory for channel codes. My understanding is that when constructing a ${\rm GF}(p^m)$, where $p$ is a prime number and $m$ is a positive integer, one has to ...
2
votes
4answers
63 views

Prove that $\mathbb{Z}[i]/(3)$ and $\mathbb{Z}[i]/(7)$ are finite fields and find their cardinality

In my rings subject's test I had to prove that $\mathbb{Z}[i]/(21)$ was decomposed as a product of two finite fields, and that was easy to prove for me because $21 = 3\cdot 7$, and $\mathbb{Z}[i]$ is ...
1
vote
0answers
48 views

Number of elements in the given construction of set cover

Consider the following construction that is used to form an instance of a set cover, taken from Vijay Vazirani (2003) Approximation Algorithms, $\S13.1.1$ Let $n=2^{k} - 1$, where $k$ is a positive ...
0
votes
2answers
28 views

Understanding proof of proposition $x \in F \to x \cdot 0 = 0$ where $F$ is a field.

Axioms: F1. addition is commutaitve: $x+y = y+x$, for all $x,y \in F$. F3. existence of additive identity: there is a unique element $0 \in F$ such that $x + 0 = x$, for all $x \in F$. F9. ...
-1
votes
1answer
36 views

How are the properties of $GF(p)$ different from $GF(p^{n})$? [closed]

I am trying to understand the concept of Galois fields from a beginner level, I read that Galois fields are of the form $GF(p^{n})$. What difference does it make conceptually to the properties of a ...
0
votes
0answers
19 views

How to partition boolean functions into CCZ(Carlet-Charpin-Zinovlev) equivalent classes

I'm doing some exercises for my course on Finite fields, and have a question regarding boolean functions. The question gives me several (7,7) functions and asks me to partition them into CCZ ...
0
votes
1answer
47 views

Compute the order of $GL_d(\mathbb{Z}/p\mathbb{Z})$

Here $p$ is prime and $GL_d(\mathbb{F})$ denotes the group of invertible $d\times d$ matrices over the field $\mathbb{F}$. I have seen several posts computing the order of $GL_2(\mathbb{Z}/p\mathbb{Z})...
1
vote
0answers
22 views

Applying Artin-Wedderburn to Finite Semisimple Rings example (720)

I am trying to apply Artin-Wedderburn to finite semisimple rings, but I am getting confused on determining the isomorphism classes. For an example, suppose I am trying to find all semisimple rings of ...
-1
votes
1answer
83 views

Determine the number of irreducible polynomials of degrees 2, 3, and 6 over the prime field $\mathbb F_p$.

Determine the number of irreducible polynomials of degrees 2, 3, and 6 over the prime field $\mathbb F_p$. Hint: Count all polynomials of a given degree. Which of these are reducible?
0
votes
1answer
51 views

What is the Galois Group of $x^4+1$ over $\mathbb{F}_3$ and describe the action of the group on the roots of it's polynomial

I know the Galois Group is cyclic of order 2 and I got the splitting field to be $\mathbb{F}_9$ but I don't understand how to write the frobenius automorphism that describes the action
2
votes
2answers
39 views

Structure of ideals in $\mathbb{F}_q[G]$

Let $\mathbb{F}$ be a finite field of characteristic $p$ and let $G$ be a cyclic group of order $p^n$. I read in a paper that all ideals of the group ring $\mathbb{F}[G]$ are of the form $I_n^j$ where ...
2
votes
1answer
37 views

Determining rank of a matrix over $\mathbb{F}_2$.

We are given a $(2n,2,2n) \times (2n,2,2n)$ matrix $A$ over $\mathbb{F}_2$ as follows: $$A= \begin{bmatrix} I & 0 & 1 \\ 0 & I & 1 \\ 1 & 0 & I \end{bmatrix}$$ Where $I$ is ...
1
vote
0answers
29 views

Elliptic curve in finite field, which solution to choose?

This is the elliptic curve I'm working with in the finite field of mod 37: $$ y^2 = x^3 - 5x + 8 $$ While trying to generate the set of points in it I noticed that, for $x = 5$, $$ y^2 = 5^3 - 5\...
1
vote
1answer
25 views

What does it mean “Lifting” from $Z_3[x]/\langle x^3-x-1\rangle$ to $Z[x]/\langle x^3-x-1\rangle$ exactly?

I have been reading a paper of a cryptographic algorithm. At some point, algorithm takes a polynomial f(x) that belongs to $Z_3[x]/\langle x^p-x-1\rangle$ and takes the lifting of this polynomial to $...
0
votes
1answer
39 views

The number of units in the quotient ring $\Bbb Z_5[x]/(x^4-1)$

I am asked to find the number of units in the quotient ring $\Bbb Z_5[x]/(x^4-1)$, where $\Bbb Z_5$ is the finite field consisting of 5 elements. I know that this ring has $5^4$ elements (which is not ...
2
votes
1answer
27 views

Every irreducible polynomial over $\mathbb F_p$ has a root in $\mathbb F_{p^{\deg f}}$ [duplicate]

I found the following question in my Galois theory book: Let $F$ be a field with $|F|=p^2$ for some prime $p$. Show that $a^2=5$ for some $a\in F$, and generalize this statement. My supposed proof ...
0
votes
0answers
12 views

Field on 3 bit-string set with uniformly distributed mapping.

I'm wondering if it's possible to construct a set S consisting of three bit-strings and some uniform mapping F: S x S -> S (...
0
votes
1answer
49 views

The degree of the irreducible factors of $r^{th}$ cyclotomic polynomial over a finite field.

I'm having trouble verifying the following proposition after Lemma 4.6 in the paper PRIMES is in P: Let $Q_r(X)$ be the $r^{th}$ cyclotomic polynomial over $\mathbb{F}_p$. The Polynomial $Q_r(X)$ ...
1
vote
1answer
33 views

Galois group of $GF(p^n): \mathbb{Z}_p$

I’m struggling to understand one part of this proof. I understand that the size of $GF(p^n)$ over $\mathbb{Z}_p$ is $n$ and that the Frobenius automorphism $\Phi$ is an element of the Galois group. I ...
4
votes
4answers
179 views

Any element $g$ of $GL(2,p)$ of order $p$, $p$ prime, is conjugate to $\begin{bmatrix}1&1\\0&1\end{bmatrix}$

Any element $g$ of $GL(2,p)$ of order $p$, $p$ prime, is conjugate to $\begin{bmatrix}1&1\\0&1\end{bmatrix}.$ I showed that $\langle g\rangle $ acts on the set $X$ of vectors with entries ...
1
vote
1answer
33 views

Semifields of order 8 are fields

I need to proof that semifields of order 8 are all fields. (S, +, *) is semifield if: 1) (S, +) is abelian additive group 2) (S \ {0}, *) is a loop 3) left and right distributive properties: (a + b)c =...
2
votes
3answers
63 views

A question in proof of a theorem in finite fields

I am unable to think about an argument while studying the section Finite Fields from Algebra by Thomas Hungerford. My question is - How $m_k(\sum Z_{m_i} ) $ = 0 implies that each u belonging to ...
1
vote
0answers
39 views

Every algebraic extension of a finite field is a finite extension. True or False? [duplicate]

If $F$ is an algebraic extension of a finite field $K$, then $F/K$ is separable. If we are able to show that $F/K$ is normal, then $F/K$ would be a Galois extension and hence splitting field of a ...
4
votes
1answer
83 views

Why study algebraic varieties over an algebraic closure of the finite field?

Let $\mathbb{F}_q$ be a finite field and $I = \langle f_1,\ldots,f_r \rangle \subseteq \mathbb{F}_q[x_1,\ldots,x_n]$ an ideal. Let me write $V(I)$ for the set $\{x \in \mathbb{F}_q^n : f(x) = 0 \text{...
0
votes
1answer
23 views

All Possible Polynomials With Max Degree 2 in GF(3)

How many max degree 2 polynomials (not necessarily irreducibles) are there with coefficients in $\{0, 1, 2\}$? There are $3$ choices for coefficients in $3$ positions. For example: $[]x^2 + []x + []$. ...
3
votes
1answer
99 views

A curve over a finite field with apparently no points

I am probably making a really silly mistake but I can't figure it out: Let $\mathbb F_q$ be a finite field and $a$ an element in it that is not a square. Let $E$ be the elliptic curve corresponding ...
0
votes
1answer
18 views

Is this finite field arithmetic?

I just found out about finite fields because of AES but I think it's may have illuminated something about the Pollard Rho Brent prime decomposition algorithm for me: ...

1 2 3
4
5
83