Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...

1
vote
1answer
42 views

Quotient $\mathbf{F}_3[X]/(X^5+1)$

Factor $X^5+1\in\mathbf{F}_3[X]$ into irreducibles. What does the quotient $\mathbf{F}_3[X]/(X^5+1)$ look like? Since $-1$ is a zero, we divide $X^5+1$ by $X+1$ using long division, to obtain $X^5+1=(...
0
votes
0answers
13 views

Irreducibility of $x^p-x-a$ [duplicate]

Suppose I consider the polynomial $x^p-x-a$ over a field $k$ of characteristic $p$, how does one show that either the polynomial is irreducible or it splits into linear factors? It is clear to me that ...
0
votes
0answers
37 views

Is it true that he polynomial $\frac{x^p- 1}{x-1}$ ($p$ is prime) is irreducible in $\mathbb{F}_2[x]$ iff $p$ is prime?

Is it true that the polynomial $\frac{x^p- 1}{x-1}$ ($p$ is prime) is irreducible in $\mathbb{F}_2[x]$ iff $p$ is prime? I know it will be true in $\mathbb Q[x]$. Can anyone please help me to ...
0
votes
0answers
15 views

Find irreducible binary polynomial of degree 5

I'm trying a brute force approach, evaluating every single polynomial of degree 5. I was decomposing them using Ruffini in order to check if they are irriducible. With this approach for example $x^5+...
1
vote
1answer
43 views

Can we find all the irreducible polynomials of $F_2[x]$?

Can we find all the irreducible polynomials of $F_2[x]$ of a degree $n$? Is the number of irreducible polynomial of $F_2[x]$ Infinite? I was to find if there is any degree $n$ such that there is no ...
0
votes
1answer
38 views

specific examples of algebraic closure on finite field

I want to confirm my understanding of algebraic closure for finite fields. What sorts of elements do the algebraic closures $\overline {\mathbb{F}_2}$, $\overline {\mathbb{F}_3}$, $\overline {\mathbb{...
2
votes
2answers
33 views

Calculations on $GF(16)$ find $0111/1111$

It's my first time doing finite field arithmetics. As an exercise, I want to find $0111/1111 \in GF(16)$ generated by $\Pi(\alpha)=1+\alpha +\alpha^4$ that is an irreducible polynomial. In ...
0
votes
1answer
49 views

A cyclic subgroup of order 3 of the Galois group $Gal(\Bbb{R}(x)/\Bbb{R})$

Let's consider the field $\mathbb{R}(x)$ formed by the quotients of $\mathbb{R}[x]$. We know that $A=\begin{pmatrix} \frac{-1}{2} &\frac{-\sqrt{3}}{2} \\ \frac{\sqrt{3}}{2} & \frac{-1}{2} \...
0
votes
0answers
22 views

Probability of linear independency of vectors under finite field

How can I compute the probability of linear independency of m vectors under finite field? The vectors length assumed to be equal to n and vector elements to be random uniformly distributed. Thank you ...
1
vote
0answers
19 views

Finding minimum weight codewords in a Code over F9.

Hello everyone reading this. I seem to have a problem understanding weights in Coding Theory, and will attempt to provide a solution to a problem - please correct me where I am wrong. Consider the ...
0
votes
1answer
66 views

Question regarding algebraic closure of$ \mathbb{F_2}$

Let $\mathbb{F_2} $ be the finite field of order $2$. Then which of the following statements are true? $1.$ $\mathbb{F_2} [x]$ has only finitely many irreducible elements. $2.$ $\mathbb{...
4
votes
2answers
54 views

Finding elliptic curves achieving the upper and lower bounds of Hasse's Interval

I always thought that Hasse's bound is sharp (at least for elliptic curves). In other words I always thought that given a prime number $p$, I can find two elliptic curves $E_1,E_2$ over $\mathbb F_p$ ...
0
votes
0answers
51 views
+100

$\operatorname{ord}_p(\sum_{i=0}^{p-1}T(\overline i)^{p-1-k}ψ(\overline i))=?$

Let $Z_p$ denote the p-adic integers. Let $T:\mathbb{F_p}\to Z_p$ be a function with the following properties: $\forall x \in \mathbb{F}_p[\overline {T(x)}=x]$ $\forall x \in \mathbb{F}_p[T(x)^p=T(x)]...
3
votes
5answers
43 views

Let k be a finite field. Is it true that the number of irreducible polynomials in k[x] is also finite?

I know this question has been asked before and I understand that it can be proved using the same sort of proof as the one used to show that there's infinite primes, but are there other ways of showing ...
0
votes
0answers
59 views

Find the invertible solutions of $x^{-1}+x=0$ over a ring.

Let $(R, +, \times)$ be a finite ring with identity $1$. There are two notations:The set of all invertible elements in $(R, \times)$ and the set of all nonzero elements in $R$, are denoted by $R^\...
1
vote
1answer
65 views

When does Fermat's Last Theorem hold over finite fields?

It is well-known that in his attempts to prove Fermat's Last Theorem (FLT) over $\mathbb Z^+$, Schur came up with a result that has come to be known as Schur's Theorem, which implies that FLT fails ...
0
votes
0answers
19 views

Probability of lying in the intersection of two subspaces over a finite field

Let $A$ be a subspace spanned by $d_A\leq M$ linearly independent $M$-dimensional vectors whose elements are uniformly randomly drawn from a finite field $\mathbb{F}_q$ of size $q$. Let $\mathcal{B}$ ...
1
vote
1answer
30 views

When is an element of an extension field in the base field?

Given a finite field $\mathbb{F}_p$, consider an extension of it; $\mathbb{F}_{p^m}$. If I'm given $\alpha \in \mathbb{F}_{p^m}$, then, if $\alpha^p = \alpha$, $\alpha \in \mathbb{F}_{p}$. Why is ...
0
votes
0answers
25 views

Relation between finite fields $F_{p^2}$ and $F_p(\omega)$.

Let $F_p$ be a finite field having $p$ elements(for some prime $p$), not having primitive $3$rd root of unit say $\omega.$ Then can i say that field $F_p(\omega)$ and $F_{p^2}$ are isomorphic. I ...
7
votes
1answer
173 views
+50

The number of non-singular $n\times n$ matrices over $\mathbb{F}_2$ with exactly $k$ non-zero entries

Suppose $M_{n}^{k}$ is the number of non-singular $n\times n$ matrices over $\mathbb{F}_2$, that have exactly $k$ non-zero entries. Is there some sort of formula to calculate $M_n^k$? If $k < n$ ...
4
votes
1answer
78 views

Write the algebraic closure of $F_p$ as union of finite fields

In Field theory by Steven Roman Chapter 9 Exercise 20, if we write the algebraic closure of finite field $F_q$ as $\Gamma(q)$ and $a_n$ be any strictly increasing infinite sequence of positive ...
8
votes
0answers
63 views

An abelian variety not isogenous to a Jacobian

In the L-functions and Modular Forms Database is an isogeny class of an abelian variety of dimension $2$ over $\mathbb F_5$. They claim that it is principally polarizable but not the Jacobian of a ...
1
vote
0answers
42 views

factors of $X^{p^n}-X$

I'm my study of Galois theory I have been struggling with the following proposition without much success: The polynomial $X^{p^n}-X$ is precisely the product of all the distinct irreducible ...
1
vote
2answers
38 views

$\mathbb{F}_{p^d}\subseteq\mathbb{F}_{p^n}$ if and only if $d$ divides $n$ [duplicate]

I am trying to solve the following exercise of Dummit and Foote Book(page # 551). Let $a>1$ be an integer. Prove for any positive integers $n,d$ that $d$ divides $n$ if and only if $a^d-1$ ...
3
votes
0answers
28 views

Unramified primes inside $\mathbb{F}_q(t)$

I have some questions about the following statement: Let $P \subset \mathbb{F}_q(t)$ be a prime, with $q=p^e$ for a prime number $p$ and $f$ a polynomial of degree $n$ with coefficients inside $\...
1
vote
1answer
30 views

Left inverse of a matrix $3 \times 2$ in $\mathbb{F}_7[x]$

Do you know a method to calculate inverse matrix in $\mathbb{F}_7[x]$? I want to calculate left inverse the following matrix of $3 \times 2$ in $\mathbb{F}_7[x]$ \begin{bmatrix} x^2+1 & x-1 \\ ...
2
votes
1answer
40 views

Factorising $X^{16}- X$ over $\mathbb F_4$.

I need to factorise $X^{16}- X$ over $\mathbb F_4$. How might I go about this? I have factorised over $\mathbb F_2$ and I know the quadratic must split but I'm not sure about the quartic and octic. Is ...
0
votes
1answer
23 views

Finite Field Subtraction {0, 1, x, y} [closed]

In a finite field {$0, 1, x, y$} how does subtraction work? Let's say I want to do $y-y$ what does this equal?
0
votes
1answer
25 views

Finite field generator exponentiation properties

For a finite integer field $\mathbb{Z}_n$ with a generator $g$ and $x\in\mathbb{Z}_n$, a property I do not understand arises and I have not come across an explanation for it. If another set of values $...
0
votes
0answers
36 views

Two finite field of same order is isomorphic. Simplest way to prove it.

I want to prove that two finite field of same order is isomorphic. I have thought something. My attempt : If $f$ be a field of order $p ^m $ then $(f,+)$ is $z_p × z_p × .......z_p$. $(f , .) $ ...
1
vote
1answer
31 views

Degrees in Monomials

I am looking over the Joux-Vitse algorithm paper whereby they present an algorithm that seems to outperform exhaustive search and some state-of-the-art algorithms. However, it only works with ...
2
votes
3answers
42 views

Does there exist a prime $p$ such that $X^4+X+1$ splits into a product of irreducible quadratics over $\mathbb F_p$?

Does there exist a prime $p$ such that $X^4+X+1$ splits into a product of irreducible quadratics over $\mathbb F_p$? I have checked a few primes but I just get a single linear factor out, or it is ...
1
vote
0answers
15 views

Fast modular composition and irreducibility testing

Given a polynomials $f\in F_q[t]$ we want an algorithm that says if $f$ is irreducible or not. In the book "Modern Computer Algebra" by von zur Gathen and Jürgen Gerhard, an algorithm for that is ...
2
votes
1answer
51 views

A linear combination of the set $\{ {\bf A},{\bf A}^T\}$

Consider $\mathbf{A}$, an $n \times n$ matrix over $\mathbb{F}_q$, the finite field with $q$ elements. The transpose of $\mathbf{A}$ is denoted with $\mathbf{A}^T$. Let $\mathbf{I}_n$ denote the ...
2
votes
2answers
57 views

Galois group of $f(x)=x^5+2x+1\in\mathbb{Z}_3[x]$

consider $f(x)=x^5+2x+1\in\mathbb{Z}_3[x]$,what is the splitting field of $f$ and its Galois group? I know it is a Galois extension. But i do not know the degree of the extension for i have no idea ...
0
votes
1answer
34 views

Galois Field Matrix Multiplication for 512 bit number

I am a beginner in the filed theory. So, I have a few questions. Consider a matrix $A$ whose each element is in $GF(2)$ (i.e. $0$ or $1$) and a matrix $B$, each element of which is of $512$ bits. If ...
0
votes
0answers
21 views

Proof verification: Is 3 a square is every field $\Bbb{F}_{p^2}$, where $p>3$ is a prime?

I tried to prove it in this way: Let $p(x) = x^2 - 3 \in K[x]$, where $K = \Bbb{F}_{p^2}$. Because $\Bbb{F}_{p}$ is isomorphic to a subfield of $K$, we can make a reasoning in the following way: If $...
0
votes
0answers
20 views

Finding a congruence chain (linear and quadratic) equivalent to a polynomial

I want to find a congruence chain (linear and quadratic) equivalent to $2x^2+3x-k \equiv 0 (\mod5)$, with $k \in \mathbb{Z}$. I've started with considering the polynomial for $x=1,2,3,4$ but I don't ...
1
vote
1answer
43 views

Characterising the irreducible polynomials in positive characteristic whose roots generate the (cyclic) group of units of the splitting field

For a nonzero element $\alpha \in \mathbb F_{p^n}$ (the finite field of cardinality $p^n$) is there a simple criterion to tell whether $\alpha$ is a generator of the cyclic group $\mathbb F_{p^n}^\...
1
vote
1answer
41 views

Gauss sum possible typo

Let $ψ: \mathbb{F_p} \to Z_p$ with the property $ψ(a+b)=ψ(a)ψ(b)$ where $Z_p$ denotes the p-adic integers. Assume further that $ψ$ is not trivial. I'm trying to follow my professor's work, but I ...
0
votes
0answers
20 views

Cyclotomic cosets and minimal polynomials

Let $\mathbb{F}_{p^m}$ be a field and let $\alpha \in \mathbb{F}_{p^m}$. Let $M^{(i)}$ be the minimal polynomial of $\alpha^i$. Then I know that $M^{(i)}(x) = \prod_{j \in C_s} (x - \alpha^j)$, where $...
1
vote
1answer
56 views

$\mathbb{F}_q(t)$ vs $\mathbb{F}_q[t]$?

I am having certain troubles understanding certain manuscript. What is the difference between $$ \mathbb{F}_q(t) \quad \text{ and } \quad \mathbb{F}_q[t]? $$
0
votes
1answer
23 views

$f(x)\in \mathbb F_p[X]$ irreducible. Then a splitting field for $f(x)$ has $p^n$ elements

Let $\mathbb F_p$ be a field with $p$ elements and consider f$f(x)\in \mathbb F_p[X]$ irreducible of degree $n$. Then a splitting field for $f(x)$ has $p^n$ elements. Write $S_f$ for the splitting ...
4
votes
0answers
102 views

Trying to understand why the zeta function is a rational function under certain conditions. Questions about some equations.

Information: I linked the pages below, which relate to my questions. I am currently reading " A Classic Introduction to Modern Number Theory " by Kenneth Ireland and Michael Rosen. In the 11th ...
1
vote
1answer
88 views

Question about characters ( Section : The Rationality of the Zeta Function associated to $a_0x_0^m+a_1x_1^m+…+a_nx_n^m$ )

I am currently reading " A Classic Introduction to Modern Number Theory " by Kenneth Ireland and Michael Rosen. In the 11th chapter they consider the zeta function. In the third section of this ...
1
vote
2answers
44 views

Prove $V$ over finite field of $q$ elements can be written as union of $q + 1$ proper subspaces

Let $V$ be a vector space (can be finite or infinite) over finite field $K$, such that $\dim V > 1$ and $|K| = q < \infty$. Prove there exist proper subspaces $V_0, \dots, V_q$ such that $V = ...
1
vote
1answer
76 views

Can this algorithm be fixed?

Consider the following algorithm from page 240 of this pdf: Irreducibility-Test(f) 1 $n ← \deg(f)$ 2 if $X^{p^n} \not\equiv X (\mod f)$ 3 $\quad$ then return "no" 4 for the prime divisors $...
0
votes
0answers
35 views

multiplication of polynomials in $\mathbb{F}_2[x]$

Let $p(x) = 1 + x + x^2$ and $q(x) = 1 + x + x^3$. Then is the multiplication $p(x)q(x)$ obtained like this: $$p(x)q(x)= (1 + x + x^2)(1 + x + x^3) = 1 +x +x^3 + x + x^2 + x^4 + x^2 + x^3 + x^5 $$ $$=...
2
votes
1answer
54 views

How can I prove that $(x^3-y^2)$ is a radical ideal in $\mathbb{F}_2[x,y]$?

In an algebraically closed field, it's easy to verify that $(x^3-y^2)$ is a prime ideal, hence a radical ideal. However, $\mathbb{F}_2$ is not algebraically closed. So how can I prove this?
0
votes
0answers
12 views

I wander the order of $1+\gamma_p$, $\gamma_p$ is a element of order p.

Let $F_{2^t}$ be a finite field ,since the multiplicative group $F^*$ is cyclic. There exist a element of order p $\gamma_p$ where $p|2^t-1$. I wander the order of $1+\gamma_p$. Is there any theorem ...