Tagged Questions

Finite fields are structures arising in abstract algebra. 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)$.

learn more… | top users | synonyms

1
vote
0answers
12 views

Arithmetic background of this RNG code

I am trying to figure out the mathematical background of the random number generation of an old video game. It does iterations where it updates a 33-bit state consisting of the variables z (32-bit) ...
2
votes
1answer
13 views

Is the Frobenius automorphism a polynomial?

Let $p$ be a prime and $\Bbb{Z}/\Bbb{Z}_p$ the field of integers mod $p$, and since $\Bbb{Z}/\Bbb{Z}_p$ is a field we have the ring of polynomials in $X$ with coefficients in $\Bbb{Z}/\Bbb{Z}_p$ ...
3
votes
0answers
61 views

On polynomials over finite fields?

Pick prime $q\in\Bbb Z$ such that $q>B^{3t}>((n+1)B)^{2t}$. Suppose I have a multilinear polynomial $g(x)\in \Bbb Z[x_1,\dots,x_n]$ of degree $t$ whose coefficients are bound by $|B|>2$, I ...
2
votes
0answers
33 views

Generators of group of “unitary” matrices over a finite field

This is about a group related to $U(n,q)$ and $SU(n,q)$. I know from multiple sources the generators for these groups, but $U(n,q)$ is defined to be the group of matrices $A$ such that $A^*JA = J$ ...
2
votes
0answers
43 views

How can I predict what numbers “work” without brute force?

I've been doing some research with LFSRs and I have found something I can't explain. I've worked on it for years but I'm finally opening up to public involvement because I can't stand not knowing. ...
1
vote
1answer
22 views

polynomial algebras and their coefficients in prime fields

According to the definition of the polynomial algebras $A(n)$ and $A(n,m)$ for $ n \in \mathbb {N} $ and $ m \in \mathbb {N}^n$, if $\mathbb{F}$ be field $GF(2)$ and $ X_1,...,X_n$ be $n$ pairwise ...
2
votes
1answer
30 views

How to partition a finite vector space into affine subspaces all of the same dimension

Given an $n$-dimension vector space $V$ over a finite field $\mathbb F_q$ and a natural number $d<n$, the goal is to write $V$ as disjoint union of $d$-dimensional affine subspaces $v_i+V_i$: $$V = ...
0
votes
1answer
33 views

Additive subgroups of the finite field GF($2^m$)

Consider the set $G=\left\{ {0,1,...,{2^m} - 1} \right\}$. The elements of this set can be viewed as the elements of GF($q=2^m$) with appropriate addition/multiplication operations. For example, GF(4) ...
3
votes
1answer
32 views

matrix rank over finite field

Let $M$ be a square matrix over finite field $\Bbb F_p$. Let $N$ be the matrix over $\Bbb F_p$ obtained replacing every non-zero entry of $M$ by $1$. Is $Rank(N)\leq Rank(M)^{f_p}$? for some constant ...
0
votes
2answers
21 views

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

How can one show that $\gcd(x^4+x+1,x^4-x)=1$ in $\mathbb{F}_2[x]$? Is it because the polynomials do not share any irreducible monic polynomials i.e. $1, x, x+1$ as factors?
0
votes
1answer
24 views

Splitting field of $x^ {a^n}$ −1 in Z/aZ[x]

What is the splitting field of the polynomial $x^ {a^n}$ −1 in \ the ring Z/aZ[x] with n natural? I´m working in some kind of proof of the best known theorem that says it´s impossible there exist a ...
-1
votes
1answer
39 views

Help with problem of the book Algebra of T. Hungerford

This is a problem in “Algebra” by T. Hungerford: If $|K|=q$ and $f\in K[x]$ is irreducible, then $f$ divides $x^{q^n}-x$ if and only if $\deg f$ divides $n$. I found it difficult to solve ...
0
votes
1answer
13 views

Explanation of division/reduction in a binary Galois Field using bit-shifts

I've seen a lot of algorithms reducing the result of a multiplication in a Binary Field by using only bit-shifts and XOR. The number of positions to shift seems to be derived from the polynomial, but ...
1
vote
0answers
13 views

Product of random binary vector with random binary matrix in GF(2)

Suppose we have a binary vector $f$ with dimensions $1×l$ such that each entry in the vector is generated independently with propability $q$ of being $1$. And we have a binary matrix $G$ with ...
2
votes
1answer
20 views

Show that a matrix is not diagonalizable over a finite field

I have a matrix: $$\ \left[ {\begin{array}{cc} 2 & 2 \\ 1 & 2 \\ \end{array} } \right] $$ which I need to show that it cannot be diagonalized over the finite field $\mathbb{F_3}$. ...
1
vote
1answer
28 views

How to find all of generators in a finite fields

How can I find all generators of a finite field? For example in GF(2^3) and X^3 + x^2 + 1 as primitive polynomial. I don`t want all of solutions. I need some hint and help to solve this problem. ...
3
votes
0answers
24 views

Irreducible representations of inhomogeneous linear transformations over $\mathbb{F}_q$

Let $\mathbb{F}_q$ be a finite field with $q$ elements and let $G$ be the group of inhomogeneous linear transformations over $\mathbb{F}_q$, that is $x\mapsto ax+b$ for some $a\in \mathbb{F}_q^*$ and ...
2
votes
1answer
24 views

What does it mean for two polynomials to be the same in this fundamental field extension theorem?

I just read about the following "fundamental" theorem of field extensions which is stated as follows: Let $F$ be a field, and let $\alpha$ and $\beta$ be elements of field extensions $K/F$ and $L/F$. ...
0
votes
0answers
16 views

$Z_p$ has a additive inverse (for all $a\in Z_p$)

Let there be a finite field donated $Z_p:p\in Primes$. prove that for all $a\in Z_p$ there is additive inverse. Due to the properties of $Z_p$, $m*P=o_F: m\in Z$ Let assume $(p-a)$ additive inverse. ...
0
votes
0answers
11 views

Why $f(0)\neq 0$ where $f $ is a polynomial over the field $F_q$ and $deg(f)=m > 0$?

To construct the Residue class ring $F_q[x]/(f)$ having $q^m-1$ non-zero elements. Is it necessary for $f(0) \neq 0$? Why or why not? I have worked with different examples such as $x^3+x=f \in ...
0
votes
2answers
60 views

Fields over which a matrix is not invertible

I am trying to find the fields over which the matrix: $\left(\begin{matrix} 1 & 2 & 3 \\ 0 & -1 & 2 \\ 1 & 0 & -2 \end{matrix}\right) $ is not invertible. I have ...
0
votes
2answers
28 views

How to handle negative numbers in modular arithmetic?

I have a constraint to use finite-field arithmetic in my application. Since I want it to resemble ordinary arithmetic as much as possible, I chose a large prime $p$ (e.g., $ p > 2^{256} )$, and I'm ...
0
votes
1answer
57 views

Field with 729 elements.

Let $\mathbb{F}$ be a field with 729 elements. How many distinct proper subfields does $\mathbb{F}$ contain. Please be generous and tell the reason also. Thanks.
1
vote
0answers
36 views

$f(x)=x^p-a$ is either ireducible or has a root? [duplicate]

Let $p$ be a prime number. Prove that for any field $k$ and any $a\in k$, the polynomial $f(x)=x^p-a$ is either irreducible or has a root. I think if $\operatorname{Char}k=0$ then $f$ is an ...
0
votes
0answers
31 views

How Would I Compute This Product? [duplicate]

$f$ is irreducible, How do I compute this $$\prod_{d\mid n}\prod_{f \in \mathbb{Z_p[x]},\, \deg(f) = d}f$$ I tried small examples for this: So $n = 1, p = 2$. We have that this product is: $x(x + 1) ...
1
vote
2answers
34 views

If $T$ be an invertible linear operator on a finite-dimensional vector space over a finite field , then $T^n$ is the identity operator?

If $T$ be an invertible linear operator on a finite-dimensional vector space over a finite field , then is it true that $T^n = I$ ( the identity operator) for some positive integer $n$ ?
1
vote
1answer
183 views

Number of roots of a polynomial over a finite field

For any $g$ in $\mathbb{Z}/p\mathbb{Z}[x]$ prove that the degree of $f = \gcd(x^p - x, g(x))$ is exactly the number of distinct roots of $g$ in $\mathbb{Z}/p\mathbb{Z}$. My main problem is that I ...
2
votes
2answers
28 views

Splitting field of $x^3 - 2$ over $\mathbb{F}_5$

I'm having some difficulty in finding the degree of the splitting field of a polynomial over a finite field. In particular $f = x^3 - 2$ over $\mathbb{F}_5$. This polynomial factorises as $f(x) = ...
0
votes
1answer
26 views

Confusion about coordinate function

Let $F_{27}=\{0, \alpha, \dots, \alpha^{26}=1\}$ and $B=\{1, \alpha, \alpha^2\}$ be a basis of $F_{27}$ over $F_3$ then an element $\alpha^k = c_1+c_2\alpha+c_3\alpha^2$ where $1\le k\le 26$. To ...
0
votes
1answer
16 views

Java efficient implementation of a finite field (for cryptography use)

Is there any popular robust implementation for a finite field in java? (An implementation of prime fields ,i.e. $GF(p)$ might also be good.
3
votes
0answers
31 views

Discrete Fourier Transform of a shift of a tuple over a finite field

Let $a = a_0 a_1 \cdots a_{N-1}$ be a sequence over a finite field $\mathbb{F}_q$, where $N \mid q^n-1$ for some $n$. Let $\xi_N$ be a primitive $N$-th root of unity in the extension ...
3
votes
4answers
215 views

How to find all irreducible polynomials in Z2 with degree 5?

I am totally lost on how to do this one. I am supposed to accomplish the following: Find all irreducible polynomials in $\mathbb{Z}_2[x]$ with degree $5$. I may use the fact that x, $x+1$ and ...
2
votes
0answers
32 views

Splitting field in finite field

What is the splitting field of the polynomial $X^{p^8}-1$ over $\mathbf F_p$? I'm confused, not is $X^{p^8}-1=(X-1)^{p^8}$ then the splitting field is $\mathbf F_p$? Thanks.
1
vote
1answer
16 views

Polynomial Factoring over a finite field

Ok, so I'm trying to figure out how to factor polynomials over a finite field. My polynomial is x^5 + x^2 + x + 1 and I have to factor over GF(2) I know the answer is (x+1)^2 * (x^3 + x + 1), because ...
-1
votes
1answer
31 views

Find the number of primitive elements

How can i find the number of primitive elements over the field of order q? GF(27) for example. Is there a formula that I can follow? I'm really confused on how to find them. Any help would be much ...
3
votes
3answers
83 views

Proving two finite fields are isomorphic

So I'm asked to prove that $\mathbb{F}_9$, defined as $\{ a+bi$ | $a,b \in \mathbb{Z}_3,$ $i^2 = 2 \}$, is isomorphic to the field $F_1$, defined as $\mathbb{Z}_3[x]/ \langle x^2+2x+2 \rangle$, where ...
0
votes
1answer
53 views

irreducible monic polynomials

Let $P_1,P_2,\dots $ be the irreducible monic polynomials in $\mathbb{F}_p[x]$. Is there any possibility to prove the following $$\lim_{n\to \infty } \sum_{i_1+\cdots+i_n=t}z^{i_1\deg P_1 + \dots ...
0
votes
1answer
33 views

Multiplication in the Galois field GF(3^3)

I am trying to compute $x^3$ in the Galois field $\text{GF}(3^3)$ using the irreducible polynomial $f(x) = x^3 + 2x^2 + 1$. From the expression $x^3 = f(x) + (2x^2 +1)$ I proceed to take the modulus ...
4
votes
1answer
34 views

Suppose $F$ is a finite field of characteristic $p$. Prove $\exists u \in F$ such that $F = \mathbb{F}_{p}(u)$.

Suppose $F$ is a finite field of characteristic $p$ ($p$ a prime). Prove $\exists u \in F$ such that $F = \mathbb{F}_{p}(u)$. Here, $\mathbb{F}_{p}$ denotes the field with $p$ elements. Here is ...
5
votes
3answers
38 views

Double finite field extension

Suppose we are given the field $\mathbb{F}_5$ and $p(X) = X^2-2 \in \mathbb{F}_5[X]$, an irreducible polynomial over $\mathbb{F}_5$. Let $\mathbb{K}$ denote the extension of $\mathbb{F}_5$ in which ...
0
votes
2answers
29 views

an irreducible polynomial over GF(2) is primitive over GF(2)

let $P \in F_{2} [X]$ of degree $7$, how to prove this: P is irreducible $\Leftrightarrow$ P is primitive i tried to use the mersenne prime !
1
vote
1answer
48 views

Compute the degree of the splitting field

I need to compute the degree of the splitting field of the polynomial $X^{4}+X^{3}+X^{2}+X+1$ over the field $\mathbb{F}_{3}$. Quite honestly I don't really know where to begin, I know the polynomial ...
0
votes
0answers
25 views

Describe all subgroups of $\operatorname{Inn}(\operatorname{GL}_2(\mathbb F_{p^n}))$

Is it possible to give a general discription of all subgroups of the group $\operatorname{Inn}(\operatorname{GL}_2(\mathbb F_{p^n}))$ of inner automorphisms of $\operatorname{GL}_2(\mathbb F_{p^n})$? ...
1
vote
1answer
19 views

When Errors Go Undetected in CRC

I understand that CRC will not be able to detect errors if: The remainder of $E(x) / G(x) = 0$ $E(x) = G(x).Z(x)$ for some polynomial $Z(x)$ I understand the first point, which means that if the ...
1
vote
0answers
44 views

Regarding Linear Subspaces over a Finite Field… TFAE:

Let $V=\mathbb{F}^n$, for a finite field $\mathbb{F}$. Prove the equivalence of the following statements: There is a linear subspace $C$ of $V$ with the property that every vector $v$ of ...
0
votes
0answers
17 views

Why does this criterion imply that $A$ is a subfield of $E$?

$E$ is an extension field of a field $F$ and $A$ is the subset of $E$ containing all the members algebraic over $F$. "To prove that $A$ is a subfield of $E$ it is enough to show that any two elements ...
2
votes
1answer
27 views

Elements of $\operatorname{SL}_2(\mathbb F_{p^n})$ of order $p^k$

Let $p > 2$ be a prime number and $n\ge 1$ an integer, and consider the group $G = \operatorname{SL}_2(\mathbb F_{p^n})$ of order $p^n(p^{2n} - 1)$. Let us denote by $\operatorname{Inn}(G)$ (the ...
1
vote
0answers
11 views

Characterise all subgroups of $\operatorname{SL}_2(\mathbb F_{p^n})$

The title pretty much explains everything. Is it possible to give an easy characterisation of all subgroups of $\operatorname{SL}_2(\mathbb F_{p^n})$?
1
vote
0answers
29 views

Number of orbits of the Frobenius automorphism

Let $q=p^s$ be a prime power congruent to $1$ modulo $4$, let $\mathbb{F}_q$ be the finite field with $q$ elements, and let $\phi$ denote the Frobenius automorphism (that is $\phi(a)=a^p$ for every ...
0
votes
2answers
45 views

Subgroups of $\mathbb F_{p^n}$

Is it possible to give a discription of the possible subgroups (with respect to $+$) of the finite field $\mathbb F_{p^n}$ (obviously, $p$ is a prime number). Of course, if $n = 1$, $(\mathbb F_p,+)$ ...