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)

0
votes
1answer
22 views

Polynomials in $\mathbb{F}_{q}[x]$ invariant under translation of $x$

Let $p$ be prim, $r \in \mathbb{N}_{>0}$ , $q = p^r $ and $ K := \mathbb{F}_{q}$ the finite field with $q$ elements. Let $F$ be the set of polynomials, which do not change under translation: $$ ...
5
votes
3answers
4k views

How many irreducible polynomials of degree $n$ exist over $\mathbb{F}_p$?

I know that for every $n\in\mathbb{N}$, $n\ge 1$, there exists $p(x)\in\mathbb{F}_p[x]$ s.t. $\deg p(x)=n$ and $p(x)$ is irreducible over $\mathbb{F}_p$. I am interested in counting how many such $...
0
votes
0answers
23 views

Tensor product and dual of vector spaces

Consider $\mathbb{F}$ the algebraic closure of a finite field with characteristic $p>0$, and let $\mathbb{F}_q$ the unique subfield of $\mathbb{F}$ with $q=p^\alpha$ elements. So if we have $J$ ...
38
votes
2answers
587 views

Shortest irreducible polynomials over $\Bbb F_p$ of degree $n$

For any prime $p$, one can realize any finite field $\Bbb F_{p^n}$ as the quotient of the ring $\Bbb F_p[X]$ by the maximal ideal generated by an irreducible polynomial $f$ of degree $n$. By dividing ...
1
vote
2answers
78 views

Splitting field of $x^9-x$ over $\mathbb{Z}_3$.

Let $F$ be a splitting field of $x^9-x$ over $\mathbb{Z}_3$. $1$. Show that there is an $\alpha \in F - \mathbb{Z}_3$ such that $\alpha^2=2$. $2$. Show that $\mathbb{Z}_3(\alpha)$ is a splitting ...
1
vote
2answers
29 views

Extension of a finite field to a finite non commutative ring

Can a finite field be extended to non-commutative finite rings so that not all elements of the field commutes with the elements of the ring? I have been trying this taking the examples of matrices.
2
votes
1answer
57 views

extending rational functions over finite fields

This is probably similar to the question in the link, but i'm not sure how to solve it either.. I want to prove $\mathbb F_p(t)/\mathbb F_p(t^p-t)$ is Galois, compute its Galois group, and describe ...
1
vote
1answer
41 views

Proving an extension is galois and describe its automorphisms

I have the extension $\mathbb F_3[A]/\mathbb F_3$ where the $A$ are the roots of $x^{80}-1$. I need to prove this extension is Galois, find the Galois group, and describe the automorphisms. but I'm ...
3
votes
1answer
23 views

Common generator of units in finite prime fields

It is well known that the unit group of a finite field is cyclic. What can we say about the generators? Specifically I am interested in the following question: Suppose we fix a positive integer $a$, ...
1
vote
2answers
81 views

Irreducible polynomial in finite-fields

Let $\overline{\mathbb{F}}_2$ be an algebraic closure of $\mathbb{F}_2$, and let $\alpha\in\overline{\mathbb{F}}_2$ be such that $\alpha^2+\alpha+1=0$. Prove that if a polynomial $P$ is irreducible in ...
3
votes
0answers
39 views

Counting couples of square-free polynomials over finite fields

I have a curve defined by the following equations over the finite field $\mathbb{F}_q$ with $q=p^r$ with $p \geq 3$: $$C_{h_1,h_2}:\begin{cases} y_1^2=h_1(t) & \\ y_2^2=h_2(t) &...
3
votes
2answers
43 views

generalization of positive-definite matrices to matrices over finite fields

Let $\mathbb{F}$ be a field, $\mathbb{F}^n$ be the $n$-dimensional vector space over $\mathbb{F}$, and $M_{n\times n}(\mathbb{F})$ be the space of $n\times n$ matrices with entries in $\mathbb{F}$. We ...
1
vote
0answers
39 views

Probability that an arbitrary element of a field has a specific structure.

This question is related to : http://crypto.stackexchange.com/questions/37351/encoding-an-element-in-r-rhr-way that I asked couple of weeks ago. The difference is that I did not take the collision ...
3
votes
1answer
70 views

Algebraic or Analytic Proof of a Polynomial Identity

Let $m$, $n$, and $r$ be integers with $0\leq r \leq \min\{m,n\}$. Define $$f_{m,n,r}(q):=\left(\prod_{j=1}^r\,\left(q^m-q^{j-1}\right)\right)\,\left(\sum_{\substack{{j_1,\ldots,j_r\in\mathbb{Z}_{\...
0
votes
0answers
22 views

How to make check matrix H when you have generator matrix (algorithm)

It's all built on top of python numpy lib. So we have a class finite field and get access to elements of field like Finite_field[index_of_element]. Elements of field are numpy matrices(ndarray). For a ...
1
vote
2answers
35 views

Group $G$ cyclic as it coincides with the multiplicative group of a finite field

I have a group $G=(\mathbb{Z}_{251}^{*}, \cdot)$ with generator $g=71$ (so, having a generator, I'm given with the fact that is cyclic, right?) further in the example of my study notes I read: "$n = |...
1
vote
0answers
17 views

the multiplication of a coset of an additive subgroup of a finite field

I have a problem linking the multiplication in a finite field with its additive structure: The set $S$ is an additive subgroup of $\mathbb{F}_{2^h}$ (the finite field of order $2^h$). I have two ...
2
votes
1answer
58 views

Solvability and reducibility of a polynomial in a “chain” of finite fields

This question is generalized based on my previous question: Is $x^5 + x^3 + 1$ irreducible in $\mathbb{F}_{32}$ and $\mathbb{F}_8$? Problem: Consider an irreducible polynomial $f = x^4 + x^3 + 1$ in ...
1
vote
0answers
49 views

Intersection of two sets of rationals

I'm looking to see if anyone has any solutions or references for this problem. I'm not even sure of a proper category. It seems like it should be trivial, perhaps I'm missing something obvious. ...
1
vote
3answers
42 views

Calculate multiplicative inverse of $95$ in group of order $n=101$ which is subgroup of $(\mathbb{F}_{607}^*,\cdot)$

In the notes where I'm studying from there is written: "Let $G=\langle g\rangle$ be a subgroup of $(\mathbb{F}_{607}^*,\cdot)$ with $g=64$ and order $n=101$" but that felt strange to me; since I know ...
3
votes
4answers
456 views

Primitive polynomials

I am revising for a discrete mathematics exam and as quite stuck on this question. Show that the polynomial $f = x^2 + 2 x + 3 \in \mathbb{Z}_5[x]$ is primitive. How many monic primitive quadratic ...
4
votes
1answer
50 views

Is $x^{2\cdot 3^n}+x^{3^n}+1$ irreducible (mod 2)?

I'm new to the finite field theory, however after doing some trivial search on primitive polynomials, it seems that the polynomials of the form $$x^{2\cdot3^n}+x^{3^n}+1 \pmod 2$$ are irreducible. ...
3
votes
1answer
38 views

Generalizing Dirichlet characters

Suppose I want to consider Dirichlet characters $$\chi: \mathbb{F}_p(\zeta_r)^{*} \longrightarrow \mathbb{C}$$ Can I prove something similar to the Polya Vinogradov inequality for these characters? ...
4
votes
1answer
19 views

Distribution of sums of random variables over finite field

Let $q$ be an odd prime, $X_1, \ldots, X_n$ be i.i.d. random variables over $\mathbb Z_q$, and $0 < p < 1$ be some constant. Let $X_i$ take on the value $0$ with probability $p$, and the ...
6
votes
2answers
107 views

Is $x^5 + x^3 + 1$ irreducible in $\mathbb{F}_{32}$ and $\mathbb{F}_8$?

Problem: Is $f(x) = x^5 + x^3 + 1$ irreducible in $\mathbb{F}_{32}$ and $\mathbb{F}_8$? My thought: $f(x)$ is irreducible in $\mathbb{F}_2$ and has degree $5$. So we can conclude that $\mathbb{F}_{...
3
votes
1answer
25 views

Field and ideal notation: double bracks/parens vs single brackets/parens

I'm reading some notes that has the following denotation: the set of formal power-series with coefficients in $\mathbb{F}_p$ is denoted by $\mathbb{F}_p[[t]]$. the fraction field, $\operatorname{...
1
vote
1answer
55 views

Irreducible polynomials over $\mathbb{Z}_2[x]$

Prove that the polynomial $1+x+..+x^m$ is irreducible over $\mathbb{Z}_2$ if and only if $m+1$ is a prime number and 2 is a primitive root in $\mathbb{Z}_{m+1}$ Is there any proof without using ...
4
votes
2answers
169 views

Eigenvalues of matrices over finite fields

I apologize in advance if this is trivial, but I am a bit confused here. So consider the finite field $\mathbb{F}_{p^d}$ over the prime field $\mathbb{F}_p$. Wecan associate with every element $\...
2
votes
0answers
28 views

when do two elliptic curves over finite fields have a common point

Given two elliptic curves over $\overline{\mathbb{F}}_p$ in the form of trivariate degree $3$ polynomial we want to find whether they have a common intersection point. This is a decision problem(I don'...
4
votes
1answer
47 views

On Schoof's proof of deterministically finding $\sqrt{x} \bmod p$ when $p \neq 1 \bmod 16$

I am reading Schoof's paper in which he gave a polynomial time algorithm for counting points on an Elliptic curve over Finite field there he gave as an application an algorithm for deterministically ...
1
vote
3answers
61 views

prove that homomorphism (rings) from a field to ring is bijective or the zero homomorphism.

$F$ is a field and $R$ is a ring.$\:\phi :F\rightarrow R$ is a ring homomorphism. I need to prove that it is bijective or it is $\phi =0$. I tried to use some how the fact that I have opposites in F, ...
2
votes
1answer
42 views

Adjoin complex numbers to an arbitrary field? [closed]

This is probably nonsense but I'm throwing it out there. I don't think I can even explain the question very well: Has anyone seen bizarre things such as adjoining, say $i$ or $\pi$, to say a finite ...
1
vote
1answer
68 views

Finite Field Question: Which of the followings are true?

I have the following True or False question that I am having trouble getting it correct. I've written down my thoughts on each choice. If anyone could verify my thoughts or tell me where I made a ...
1
vote
0answers
67 views

How to determine redundant elliptic curves?

When we enumerate elliptic curves $y^2 = x^3 + ax + b$ over a finite field, how do we determine redundant ones, i.e. ones that are equivalent to others?
1
vote
1answer
49 views

Find the number of square matrices A of size n over the field $\mathbb F_p$ of $p$ elements such that $A^p = A$.

A question from entrance test of PRIMES 2016, namely M3. The solution says: The matrix has eigenvalues $0, 1, ...., p-1$ with eigenspaces of dimension $n_0, n_1, ...n_{p-1}$. The group $GL_n(\mathbb ...
3
votes
2answers
52 views

How do I find the order of an element if I am given the minimal polynomial of the element?

For example, let's say I am given an element $α$ in a field of characteristic $2$. Further, I am given the minimal polynomial of α with respect to $GF(2)$. Let's say that minimal polynomial is $f(x) = ...
5
votes
2answers
121 views

Properties of a finite field extension of degree 2.

I am bad (but trying to improve!) at very basic number theory and algebra. I'm quite sure this question is easy, but I do not know what fundamentals I am missing. This is from Ireland & Rosen's "...
1
vote
0answers
39 views

Binomial identity in a finite field

Suppose we have a prime $p$ and consider $\mathbb{F}_q$ where $q=p^s$ for some $s$. Fix a positive integer $m \geq 2$ and let $t \leq m-1$. Let $r$ be a positive integer such that $0 \leq r \leq q^t-1$...
1
vote
1answer
87 views

Dependence of algebraic elements in a finite field

Lets work over the finite field $\mathbb{F}_p$ for a prime $p$. Consider a monic irreducible polynomial $f(X)=X^3+aX^2+bX+c$ in $\mathbb{F}_p[X]$. Let $x$ be a root of $f(x)=0$ (say, in the closure of ...
5
votes
2answers
311 views

Elements in finite field extensions

Let $A,K$ be finite fields with $K\supset A$. If $[K:A]=3$, I would like clarification as to why, if $x$ is not a square in $A$, then $x$ is not a square in $K$. My notes just mention this fact, but ...
1
vote
3answers
53 views

How to evaluate GF(256) element

I wonder is there any easy way to evaluate elements of GF$(256)$: meaning that I would like to know what $\alpha^{32}$ or $\alpha^{200}$ is in polynomial form? I am assuming that the primitive ...
2
votes
1answer
46 views

Showing that $c_{i}\equiv 0\pmod{p}$

Let the numbers $c_{i}$ be defined by the power series identity $$\frac{1+x+x^{2}+\ldots+x^{p-1}}{(1-x)^{p-1}}= 1+c_{1}x+c_{2}x^{2}+\ldots$$ Show that $c_{i}\equiv 0\pmod{p}$ for all $i\geq 1$. $\...
0
votes
1answer
45 views

Is $Z_q[X]/(\phi(X))$ a field?

Let $\phi$ be an irreducible polynomial and $q$ a prime number. Let $R=Z_q[X]/(\phi(X))$ be the ring of polynomials modulo $\phi$ with the coefficients in $Z/qZ$. I wonder why $R$ is referred always ...
0
votes
1answer
22 views

How to make the probability that two random sets have any intersection close to zero (negligible)?

This question is related to one of my question: Probability that two random sets have at least one element in common Assume we have a field $\mathbb{F}_p$, where $p$ is a large prime number i.e. $...
2
votes
0answers
27 views

Extending a code by adding a parity check

Let $C$ be a $[n,k,d]_2$ code where $d$ is odd. It is known that you can construct a $[n+1,k,d+1]_2$ code by adding a column $\boldsymbol{c}_{n+1}$ to the codebook matrix where each element contains ...
1
vote
1answer
63 views

Simplification of a double summation in a polynomial ring over a finite field

I am looking out to simplify the following double summation in $\mathbb{F}_q[x_1,x_2]$, where $p$ is a prime and $q=p^k$ for some positive integer $k$ and a positive integer $r$ such that $0 \leq r \...
0
votes
0answers
45 views

Counting GF($q=8$) matrices with a certain property

Let us denote by $\boldsymbol{v}_i$ the columns of an $m \times n$ GF($8$) matrix. The field elements are enumerated $\{0,1,2,...,q-1\}$. To define the arithmetic operations between field elements, we ...
4
votes
2answers
48 views

Find roots of polynomial in a finite field

I need to build a field $L$ of 121 elements and find how many roots polynomial $g=x^9-1$ has in $L$. Then to find all these roots. So, $121=11^2$ this is power of prime. We can build finite field of ...
30
votes
2answers
8k views

Number of monic irreducible polynomials of degree $p$ over finite fields

Suppose $F$ is a field s.t $\left|F\right|=q$. Take $p$ to be some prime. How many monic irreducible polynomials of degree $p$ do exist over $F$? Thanks!
1
vote
3answers
83 views

What is the meaning of $\Bbb{Q}[x]/f(x)$?

I am very confused with the meaning of $\Bbb{Q}(x)/f(x)$. Does it mean the set of all polynomials modulo $f(x)$? If it does then how can we say that $\Bbb{R}[x]/(x^2+1)$ is isomorphic to set of ...