Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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