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
0
votes
2answers
1k views

Addition in $\operatorname{GF}(2^4)$

How can I compute $A(x)+B(x) \mod P(x)$ in $\operatorname{GF}(2^4)$ using the irreducible polynomial $P(x)=x^4+x+1$. What is the influence of the choice of the reduction polynomial on the computation? ...
7
votes
1answer
108 views

Why isn't the zero ring the field with one element?

I've heard that in the study of finite fields, and other concepts related to finite fields, mathematicians have found a sort of gap: there are various results and things that seem like they correspond ...
3
votes
1answer
449 views

Irreducible polynomial roots and representations for Galois field elements in normal basis

I am trying to understand some topics in the literature and came across the following problem. Say I have a field $GF(2^4)$ defined by the irreducible polynomial $r(z) = z^4 + z + 1$, and I want to ...
2
votes
3answers
53 views

The order of a finite field [duplicate]

I'm reading a theorem about the order of a finite field: Here is the proof: At the end, the author said It follows that $\mathbb{F}$ is a vector space over $\mathbb{F}_{p}$, implying that its size $...
3
votes
2answers
435 views

Transition between field representation

In a number of papers related to efficient implementation of the AES Sbox, people are computing stuff (the multiplicative inverse for instance) in GF(($2^4$)$^2$) instead of GF($2^8$). In some cases ...
2
votes
1answer
82 views

Is there a fast way to factor polynomials with finite field $\operatorname{GF}(p^k)$ coefficients?

For example the 33-term polynomial $x^{32} + c_{31} x^{31} + \ldots + c_1 x + c_0$, where the coefficients are 16-bit finite field numbers. For the cases I'm considering, the 33-term polynomial will ...
1
vote
3answers
54 views

What is the intuition behind mapping of elements from $GF(2^8)$ to $GF(((2^2)^2)^2)$?

I'm finding it very difficult to understand the concept of mapping elements from the extension field $GF(2^8)$, to $(GF(2)^2)^2)^2 $. I realize that the field that the elements of the field, $GF(2^8)$,...
-4
votes
0answers
34 views

If $K_{1}$ and $K_{2}$ are finite field and $K_{1}$ $\cong$ $K_{2}$, is $E(K_{1})$ $\cong$ $E(K_{2})$?

If $K_{1}$ and $K_{2}$ are finite field and $K_{1}$ $\cong$ $K_{2}$, is $E(K_{1})$ $\cong$ $E(K_{2})$ ? where $E(K)$ is elliptic curve over $K$.
1
vote
1answer
32 views

Proof for subgroup of SL(2,q)

In Suzuki's Group Theory I, Theorem 6.21 says Let $p$ be an odd prime number, and let $\lambda$ be an element of $F$ which is algebraic over the prime field $F_0=GF(p)$. Set $E=F_0(\lambda)$. Let $G$ ...
1
vote
3answers
790 views

Isomorphism for optimization of GF256 implementation in AES S-Box using intermediary finite fields

I've questions about the implementation of The S-Box in the AES cipher. In this cipher, the Finite Field GF256 is implemented as a quotient $\mathbb{F}_2[X]/(X^8+X^4+X^3+X+1$). The operations can be ...
11
votes
2answers
226 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: Setting. ...
1
vote
0answers
25 views

A generalization of quadratic forms over finite fields

Let $\mathbb{F}$ be a finite field, $V$ be a vector space over $\mathbb{F}$ and $\sigma$ be a field automorphism of $\mathbb{F}$. I would like to know if the following objects have been considered in ...
3
votes
1answer
87 views

Maximal ideals in $\mathbb{F}_q[x,y]$

Let $p \in \mathbb{P}$ be a prime and suppose that an integer $e > 1$ is given such that the polynomial $s_e = 1 + x + \dots + x^{e-1}$ is irreducible in $\mathbb{F}_p[x]$. My question is the ...
3
votes
1answer
62 views

Solution Verification: Factoring $\left|\begin{smallmatrix}x&y&z\\x^p&y^p&z^p\\x^{p^2}&y^{p^2}&z^{p^2}\end{smallmatrix}\right|$ over $\mathbb{Z}_p.$

Problem: Factor $\begin{vmatrix} x & y & z \\ x^p & y^p & z^p \\ x^{p^2} & y^{p^2} & z^{p^2} \end{vmatrix}$ over $\mathbb{Z}_p$ as a product of polynomials of the form $ax+by+...
4
votes
1answer
78 views

Is $(A+B)$ necessarily singular?

Let $A, B$ be two orthogonal matrices over a field $F$ of characteristic $2$ such that $$\det (A) + \det (B) = 0.$$ Is $(A+B)$ necessarily a singular matrix? I have proved the result to be true for ...
0
votes
0answers
13 views

Mean and variance of rank of a random matrix over finite field

I am trying to understand the statistics of the rank of a random matrix over a finite field, and some search brought me this paper. In Corollary 2.2 the paper gives the number of $k\times n$ matrices ...
1
vote
2answers
75 views

A property of finite fields [closed]

Why does the remark in Wiki's proof of Warning's theorem true? If ${\displaystyle i<q-1}$ then ${\displaystyle \sum _{x\in \mathbb {F} }x^{i}=0}$ Best regards
1
vote
1answer
68 views

Find a subspace of $(\mathbf{Z}/2\mathbf{Z})^{64}$ with some conditions!

in order to solve a little problem that give me a friend, I have the following question: Is it possible to find a subspace $W$ of the $\mathbf{Z}/2\mathbf{Z}$-vector space $(\mathbf{Z}/2\mathbf{Z})^{...
1
vote
1answer
41 views

SageMath: defining class of functions on Elliptic Curves

In SageMath, I would like to manipulate rational functions on elliptic curves (defined on finite fields). For example, for $P = (x,y)$ on some curve $E$ $$f = x+y-12$$ $$g = \frac{x+y-3}{(x-3)^2} $$ ...
0
votes
1answer
23 views

Number of elements in a set of orthogonal matrices

Let $S$ be defined as $$S:= \left\{ M \in \mathbb{F}_3^{2 \times 2} : M \text{ is orthogonal} \right\}$$ where $\mathbb{F}_3$ is a field with $\mathbb{F}_3 = \{ 0, 1, 2\}$. How many elements does the ...
0
votes
0answers
66 views

Chevalley–Warning theorem's proof

I'm struggling to prove Chevalley–Warning theorem, i.e. only the part which shows that the number of common solutions ${\displaystyle (a_{1},\dots ,a_{n})\in \mathbb {F} ^{n}}$ is divisible by the ...
13
votes
3answers
5k views

Irreducible polynomials have distinct roots?

I know that irreducible polynomials over fields of zero characteristic have distinct roots in its splitting field. Theorem 7.3 page 27 seems to show that irreducible polynomials over $\Bbb F_p$ have ...
6
votes
1answer
83 views

Which linear maps on a finite field are field multiplications?

I am mainly interested in the fields $\mathrm{GF}(2^n)$, but the question can be asked for any prime. We can write out each element $x\in\mathrm{GF}(2^n)$ in base $2$ and note that its additive group ...
0
votes
2answers
40 views

What is the cardinality of a vanishing set?

In Wiki's page on Chevalley–Warning theorem, under "Statement of the theorems", it's written that Chevalley–Warning theorem states that [...] the cardinality of the vanishing set of ${\...
2
votes
1answer
32 views

Rank of matrix over $GF(2)$ whose rows have exactly $k$ elements $1$ [closed]

Consider the $\binom{n}{k}\times n$ matrix $A$ whose rows have $k$ $1$'s and $n-k$ $0$'s. There are no repeated rows. What is the rank of $A$ over $GF(2)$?
1
vote
0answers
16 views

A quadratic solution and its conjugate

Let $\mathbb{F}_q$ be a finite field of $q$ elements such that $q=p^{t}$. Let $\alpha$ be a solution of the equation $Ax^2 +Bx +C=0$ and $\alpha'$ its conjugate, where $A$, $B$ and $C$ are nonzero ...
6
votes
1answer
52 views

Elliptic Curve r-torsion points: Trace and AntiTrace

I am reading Pairings for Beginners from Craig Costello (pdf available for free, just google it) on page 53-55, We consider an elliptic curve E defined on a finite field $F_q$ with q prime q. We are ...
0
votes
1answer
22 views

$A\in \mathbb{F}_q$, then there exists $n\in \mathbb{Z}_{\geq 0}$ such that $A \in \mathbb{F}_{q^n}$ a perfect square.

I was wondering whether the statement in my title holds. I think it does, but I am not sure. I have managed to prove it for the case $A = -3$, but not in the general case. Any ideas or tips?
0
votes
1answer
32 views

Question about some term in Sage while using GF(9)

I tried to define an elliptic curve over $GF(9)$ in Sage, and some term $z2$ appeared, see below (click on the image if the font is too small): I know that it has something to do with the definition ...
0
votes
1answer
46 views

Group / field extension solvability in the case of $x^3 - 2$

Whenever a polynomial is solvable by radicals, the Galois group of its splitting field must be a solvable group. A group $G$ is solvable if there are subgroups $H_0, H_1, \dots , H_n$ such that $$\ 1 =...
3
votes
3answers
92 views

Factorizing the polynomial $x^6-2x^3+8$ over finite fields

This is a very specific question. This equation came up when attempting to compute certain subgroups of groups of Lie type. The polynomial $x^6-2x^3+8$ splits over $\mathbb{F}_q$ if and only if a ...
2
votes
1answer
44 views

Any multiplicative subgroup of a finite field is cyclic

I asked for minimal hints in this question. Now I've come up with a proof. Could you please verify if it is fine or contains logical mistakes? Let $F$ be a finite field and $F^\times = F \setminus \{...
1
vote
0answers
26 views

solution to cube root of finite field

I'm trying to solve the following equation and I'm having trouble $$y^3 = (x)^e \pmod n $$ in my case $x^e = 124205, n = 129071$ I'm expecting this answer to result in $65$ (as this is the thing that ...
0
votes
2answers
69 views

Let $F$ be a finite field. Then the multiplicative group $(F \setminus \{0\}, \cdot)$ is cyclic

Let $F$ be a finite field. I'm trying to prove The multiplicative group $(F \setminus \{0\}, \cdot)$ is cyclic. Then I figure out that it's sufficient to prove Different multiplicative subgroups of ...
0
votes
0answers
39 views

Why is $|\langle A \rangle|$ odd?.

Let $A \in GF(2^r)$. Why is $|\langle A \rangle |$ odd? If $A$ is zero then it only maps to itself, leading the element to have an order of one. Hence, an odd order. Why can I claim for all non-zero ...
0
votes
0answers
28 views

Euler decomposition of symplectic matrix over finite field

Is there a finite field equivalent to the Euler decomposition of symplectic matrices? See previous post for the real version : Finding Euler decomposition of a symplectic matrix
2
votes
2answers
59 views

polynomials in $\mathbb F_p$

Let $p$ be a prime number and denote by $\mathbb F_p$ the field of integers modulo $p$. Like before, we can consider polynomials with coefficients in $\mathbb F_p$. Then, the polynomial $X^p − X$ is ...
1
vote
1answer
34 views

How to generate and solve finite fields and insure integers instead of decimals for coefficients and random points

Background: I have tried to follow this tutorial on secret sharing: https://medium.com/@apogiatzis/shamirs-secret-sharing-a-numeric-example-walkthrough-a59b288c34c4. I have managed to use Shamir's ...
7
votes
2answers
21k views

Galois Field GF(4)

Question: Why is the table of $GF(4)$ look like the one below? I know it has to do with the fact that 4 is composite Let $GF(4) = \{0,1,B,D\}$ Addition: $$ \begin{array}{c|cccc} + & 0& 1&...
2
votes
1answer
54 views

Finite field with 8 elements

I am trying to work out exercise 61 from Rotman's Galois Theory, second edition: 61. Give the addition and multiplication tables of a field having eight elements. (Hint: Factor $x^8 -x$ over $\mathbb{...
2
votes
2answers
98 views

Implications of zero elementary symmetric polynomials over a finite field

For a prime $q$ and an integer $n<q$, consider working over the finite field of $q^n$ elements. Denote by $s_n^k$ the $k$-th elementary symmetric polynomial in $n$ variables. That is, $s_n^k(x_1,\...
6
votes
2answers
82 views

Does $\Phi_n(\alpha)=0$ in $\Bbb{F}_p$ for some $\alpha\in\mathbb{F}_p$ imply that $\mathrm{ord}(\alpha) = n$?

Let $\Phi_n(x)$ denote the $n^\text{th}$ cyclotomic polynomial. Suppose it has a root $\alpha$ in the finite field $\Bbb{F}_p$ and $p \nmid n$. Does it follow that $\mathrm{ord}(\alpha) = n$? In the ...
10
votes
1answer
569 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 ...
0
votes
0answers
32 views

Every Galois field $F$ of characteristic $p$ is perfect

I'm trying to do Exercise 2.6.13 from textbook Groups, Matrices, and Vector Spaces - A Group Theoretic Approach to Linear Algebra by James B. Carrell. Could you please confirm if my attempt is fine or ...
1
vote
0answers
27 views

How to find the generators of the multiplicative group of a finite field

Input: p (prime number), n (positive number) Output: g ( generator ) I have just found an irreducible polynomial over $F_p[x]$. Now I must find all generators of the multiplicative group from this ...
1
vote
1answer
24 views

Show that $\psi_{b}=\psi_{c}\Leftrightarrow b=c$.

Let $K$ finite field with $|K|=p^{n}$,where $p$ is prime number.Let the transformation (Trace) : $$Tr:K\to K,\ Tr(a)=a+a^{p}+a^{p^{2}}+\cdots a^{p^{n-1}}.$$ For every $a\in K$ we khow it's true that $...
0
votes
1answer
53 views

The roots of an irreducible polynomial over $\Bbb Z_p$ and a useful equivalence

In the excellent expository papers of Keith Conrad, I stuck at a proof of a proposition in the Finite Fields. Proposition. Let $\pi(X)\in \Bbb Z_p[X]$ be an irreducible polynomial of $\Bbb Z_p[X]$ of ...
0
votes
0answers
21 views

Why is $\ \frac{1}{2}(p^{rmn-r})(p^r - 3)\ $ odd?

Let $p>2$ be prime and $m,n,r \in \mathbb{Z}^+$. Why is $$\frac{1}{2}(p^{rmn-r})(p^r - 3)$$ an odd number when $p \equiv_4 1$ or when $r$ is even? I'm not really sure how to approach this.
0
votes
1answer
15 views

How to get $(ab)1 = (a1)(b1)$ in Galois field?

I'm reading Galois field from textbook Groups, Matrices, and Vector Spaces - A Group Theoretic Approach to Linear Algebra by James B. Carrell. Here $r,a,b \in \mathbb N$ and $1 \in \mathbb F$. While ...
0
votes
0answers
20 views

Independence of coordinate functions on variable.

Consider a permutation $f : (\mathbb{F}_2^{n})^2 \to (\mathbb{F}_2^n)^2$. Let $(x,y) \in (\mathbb{F}_2^n)^2$ be any vector. Write $(z,w) = f(x,y)$. Suppose that I know that $x = 0 \iff z = 0$ and $y = ...

1
2 3 4 5
84