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)$.
1
vote
0answers
15 views
Efficient calculation of difference sets from finite fields
A while ago I wrote a program to generate, amongst other things, difference sets from finite fields. Generating these sets is rather slow. Is there some theorem or construction I could use to speed it ...
1
vote
1answer
35 views
Is there an easy expression for multiplicative inverses in $\mathbb Z_p$?
I know that in arbitrary division rings, one can go about finding inverses Euclidean division. But take $\mathbb Z_{11}$ as a simple example. Is there a "nice" expression which yields the inverses in ...
1
vote
2answers
36 views
A question about the degree of an extension field
Consider $f(x) := x^3+2x+2$ and the field $\mathbb{Z_3}$. $f(x)$ is obviously irreducible over $\mathbb{Z_3}$. Let $a$ be a root in an extension field of $\mathbb{Z_3}$, then why is it that $[\mathbb{...
0
votes
0answers
6 views
$\mathbb{F}_{p}(t)$ separable over $\mathbb{F}_{p}(f(t)/g(t))$ when $\deg(f), \deg(g) < p$.
Let $f(t), g(t) \in \mathbb{F}_{p}[t]\setminus \{0\}$ where $t$ is an indeterminate, and where $\max\{\deg(f), \deg(g)\} < p$ and $f(t)/g(t) \not\in \mathbb{F}_{p}$. Show that the extension $\...
1
vote
1answer
14 views
A question about finite field extension of a finite field
Let $K$ be a finite extension field of a finite field $F$. Show that there is an element $a\in K$ s.t. $K = F(a)$.
My attempt:
$K$ is a finite field and $char(K) = char(F) := p$. I know that for a ...
2
votes
0answers
33 views
A problem about the field of rational functions over finite field
Let $p$ be a prime number, and let $F_{p}$ be the finite field with $p$ elements. Let $F=F_{p}(t)$ be the field of rational functions over $F_{p}$ . Consider all subfields of $F$ such that $F/C$ is a ...
2
votes
2answers
65 views
Factorization of a polynomial in $\Bbb F_7$
I need to reduce as much as possible the polynomial: $x^6+3x^5+2x^4+6x^3+4x^2+5x+2$ in the finite field $\Bbb F_7$.
It has no roots over the field, and I don't think that it is necessary to check ...
4
votes
1answer
49 views
Low-degree polynomial $T\in\mathbb F[x,y]$ with $T(P(z),Q(z))=0$
Given polynomials $P,Q\in\mathbb F[z]$ over a finite field $\mathbb F$, one can find a non-zero polynomial $T\in\mathbb F[x,y]$ such that $T(P(z),Q(z))=0$ for any $z\in\mathbb F$. Is there a way to ...
2
votes
2answers
31 views
elliptic curve over nonprime finite field $\mathbb{F}_{p^n}$
I am currently trying to conceptualize what an elliptic curve over the finite field $\mathbb{F}_{p^n}$ looks like where $p$ is an odd prime.
I have never taken a course on field theory so I am still ...
-1
votes
0answers
33 views
Algebraic Closure of a Finite field [on hold]
On a textbook I read:
"Any polynomial $f\in\mathbb{F}_q[x]$ has $deg(f)$ roots in $\overline{\mathbb{F}}_q$"
What does this really mean? It seems very obvious, is there something I am missing?
0
votes
0answers
24 views
Bounding the exponent in unit groups of modular group algebras
Let $p$ be a prime number, $G=:G_0$ a (non-Abelian) finite p-Group and $K$ a finite field with $\operatorname{char}(K)=p$. It is well-known that the group $G_1:=1+\operatorname{rad}(KG)$ is a p-group ...
0
votes
1answer
49 views
Understanding algebraic closure of finite fields
From Wikipedia I learn that finite fields are not closed: If $F$ has $a_1,\dots,a_n$ then one could construct a polynomial $f(x) = (x-a_1)\cdot \ldots \cdot (x-a_n) + 1$ which has no roots (no zeros ...
1
vote
0answers
6 views
A question to the ascending central chain in modular group algebras
Let $p$ be a prime number, $G$ a finite p-Group and $K$ a finite field with $char(K)=p$. It is well-known that the group $1+rad(KG)$ is a p-group containing $G$. Let us focus on the sequence $G\cdot ...
0
votes
0answers
62 views
Group of units of a field
So I'm a bit confused with this... I'm learning some field theory and I've just learnt about groups of units. With rings this makes sense. However say $F$ is a field then isn't every element in $F$ ...
0
votes
0answers
14 views
Construct parity check matrix of binary Goppa Code
I am working out on a problem given in the book Theory of Error-correcting codes by MacWilliams and Sloane. The problem is to construct a parity check matrix for a classical binary $[8,2,5]$ Goppa ...
2
votes
2answers
89 views
Number of n-tuples in $\{0, 1, 2\}$ with sum less than or equal to $d$.
I would like to know if there is an expression for the number of n-tuples of $\mathbb{Z}$, where each component is an integer between $0$ and $2$, and the sum of the components is less than or equal ...
0
votes
1answer
24 views
Computing minimal polynomial in finite field F8
In a finite field $F_q$, I've read that one can get the minimum polynomial $f(z)$ of an element $\beta \in F_q$ using this formula:
$$f(z) = (z-\beta)(z-\beta^2)(z-\beta^4)(z-\beta^8)...$$
I'm ...
0
votes
1answer
39 views
Factoring $9788111$ via Gaussian elimination over $\mathbb F_2$
I am trying to follow page 142 to page 144 of An Introduction to Mathematical Cryptography by Hoffstein, Pipher & Silverman, where they give an example using Gaussian elimination over $\mathbb F_2$...
2
votes
1answer
45 views
Least period of the Fibonacci sequence in a field
Actually, I'm solving some exercises from the book "Finite Field" by Rudolf Lidl et al.
There is an exercise for which the idea is missing to solve it:
Let $r$ be the least period of the Fibonacci ...
2
votes
1answer
59 views
Niho APN prove that $gcd(d − 1, 2^n − 1)$ , where d is exponent
in a finite field $F_{2^n}$
where
$
d =
\begin{cases}
2^t + 2^{t/2}-1 & \text{t even}\\
2^t + 2^{(3t+1)/2}-1 & \text{t odd}
\end{cases}
$
and $n=2t+1$
How do you prove ...
0
votes
0answers
28 views
Why is $GF(p^n)$ unique? [duplicate]
I'm having trouble understanding why exactly $GF(p^n)$ is unique up to isomorphism.
I know that the proof begins by claiming that $GF(p^n)$ is the splitting field of the polynomial $x^{p^n}-x\in \...
0
votes
1answer
20 views
If $[K:F] = 3$, show a non square in $F$ is a non square in $K$ [duplicate]
Let $F \subset K$ be finite fields with $[K:F] = 3$. Show that if $\alpha \in F$ is not a square in $F$, it is not a square in $K$.
My attempt:
$[K:F] = 3 \implies \forall x \in K$, $x = \beta_1a_1 +...
0
votes
1answer
12 views
Compute a polynomial with a specific root by composing a set of other polynomials
Let $G$ be a finite field. and let $S = \{f | f ∈ G[X]\}$ where $S$ is a finite set and the degree of any polynomial in $S$ is at most $n$. Is there a way to compute a polynomial $F = f_1 ∘ f_2 ∘ ... ∘...
1
vote
1answer
37 views
Show that the polynomial $x^{q^n}-x$ does not split over $\Bbb F_q$
Show that the polynomial $x^{q^n}-x$ does not split over $\Bbb F_q$.
I don't know where should I start. Should I rewrite and expand $x^{q^n}-x$?
1
vote
1answer
16 views
Proving the ideal generated by subset of a ring is the set of linear combinations of the subset and the ring.
Let $I(X)= \cap \lbrace I \subset R | X \subsetneq I \rbrace $ where $I \subset R$ is an ideal. I want to prove that $I(X)$ is equal to:
$$A= \lbrace a \in R |a=\sum_{i=1}^{n}r_{i}x_{i} \quad r_{i} \...
2
votes
2answers
54 views
Write down the $8$ elements of $ F_2[x]/(x^3 + x + 1) $ in terms of α
Consider the field $F_2[α] = F_2[x]/(x^3 + x + 1)$, where $α$ is the image of $x$ in $F_2[x]/(x^3 + x + 1)$. Write down the $8$ elements of this field in terms of $α$.
I have no clue how to start ...
0
votes
0answers
24 views
least degree divisor of $x^p -1$ in $Z_{q}[x]$
For p a prime and q a prime power (q not a power of p), I'm trying to find the polynomial divisors of $x^p -1$ in $Z_{q}[x]$. In particular, I'm hoping to present a general idea of the minimum degree ...
0
votes
1answer
31 views
Splitting field of irreducible polynomial over finite field
Let $\mathbb{F}_q$ be a finite field with $q=p^r$ elements where $p$ - prime. Let $f(x)\in \mathbb{F}_q[x]$ be an irreducible polynomial of degree $n$. Am I right that $\mathbb{F}_q[x]/\langle f(x)\...
3
votes
3answers
118 views
Number of matrices with zero determinant
I want to count matrices over finite field with zero determinant.
For example, the numbet of $2\times2$ matrices over $\Bbb{Z}_4$ with zero determinant is 88 by hand computations.
On the other hand ...
0
votes
0answers
23 views
$\sqrt 2$ in $F_p$ [duplicate]
Is there a way to find out if $\sqrt 2$ exists in $F_p$ depending on p?
0
votes
0answers
47 views
Galois group of a polynomial of degree 5
I have a symmetric polynomial $p(x) = x^5+a_4(y)x^4 + a_3(y)x^3+a_2(y)x^2+a_1(y)x+a_0(y)$ over the ring $F_q[x,y]$ where $F_q$ is a finite field with $q$ elements.
With experiment, i know that in ...
0
votes
0answers
17 views
Is it possible to find $x$, knowing the following: $((z_1s_2 - z_2s_1) (v_1 s_1 - v_2 s_2))^{p-2} (\text{mod } p)$
This puzzled me over the last weekend, before everything let me say it's quite possible that the equation doesn't have a "solution" but it is a special case that follows from a solution. In any case, ...
3
votes
1answer
54 views
Is there a principal maximal ideal in $\mathbb F_q[X,Y]$? [duplicate]
Given an infinite field $K$, one can prove that any maximal ideal of $K[X,Y]$ can't be principal. In fact, every non-principal prime ideal is a maximal ideal, and can be generated by two polynomials.
...
0
votes
0answers
20 views
Algorithm for multiplication in finite field
I am trying to understand multiplication in finite fields. I have understood the usual multiplication method for multiplying two polynomials in a finite field. But I am unable to understand the ...
3
votes
1answer
96 views
Irreducible Polynomials In $F_3$
Let us say I have some irreducible polynomials in $F_3$
$$p(x) = x^3 + 2x + 2$$
and
$$p(x) - 1 = x^3 + 2x + 1.$$
Now, using the power of Maple and Wolfram Alpha, we can check that
$$p(x^{13}) = x^{...
0
votes
0answers
28 views
how $𝑎^𝑒𝑢^𝑒 +𝑎^{𝑒−1}𝑢^{𝑒−1}𝑏+𝑎𝑢𝑏^{𝑒−1} +𝑏^𝑒$ is derived from $(𝑎𝑢+𝑏)^𝑒$ in $F_{2^{2𝑛}}$?
from the paper : Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem (Full Version)
We represent an element $𝑥$ of $F_{2^{2𝑛}}$ as a linear polynomial $𝑥 = 𝑎𝑢 +...
2
votes
0answers
29 views
DFT modulo $p$: how to find the primitive root $\omega_n$.
On complex numbers:
Suppose that we want to find the DFT of the polynomial $A$ given in coefficient form
$$a = (a_0, ..., a_{n-1})$$
where $n$ is the length $a$.
What we do is to
Find the $n$th ...
1
vote
0answers
18 views
Equivalence between valuations
let $k$ be a finite field and $K=k[t]$ be the function field in one variable. Show that a non-trivial, non-Archimedean absolute value $\|\cdot\|$ on K is equivalent to $|\cdot|_{\mathbb{P}}$ for some ...
2
votes
1answer
46 views
Existence of irreducible polynomials with certain criteria
Let $\mathbb{F}_{q}$ be the finite field with $q$ elements, where $q$ is an odd prime power. The question is as follows:
Does there exists $a\in \mathbb{F}_{q}^*\setminus (\mathbb{F}_{q}^*)^2$, such ...
1
vote
0answers
39 views
How many pairs $(A,B)$ such that $rank(A)=m, rank(B)=k$ and the equation $AX=B$ has solution?
I am trying to estimate the second value of adjencent matrice of graph. This is leading a problem in linear-algebra and combinatorics, particularly:
Let $\mathbb{F}_q$ be a finite field, $q=p^r$ ...
2
votes
0answers
32 views
Proving the mean zero condition for polynomials over finite fields by linear algebra
Let $q:=p^n$ with $p$ a prime and let $\mathbb{F}_q$ denote a finite field with $q$ elements. Consider the following result:
If $f\in\mathbb{F}_q[X]$ has $\deg f\leq q-2$ then $$\sum_{x\in \mathbb{F}...
0
votes
2answers
37 views
Is it true that no polynomial (with the exception of constant polynomial) have an inverse in $\mathbb Z/p\mathbb Z$ (where p is prime)?
I was solving the following exercise:
Find the inverse of $p(x) = 1 + x$ in $R[x]$ over $\mathbb Z/5\mathbb Z$ or show that it does not exist.
and finding that it does not exist because if there is ...
1
vote
1answer
33 views
Quadratic forms over $F_p$ in more than $2$ variables are isotropic
I'm trying to find all anisotropic quadratic forms over $F_p=Z/pZ$. I have found that "If $F$ is a finite field and $(V, q)$ is a quadratic space of dimension at least three, then it is isotropic" (...
1
vote
1answer
44 views
Precisely which polynomials vanish on $\mathbb{F}_{p^n}$?
Let $F$ be a field. Let $V \subseteq F^k$. Let $\mathcal{I} (V)$ be the ideal in $F[t_1, \ldots, t_k]$ of polynomials that vanish on $V$.
If $F=\mathbb{F}_{p^n}$ is a finite field, what is $\mathcal{...
1
vote
1answer
39 views
Show that $x^{p^m} - x$ divides $x^{p^n} - x$ if and only if $m$ divides $n$. [duplicate]
Working towards the complete classification of finite fields in our algebra class, some final book-keeping involved proving the above (for a prime $p$, $n \geq 1$).
I've tried comparing the ...
-1
votes
1answer
111 views
Prove that $f(x)$ and $g(x)$ do not have any roots in common.
Suppose that $a(x)f(x) +b(x)g(x) = 135$ where $a(x), b(x), f(x)$ and $g(x)$ are polynomials over $F$. Prove that $f(x)$ and $g(x)$ do not have any roots in common.
Any help is appreciated; thanks!
1
vote
2answers
45 views
Power functions generating finite fields
Let $q > 2$ be a prime number and consider finite field $\mathbb F_q$. I am interested in functions $f_a : \mathbb F_q \to \mathbb F_q$ defined as follows
$$
f_a(x)=x^a
$$
What should be a ...
1
vote
2answers
80 views
Show that $a^{p^n}=a\mod p$
My book says that for elements $\alpha$ in $\mathbb F_p$, where $p$ is prime, it holds that
$$
\alpha^{p^n}=\alpha,
$$
because of Fermat's little theorem, which says that
$$
a^p=a\mod p.
$$
Of course ...
0
votes
0answers
28 views
Anomalous EC and MOV attack
I'm reading Washington's book about elliptic curves and I am particularly interested about anomalous curves (p. 159):
Why should ord($E(Fq)) = q$ prevent the MOV-attack or what is the idea behind ...
4
votes
2answers
228 views
Do there exist finite commutative rings with identity that are not Bézout rings?
A similar question has been asked before: Example of finite ring which is not a Bézout ring, but has not been answered.
There also seems to be a dearth of resources online regarding this ...
