Stack Exchange Network

Stack Exchange network consists of 175 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 isomorphism type. It is usually denoted by $\mathbb{F}_q$ or $\operatorname{GF}(q)$.

0
votes
0answers
8 views

Grouping dependant variables

Given $ f: GF(2^n) \rightarrow GF(2^n)$ Divide the $n$ variables into $m$ groups such that changing the value of a variable in a specific group will only affect the values of the variables in that ...
2
votes
2answers
24 views

Is the rank of a matrix with coefficients $\{-1,0,1\}$ the same as the rank of the matrix with coefficients in $GF(3)$?

I have a set of matrices defined over the ring of the integers, which items are using only coefficients -1, 0 and 1. For example: $$ A = \left(\begin{matrix} 1 & 0 & -1 \\ -1 & 1 &...
1
vote
1answer
49 views

Number of distinct roots of $f(x) = x^n - d \in \mathbb{Z}_p[x]$ in its splitting field

Where $d \in \mathbb{Z}_p \setminus \{ 0\}$. I have two cases to consider: when $n \mid p$ and when $n \nmid p$. For $n \nmid p$ I found that there are $n$ distinct roots in its splitting field, $K$,...
0
votes
1answer
37 views

Why is the residue field of $Q_p$ isomorphic to $F_p$?

$\mathcal{O}=\{x\in Q_p:v(x)\geq0\}$ is a valuation ring $\mathfrak{M}=\{x\in Q_p: v(x)>0\}$ is the maximal ideal of $\mathcal{O}$ Why is $K=\mathcal{O}/\mathfrak{M}$ isomorphic to $F_p$, the ...
1
vote
0answers
30 views

field extension being algebraic is equivalent to every $K-$ algebra being an automorphism.

For a field extension $L\vert K,$show that the following statements are equivalent : $(i)$$L\vert K$ is algebraic. $(ii)$ For every $E\in${$E:E$ is a field with $K\subset E\subset L$},...
0
votes
1answer
24 views

Polynomial dividing a power of another polynomial

Let $f \in \mathbb{F}_{q}[x]$, and let $x^n - 1$ divide $f^{k}$ in $\mathbb{F}_q[x]$, for some natural number $k$. If $gcd(n,q) = 1$, then apparently I can deduce that $x^n - 1$ divides $f$? How is ...
0
votes
0answers
15 views

Inner product with values in a finite field over space of finite functions

Suppose we have $\mathbb{Z}_n$ the group of residues modulo $n$ and $\mathbb{F}_q$ a Galois finite field with $q$ elements where $q=p^m$ with $p$ prime and $m\in\mathbb{N}$ and suppose $n\vert q-1$. ...
0
votes
1answer
28 views

Associativity and commutativity of the Field of order 2, ${\mathbb{F}_2}$

Let ${\mathbb{F}_2} = \left\{ {0,1} \right\}$, with addition defined by $0 + 0 = 1 + 1 = 0$ ; $0 + 1 = 1 + 0 = 1$, and multiplication by $0 \cdot 0 = 0 \cdot 1 = 1 \cdot 0 = 0$; $1 \cdot 1 = 1.$ I ...
0
votes
0answers
21 views

When is a field element in its base field?

Let $q = p^r$ some prime power. Let $f \in \mathbb{F}_{q^m}$, some field extension of $\mathbb{F}_{q}$. Then, if $f = f^q$, then $x \in \mathbb{F}_q$. Why is this true? Is it simply because $x$ is a ...
1
vote
2answers
30 views

Product ring isomorphism from example 11.6.3 in Artin's Algebra

I am currently reading chapter 11.6 in Artin's Algebra on Product Rings. There's a proposition that says if $e$ is an idempotent element of a ring $S$ and $e' = 1 -e$ then $S \cong eS \times e'S$. I ...
1
vote
1answer
29 views

Why does the cardinality of the vector space over a finite field of characteristic $p$ have to be a power of $p$?

In a lecture note that I have, it is written that if $F$ is a field of $q$ elements of characteristic $p$, then $q = p^m$ for some $m>0$. To show this, observe that $F$ is a vector space ...
0
votes
1answer
32 views

Showing that $\{\overrightarrow x, \overrightarrow y, \overrightarrow z\}$ is linearly independent

If the field $\Bbb{F}_2$ is a set with 2 elements $\{0,1\}$ and the addition and multiplication operations are defined by $$0+0=1+1=0 , 1+0=0+1=1 , 0*0=0*1=1*0=0 , 1*1=1$$ and each element is its own ...
0
votes
0answers
10 views

Misprint in Fearless Symmetry by Ash and Gross? Conditions for Elliptic Curves.

On page 104 of the paperback edition of Fearless Symmetry by Avner Ash and Robert Gross, they give one way of thinking of elliptic curves as $y^2=x^3+Ax+B$ wherein $A$ and $B$ can be any fixed ...
0
votes
0answers
20 views

Irreducible polynomial with repeated root [duplicate]

I understand why given any field of characteristic zero any irreducible polynomial cannot have any repeated roots, by arguing that the derivative of the polynomial and the polynomial itself are ...
1
vote
6answers
49 views

Does $\mathbb{F}_9$ contain a 4th root of unity?

I realised that I don't know how to construct $\mathbb{F}_9$. I'm guessing that $\mathbb{F}_9 = \mathbb{F_3(\theta)}$, where $\theta$ is the root of some irreducible polynomial over $\mathbb{F}_3[x]$ ...
1
vote
0answers
14 views

Degree of non-degenerated Boolean function over field of prime order

This problem occurred when we were trying to analyze the degree of a Boolean function over fields of different prime order. Problem: For any prime $p$, assume $n$ is large enough, then any non-...
0
votes
0answers
18 views

differential uniformity solution of exponential box

BelT cipher uses a Pseudo-exponential substitution box. The $\lambda$ and z values selected for the the BelT gives a differential uniformity of 8. \begin{equation} exp_\lambda,_z (x) = \begin{...
1
vote
1answer
51 views

Prove the sum of the Mobius function over monic polynomials of degree $n$ is $0$ if $n > 1$

Let $\mu(m)$ be the Möbius function on monic polynomials in $\mathbb{F}_q[x]$ ($q$ is power of prime) where $\mu(m) = 0$ if $m$ is not square-free and $\mu(m) = (-1)^k$ if $m$ is square-free and can ...
0
votes
1answer
66 views

Is $X^8+a \in \mathbb{F}_{49}[x]$ irreducible?

Let $f(x) = x^8+a \in \mathbb{F}_{49}[x]$ with $a \in \mathbb{F}_{49}\setminus \{0\}$. Find all $a$ such that $f$ is reducible over $\mathbb{F}_{49}$! What I know is that $\mathbb{F}_{49} \cong \...
1
vote
1answer
71 views

How to show that there are infinitely many prime numbers $p$ such that the polynomial f has a zero in $\mathbb Z_p$? [duplicate]

Let $f\in \mathbb Z[X]$ be a polynomial of positive degree.How to show that there are infinitely many prime numbers $p$ such that the polynomial $f$ has a zero in $\mathbb Z/p \mathbb Z$ ? I have no ...
1
vote
0answers
22 views

Minimal polynomials of primitive elements compared to normal elements

Let $gcd(n,q)= 1$ Consider $x^n - 1 \in \mathbb{F}_{q}[x]$, and let $\mathbb{F}_{q^t}$ be a splitting field for $x^n - 1$ over $\mathbb{F}_q$. Then, $\mathbb{F}_{q^t}$ contains a primitive $n^{th}$ ...
1
vote
2answers
30 views

GCDs for the polynomial ring over a Galois field.

You can find many examples of computing the inverse of an element inside a Galois field. (For example here) What happens if we look at the polynomial ring over a Galois field and would like to ...
3
votes
0answers
54 views

Factoring $x^n - 1$ and minimal polynomials

Let $gcd(n,q) = 1$ I'm trying to get to grips with factorising the polynomial $x^n - 1$ over $\mathbb{F}_q$. Firstly, it is a good idea to find an extension field containing all the roots of $x^n - 1$...
0
votes
0answers
34 views

Modular Polynomial Arithmetic in Schoof's Algorithm

I've been trying to implement Schoof's Algorithm, and I understand it except for one part. Near the bottom of page 7 of this paper is where my issue is: http://www-users.math.umn.edu/~musiker/schoof....
0
votes
0answers
22 views

How to show that every element involving $x$ in $F_p(x)/F_p$ is not algebraic.

In the field extension $F_p(x)/F_p$, where $F_p(x)$ is the field of fractions of polynomials over $F_p$, is it by definition that $x \in F_p(x)$ is not algebraic? In other words, should I claim that $...
7
votes
1answer
82 views

Determine whether a polynomial is irreducible

Consider the polynomial $P=X^5-X-1\in\Bbb{F}_3[X]$. I want to show that $P$ is irreducible. We can easily check it has no roots, so the only way it could not be irreducible is by being a product of ...
1
vote
1answer
58 views

Finding square roots of quadratic residues in prime power field

I know that in fields of cardinality $p$, $a$ is a quadratic residue if and only if $a^{\frac{p-1}{2}}=1$ (Euler's criterion). Therefore $a^{\frac{p+1}{2}}=a$ and if also $p=3\!\!\!\mod\! 4$ we can ...
9
votes
2answers
109 views

Pattern of Newton-Raphson iteration $x\mapsto\frac{1}{2}(x+\frac{q}{x})$ over finite fields

While playing with Newton-Raphson method over finite field $\mathbb{F}_p$, I noticed some cute patterns that I can't explain out of my brain contaminated with analysis. Here is the setting: ...
0
votes
1answer
21 views

Help with a basic question on Finite Field characteristic [duplicate]

Let $F$ be a field of characteristic $p > 0$. Show that $(\alpha + \beta)^{p^m} = \alpha^{p^m}+\beta^{p^m}$, for all $\alpha,\beta \in F$ and $m > 0$. I am stuck on this question; can anybody ...
2
votes
0answers
43 views

Finite subgroup of the multiplicative group of a field is cyclic [duplicate]

Dummit and Foote's Abstract Algebra contains a proof that a finite subgroup of the multiplicative group of a field, $F$, is cyclic. However the seems unnecessarily complex to me. Certainly their ...
2
votes
0answers
25 views

Surjectivity of Lang map

Could we prove the surjectivity of Lang's map for $GL(N)$ without using algebraic geometry? In other words, given a invertible matrix $M$ in $GL_N(\mathbb{F})$, there exists another invertible ...
0
votes
2answers
69 views

How can the polynomial $x^7+1$ be factored in $\mathbb F_2$? [duplicate]

I want to factorize this polynomial $x^{7}+1$. The result that I expect is $(x+1)(x^{3}+x+1)(x^{3}+x^{2}+x+1)$ What is the best way to proceed? As it seems the factorization is conducted in $\...
0
votes
2answers
53 views

$\mathbb{F}_{4096}$,$\mathbb{F}_{16}$ and $\mathbb{F}_{2}$

I'm stuck at these two questions: i) How many distinct elements $a \in \mathbb{F}_{4096}$ exist, such that $\mathbb{F}_{4096}=\mathbb{F}_2 \left[a\right]$ ii) Find an irreducible $g \in \mathbb{F}_4 ...
1
vote
2answers
86 views

Factor $x^8-x$ in $\Bbb Z[x]$ and in $\Bbb Z_2[x]$

Factor $x^8-x$ in $\Bbb Z[x]$ and in $\Bbb Z_2[x]$ Here what I get is $x^8-x=x(x^7-1)=x(x-1)(1+x+x^2+\cdots+x^6)$ now what next? Help in both the cases in $\Bbb Z[x]$ and in $\Bbb Z_2[x]$ Edit: I ...
1
vote
1answer
32 views

How does a field extension maintain the field structure, and are all field extensions fields, or only algebraic extensions?

Suppose we adjoin a symbol $k$ to the field $F_p$, as in $F_p(k)$. What is an intuitive understanding of the structure of this field and its elements? Since multiplication needs to be closed, all new ...
0
votes
1answer
32 views

Criteria when $[ML:K]= [M:K] \cdot [L:K]$ holds

Let $K$ be a field and $M,L$ algebraic field extensions and $ML$ the composition/product field. I'm looking for some useful criteria when the equation $$[ML:K]= [M:K] \cdot [L:K]$$ holds. ...
0
votes
1answer
20 views

The degree of a splitting field over $\mathbb{F}_p$ of non-reducible monic polynomial of degree $n$

Let $f\in\mathbb{F}_p(x)$ be a monic irreducible polynomial, denoting $\deg(f)=n$. I wish to show (if it's true) that $f(x)$'s splitting field is $\mathbb{F}_{p^n}$. I did some manual test for some ...
0
votes
1answer
42 views

$x^2-3$ is separable over $\mathbb Q$ but not separable over $F_2$

$x^2-3=(x-\sqrt{3})(x+\sqrt{3})$ over $\mathbb Q$, so that part makes sense. Now, when it says $x^2-3$ is a polynomial over $F_2$, I imagine it means all the coefficients are calculated mod $3$, so $...
0
votes
0answers
22 views

For each $k = 0, \dots, 26$ count the number of ordered pairs $(a,b)$ in $\mathbb{F}_{27} ^2$ for which $a^k = b^2$

I believe we have to check all values of $k$. $k = 0$: $a^0 = 1 = b^2$. This holds for all $a\in \mathbb{F}_{27}$, so we just have to find all $b \in \mathbb{F}_{27}$ for which $b^2 \equiv 1 \text{ (...
0
votes
0answers
23 views

Splitting field of an irreductible polynomial $f(X) \in F_{q}[X]$

Let $F_q$ be a finite field ($q$ is a power a prime) and irreductible polynomial $f(X)\in F_q[X]$ with degree $n\geq 2$. I have to see that $F_{q^n}$ is the splitting field of $f$ over $F_q$, and ...
0
votes
1answer
42 views

Classify finitely-generated modules over $\mathbb{F}_2[x]/\langle x^2+x+1 \rangle$ up to isomorphism.

While studying the classification of finitely-generated modules over PIDs, I came across this exercise: Classify finitely-generated modules over $\mathbb{F}_2[x]/\langle x^2+x+1 \rangle$ up to ...
2
votes
2answers
53 views

Determine if an ideal is a prime ideal over $\mathbb{Z}_5[x]$

Conside the ring $<\mathbb{Z}_5[x],+,.>$. Is the ideal $ \langle1 + 3x + 3x^2 + x^3\rangle $ a prime ideal? If we have a ring of integers then we can simply check that if product of $a$ and $b$ ...
2
votes
2answers
40 views

Find the elements of the extension field using primitive polynomial over $GF(4)$

Let $p(z) = z^2 + z + 2$ be a primitive polynomial. I want to construct the elements of the extensional field $GF(4^2)= GF(16).$ Since $p(z)$ is primitive polynomial , it should generate the ...
6
votes
1answer
44 views

Verifying if a given polynomial is primitive polynomial

Given a polynomial: $f(x) = x^2 + 2x + 2$ over $GF(3)$. I want to know if i can use it to construct $GF(3^2)$. My approach: This equation satisfies first condition: A primitive polynomial is ...
0
votes
0answers
15 views

Linearity of the map Field Trace. [duplicate]

!I want to prove that this map is well-defined. I know that the image of 'a' is sum of all Galois conjugates of 'a' i.e. the roots of minimal polynomial 'a' over Fq. I can prove the linearty of this ...
3
votes
1answer
40 views

Lemma 2.1 of “A SUM-PRODUCT ESTIMATE IN FINITE FIELDS, AND APPLICATION”, by Bourgain, Katz and Tao

I am trying to understand Lemma 2.1 of this paper: https://arxiv.org/pdf/math/0301343.pdf. Can anyone explain to me explicitly the reason why we can assume WLOG that $|A||B|\leqslant |F|/2$? Many ...
0
votes
1answer
20 views

Finding the $\gcd$ of $a(x)$ and $b(x)$ in field $\mathbb{F}$

I'm trying to find the $\gcd$ of $a(x) = x^4 + 2x^3+x^2+4x+2$ and $b(x)=x^2+3x+1$ over $\mathbb{F_5}$. I've already tried Euclid's algorithm: $x^4 + 2x^3+x^2+4x+2 = x^2(x^2+3x+1) - x^3+4x+2$. Now I ...
0
votes
0answers
19 views

Solving quadratic equations in $\mathbb F_{2^h}$ using the sum and product rule.

In the finite field $\mathbb F_{2^h}$ with primitive element $\alpha$ consider the quadratic eqution: $$\alpha^ax^2+\alpha^b x+\alpha^c =0$$ In class we saw we could solve it using the subsition $y=\...
2
votes
2answers
49 views

Linear dependency in certain fields

EDIT: I made a vital mistake switching $4$ by $3$ Let $q$ be a prime number and $n\in\mathbb{N}$. Suppose that $q^n\equiv 1\pmod{3}$. Is it possible that there are $0\neq a,b\in \mathbb{F}_{q^n}$ ...
2
votes
1answer
55 views

Condition for roots of $x^2+xy+y^2\in\mathbb{F}_{q^n}[x,y]$

Let $q$ be a prime number and $n$ an integer. Is there some number theoretic condition involving the numbers $q,n$ that can tell me when is the polynomial $$x^2+xy+y^2\in\mathbb{F}_{q^n}[x,y]$$ ...