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