Tagged Questions

2
votes
0answers
32 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 ...
3
votes
1answer
72 views

Irreducible polynomial over $\mathbb Z/7\mathbb Z$

Is the polynomial $t^6-3$ irreducible over $\mathbb{Z}/7\mathbb{Z}$? How would you prove that without doing all the computations? Is there a general method for this? Thank you.
3
votes
1answer
43 views

Lagrange interpolation of Galois field functions

I'm trying to understand how to apply Lagrangian interpolation for a function $F : GF(2^k) \to GF(2^k)$, but am having some difficulty. Suppose I have a function $F : GF(2^2) \to GF(2^2)$ given by the ...
1
vote
1answer
38 views

Number of solutions of $P(x_1, …, x_n) = 0$ in $\mathbb{F}_q^n$

I have this exercise : $q = p^r$ (it is not clearly precised in the exercise that $r = n$). and $\mathbb{F}_q$ is the finite field of cardinal $q$. Let's $P \in \mathbb{F}_q[X_1, ..., X_n]$ of degree ...
1
vote
0answers
68 views

How does trigonometry in a Galois field work?

This is a follow-up to this question. I'm interested in doing trigonometry in finite fields on a computer. I do not understand precisely how trigonometric functions are supposed to work in a finite ...
8
votes
3answers
158 views

Why does rational trigonometry not work over a field of Characteristic 2?

I am interested in solving triangles in a finite field with a computer program. Rational trigonometry seems well suited to do this. However, the Wikipedia article, as well as several published ...
5
votes
1answer
82 views

Modules for twisted polynomial ring and Galois descent

Let $\mathbb{F}_q$ be a finite field with algebraic closure $\overline{\mathbb{F}}_q$ and consider the twisted polynomial ring $\overline{\mathbb{F}}_q\{ \tau \}$, where multiplication satisfies the ...
0
votes
1answer
34 views

Extension field

Let $E$ an extension field of $k$ of grade $n$. I want to know if for $\alpha\in E$ the minimal polynomial of $\alpha$ has degree $r\leq n$. I think is true, but i could use some help
5
votes
1answer
74 views

Find Galois Group

I want to know how to find a polynomial $f(x)$ of degree $6$ in $\mathbb{Q}[x]$ with Galois groups $G_f=\mathbb{S}_6$. I have a criterion to find a polynomial wich Galois group is $\mathbb{S}_p$ with ...
2
votes
1answer
102 views

Problem with roots of unity

Let $\zeta$ a root of $x^{p}-1$, with $p$ an odd prime, and $K$ a subgroup of the mutiplicative group $\mathbb{Z}_p^{*}$ of index $2$. I need to prove that $a=\displaystyle\sum_{k\in K}\zeta^{k}$ ...
2
votes
1answer
81 views

Cyclotomic polynomials, irreducibility [duplicate]

I need to decide if certain cyclotomic polynomials are irreducibles over the $\mathbb{F}_q$. For example, if $\Phi_{12}(x)$ is irreducible over $\mathbb{F}_9$. Anyone can help me? Ok, i think i ...
1
vote
4answers
102 views

Polynomial factorization over finite fields

How can i factorize the polynomial $x^{12}-1$ as product of irreducibles polynomials over $\mathbb{F}_4$? Anyone can help me?
-2
votes
1answer
91 views

When does a polynomial in $GF$ have a multiplicative inverse?

When does a polynomial in $GF$ have a multiplicative inverse? Are there values of $n$ such that all polynomials in $GF(n)$ have multiplicative inverses? EDIT: To address the comments, I mean: All ...
1
vote
1answer
64 views

Are all functions on vectors in GF(2^n) representable as polynomial functions?

In $GF(2)$, any function from an n-dimensional vector to a number is equal to a polynomial function of n variables. (See proof below.) Question: Is this true for other $GF$, especially $GF(2^8)$? ...
3
votes
2answers
76 views

Application of Hilbert 90 for Finite Fields

Let $k = \mathbb{F}_{p^n} = \mathbb{F}_q$ finite field of $q = p^n$ and $[K:k]=2$ Galois extension of degree 2. Then $K = \mathbb{F}_{q^2} = \mathbb{F}_{(p^n)^2} = \mathbb{F}_{p^{2n}}$. It is ...
2
votes
1answer
128 views

Existence of irreducible polynomial of arbitrary degree over finite field without use of primitive element theorem?

Suppose $F_{p^k}$ is a finite field. If $F_{p^{nk}}$ is some extension field, then the primitive element theorem tells us that $F_{p^{nk}}=F_{p^k}(\alpha)$ for some $\alpha$, whose minimal polynomial ...
6
votes
1answer
106 views

What does this notation mean: $\displaystyle\lim_{\leftarrow} \,\mathbb{Z}/n\mathbb{Z}$?

Just a small notation question from this Wikipedia page: The absolute Galois group of a finite field $K$ is isomorphic to the group $$\hat{\mathbb{Z}}=\lim_{\leftarrow} \mathbb{Z}/n\mathbb{Z}.$$ ...
1
vote
2answers
105 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 ...
0
votes
1answer
36 views

why using irriducible polinomial for galois field?

To construct the finite field $GF(2^{3})$ we need to choose an irreducible polynomial of degree $3$. Why we should choose an irreducible polynomial? I don't understand this lemma
5
votes
1answer
100 views

factorization of the cyclotomic $\Phi_n(x)$ over $\Bbb F_p$

One can prove that the $\Phi_n(x)$ are irreducible over $\Bbb Z$. Where $\Phi_n(x)=\prod _{(a,n)=1}\zeta_n^a$ (i.e the product of the primitive n-rooth of unity). I want to find a factorization of ...
3
votes
1answer
112 views

finite fields, a cubic extension on finite fields.

Let $q=p^n$ where $p$ is a prime number. For which $q$ is the extensión $\mathbb{F}_{q^3}/\mathbb{F}_q$ (i.e the extension of degree $3$) an extension of the form $\mathbb{F}_q(\root 3 \of \alpha )$ ...
1
vote
1answer
126 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 ...
6
votes
1answer
184 views

what simple extensions can be naturally embedded into Conway's algebraic closure of $\mathbb{F}_2$?

John Conway proved in his book, On Numbers and Games (ch6, theorem 49) that the set of all ordinals smaller than $\omega^{\omega^\omega}$ form a field of characteristic 2 that is isomorphic to ...
13
votes
2answers
414 views

Polynomials irreducible over $\mathbb{Q}$ but reducible over $\mathbb{F}_p$ for every prime $p$

Let $f(x) \in \mathbb{Z}[x]$. If we reduce the coefficents of $f(x)$ modulo $p$, where $p$ is prime, we get a polynomial $f^*(x) \in \mathbb{F}_p[x]$. Then if $f^*(x)$ is irreducible and has the same ...
7
votes
3answers
590 views

Galois Group over Finite Field

I am having a bit of difficulty trying to answer the following question: What is the Galois group of $X^8-1$ over $\mathbb{F}_{11}$? So far I have factored $X^8-1$ as ...
1
vote
1answer
199 views

Formal derivatives over finite fields.

I am slightly confused about what formal derivatives over finite fields mean. Example 1: Consider $f(x)=x^3-2\in \mathbb{F}_7[x]$. By checking each element of $\mathbb{F}_7$ we easily see that this ...
2
votes
1answer
181 views

General Primitive Element Theorem

I have a proof of the primitive element theorem for subfields $K$ of $\mathbb{C}$ which relies on there being infinitely many elements in $K$. In a book I've been reading it states that every finite ...
4
votes
2answers
126 views

Find all finite fields k whose subfields form a chain: if $k'$ and $k''$ are subfields of $k$, then either $k' \subseteq k''$ or $k'' \subseteq k'$.

Find all finite fields $k$ whose subfields form a chain: that is, if $k'$ and $k''$ are subfields of $k$, then either $k' \subseteq k''$ or $k'' \subseteq k'$. So, I understand that I'm trying to ...
3
votes
2answers
305 views

Show the norm map is surjective

Let $K/F$ be an extension of finite field. Show that the norm map $N_{K/F}$ is surjective. Here is what I have so far: Since $F$ is a finite field and $K/F$ is a finite extension of degree $n$, so ...
1
vote
1answer
132 views

Order and generator of the Galois group of an extension of finite fields

I'm trying to find the order and describe a generator of the group $$\mathrm{Aut}_{\mathrm{GF}(2^3)}(\mathrm{GF}(2^{12}))$$ It's clear that the order is 4, but how would you describe the generator? ...
2
votes
1answer
109 views

Extensions over finite fields

Let $K$ and $L$ be extensions of a finite field $F$ of degrees $n$ and $m$,respectively. How do I show that $KL$ has degree $\mathrm{lcm}(m,n)$ over $F$ and $K\cap F$ has degree $\gcd(m,n)$ over $F$? ...
1
vote
0answers
257 views

Generator and char. polynomial for a binary Galois Field produced by an external-XOR LFSR

My question is regarding LFSRs (Linear Feedback Shift Registers), and the binary Galois Field produced by them (also commonly termed GF($2^n$) ). I understand that a given n-bit LFSR produces a ...
1
vote
1answer
56 views

Number of solutions to a 0-1 non-linear integer program

When all the input variables $a_i$ are restricted to $\{0,1\}$, how does one compute the number of solutions to equations like $$ a_1a_4a_2 + a_1a_5a_3 + a_4a_6a_3 = c $$ where $c$ is a ...
1
vote
1answer
149 views

Product in GF(16)

i need some help with a product in GF(16), where it is seen as an extension of GF(4)={0, 1, x, x+1} (where $x^2 = x + 1$ ) with the irreducible polynom $f(y) = y^2 + y + x$ So the elements in the ...
4
votes
2answers
687 views

Constructing an explicit isomorphism between finite extensions of finite fields

Suppose $K$ is a finite field, $K = \mathbb F_{p^s}$. If we take an irreducible polynomial $f$ of degree $d$ over $K$, then the splitting field $L$ of $f$ is $K(\alpha)$ where $f$ is the minimal ...
2
votes
1answer
536 views

Splitting fields of polynomials over finite fields

I can't follow a statement in my notes: "Let $K$ be a finite field, with $f \in K[X]$ an irreducible polynomial of degree $d$. Then any finite extension $L/K$ is normal, and so if $L$ contains one ...
5
votes
3answers
2k views

Addition and multiplication in a Galois Field

I am attempting to generate QR codes on an extremely limited embedded platform. Everything in the specification seems fairly straightforward except for generating the error correction codewords. I ...
5
votes
2answers
325 views

Are quartic minimal polynomials over $\mathbb{Q}$ always reducible over $\mathbb{F}_p$?

This situation arose while studying biquadratic extensions. Let $\mathbb{Q}(\alpha)$ is some biquadratic extension, with $m(x)$ the minimal polynomial of $\alpha$. Suppose that ...
5
votes
2answers
831 views

reducible polynomial modulo every prime

how to show that $x^4+1$ is irreducible in $\mathbb Z[x]$ but it is reducible modulo every prime $p$. For example i know that $\mod 2 $, $x^4+1=(x+1)^4$ . Also $\mod 3$,we have that $0,1,2$ are not ...
3
votes
4answers
624 views

Do finite algebraically closed fields exist?

Let $K$ be an algebraically closed field ($\operatorname{char}K=p$). Denote $${\mathbb F}_{p^n}=\{x\in K\mid x^{p^n}-x=0\}.$$ It's easy to prove that ${\mathbb F}_{p^n}$ consists of exactly $p^n$ ...
3
votes
2answers
719 views

Field Norm Surjective for Finite Extensions of $\mathbb{F}_{p^k}$

I'd rather not have the answer, because I feel like this should be a relatively easy question, and I'm just missing some key step, but could anyone give me a hint on showing that the norm (defined as ...