1
vote
1answer
35 views

Maps preserving roots of a polynomial function over finite fields

Let $P(x_{1},\ldots,x_{n}):\mathbb{F}_{2}^{n}\rightarrow \mathbb{F}_{2}$ be a polynomial function with degree $d$ and with variables $x_{1},\ldots,x_{n} \in \mathbb{F}_{2}$. Let $S(P)=\{ ...
1
vote
0answers
28 views

Version of Chevalley's Theorem proving $\mathbb{F}_q$ is a $C_1$-field for $\mathbb{Z}/p^n\mathbb{Z}$?

Let $k=\mathbb{F}_q$ Chevalley's theorem states that if $f(x_i)\in k[x_1,...,x_n]$ is such that $f(0,...,0)=0$ and $deg(f)<n$, then there is a non-trivial $a_i\in k^n$ such that $f(a_i)=0$. Is ...
3
votes
0answers
83 views

zeros of a simple polynomial

For $x, y \in GF[2^n]$, consider the two-parameter polynomial $P(x,y) = x \cdot y + f(x) + g(y)$, where $f$ and $g$ are arbitrary polynomials on $GF[2^n]$. Can we say anything about the number of ...
1
vote
0answers
79 views

Approximating polynomials over finite fields

Consider a binary finite field $F = GF[2^{n}]$ with addition and multiplication denoted by $\oplus$ and $*$, respectively. Let me represent the elements of $F$ by $n$-bit strings, which means that ...
1
vote
2answers
114 views

Polynomial multiplication modulo polynomial

Suppose we are working on finite field $F_{16}$ and have pritimive polynomial $z^4+z+1$. I stuck at how to compute polynomial modulo. For example, we have $z^5+z+1$ mod $z^4+z+1$. I use the usual ...
0
votes
1answer
18 views

Can the set L, of all even polynomials be a subspace of F[X]?

So I have the question Let F be a field and let L be the set of all polynomials f(x) element of F[X] satisfying the condition that deg(f) is even. Is L a subspace of F[X]? I would say that L is not a ...
0
votes
1answer
23 views

Showing $f\in\mathbb{F}_{p^d}[X]:f'=0\Rightarrow\exists g\in\mathbb{F}_{p^d}[X]:f=g^p$

Let $\mathbb{F}_{p^d}$ denote the final field with $p^d$ elements and $\mathbb{F}_{p^d}[X]$ denote the polynomial ring in $X$ over $\mathbb{F}_{p^d}$. How can we show ...
2
votes
1answer
67 views

Primitive polynomials in LFSRs

I need help proving the following theorem. I found it many books but on every single one it says that they omit the proof because it is in every good textbook. THM Let $c(x)$ be a connection ...
0
votes
3answers
96 views

Quotient rings of polynomial rings

I have come across a quite difficult question while I am studying for a test: Let $F=\Bbb Z[x]/(7,x^2-3)$. Let $u$ denote the image of $x$ under the canonical epimorphism from $\Bbb Z[x]$ to ...
0
votes
1answer
41 views

Discrete Logarithm Problem in $GF(p^m)$

I have question regarding DLP in $GF(p^m)$ I know the algorithms for solving the DLP in $GF(p)$ like Baby Step-Giant Step, Pohlig-Hellman etc... But what if we move into the $GF(p^m)$ and are ...
3
votes
3answers
313 views

How and in what context are polynomials considered equal? [duplicate]

There's two notions of equivalent polynomials floating around, one saying that $f = g$ iff they're equivalent as maps, and the other saying $f = g$ iff they're equal on each coefficient when written ...
4
votes
0answers
67 views

Isomorphism between finite fields adjoining a root

Let $p(x)=x^3+x^2+1$ and $q(x)=x^3+x+1$ be polynomials over the field $\mathbb{Z}_2$. Let $\alpha$ be a root of $p(x)$ and $\beta$ be a root of $q(x)$. Now let $K=\mathbb{Z}_2(\alpha)$ and ...
8
votes
1answer
58 views

Existence of root of a polynomial over $\mathbb F_p$.

I came accross the following question and I can't find an easy proof of this fact : Let $p\geq 17$ be a prime number such that $p\equiv 1 \pmod 4$. Show that for any $z\in \mathbb ...
3
votes
0answers
26 views

Determinant of a generalization of Moore matrices

The Moore matrix over $\mathbb{F}_q$ is the $n\times n$ matrix whose i'th row is: $a_i,a_i^q,a_i^{q^2},\dots,a_i^{q^{n-1}}$. The determinant of this matrix is the product of all linear combinations ...
1
vote
1answer
36 views

How to give irreducible factorization in $\mathbb{Z}_5$?

I have this polynomial: $$f=x^5+2x^3+4x^2+x+4$$ How can i find the irreducible factorization(in $\mathbb{Z}_5$)?I can find the roots easily but thats not enough.
1
vote
1answer
26 views

Every irreducible polynomial in $\mathbb{F}_p[x]$ is separable?

How can I show this? I tried proving the contrapositive statement but didn't get anywhere. I think I may have to do something involving automorphisms of the splitting field of such a polynomial, and ...
0
votes
1answer
61 views

Do there exist polynomials not computable in polynomial time?

Motivation: Computing a problem in $k$ memory slots Do there exist polynomials in $R = \Bbb{Z}_p[z_1, \dots, z_k]$ that can't be computed in time polynomial in $k,p$? Thanks... Good luck! Edit. I ...
0
votes
1answer
26 views

Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...
2
votes
0answers
39 views

Roots of polynomial in $F_3[x]$

Let $\alpha$ be a root of $x^2 + x + 2 = 0$ in $F_3[x]$. I am asked to show that $x^3 + x + 1$ has roots $\alpha$, $\alpha^2$ and $\alpha^4$. I started by observing that $\alpha^2 + \alpha + 2 = 0 ...
0
votes
2answers
40 views

Addition in $\operatorname{GF}(2^4)$

How can I compute $A(x)+B(x) \mod P(x)$ in $\operatorname{GF}(2^4)$ using the irreducible polynomial $P(x)=x^4+x+1$. What is the influence of the choice of the reduction polynomial on the computation? ...
1
vote
1answer
25 views

multiplication in finite fields irreducible polynomial

I just started doing some reading about multiplication in finite fields and i keep stumbling over one point: in the field G(2^8) how does x^8 + x^4 + x^3 + x + 1 = 0 imply that x^8 = x^4 + x^3 + x + ...
5
votes
1answer
55 views

Construction of a polynomial

Let $ m \in \mathbb{N}$ be fixed and $q=p^n$ (a variable prime power) for $n \in \mathbb{N}$ and $p$ prime. We define $$c_m=|\left\lbrace f \in \mathbb{F}_q[X]; f \ \text{irreducible, monic, ...
2
votes
1answer
33 views

Number of monic polynomials = $q^n$?

In the situation $q=p^k$ with $p$ prime and $k \in \mathbb{N}$ I have the following question: Why is the number of monic polynomials of degree $n$ in $\mathbb{F}_q[X]$ $$q^n \ ?$$
5
votes
1answer
152 views

Calculating a strange algebraic limes

I have a problem with calculating a strange limes: Let $ m \in \mathbb{N}$ be fixed and $q=p^n$ (a variabel prime power) for $n \in \mathbb{N}$ and $p$ prime. We define $$c_m=|\left\lbrace f \in ...
2
votes
1answer
103 views

Algebraic problem - irreducible polynomials

Let $p$ be a prime number and $q=p^n$ with $n \in \mathbb{N}$. We define the polynomial$$ F_m:=\prod \left\lbrace f \in \mathbb{F}_q[X]; f \ \text{irreducible, nomic}, \text{deg}(f)=m \right\rbrace $$ ...
0
votes
1answer
79 views

Order of element of multiplicative group of finite field mod polynomial

If $K$ is a finite field of size $q$ and $f$ is a degree $n$ polynomial in $K[x]$, then we can form the quotient field by modding out this polynomial. Elements of this quotient field are of the form ...
5
votes
2answers
173 views

Understanding Intel's white paper algorithm for multiplication in $\text{GF}(2^n)$?

I'm reading this Intel white paper on carry-less multiplication. For now, suppose I want to do multiplication in $\text{GF}(2^4)$. We are using the "usual" bitstring representation of polynomials ...
2
votes
1answer
69 views

Relation between divisibility of polynomials in different rings, $h | f$ in $\mathbb{Z}[x], \mathbb{Z}/p^k\mathbb{Z}[x]$ and $\mathbb{F}_p[x]$

Let $p$ be a prime, $k$ a positive integer. Let $f,h \in \mathbb{Z}[x]$ be polynomials such that $h | f \mod p^k$ in $ (\mathbb{Z}/p^k\mathbb{Z})[x]$ $h \mod p$ is irreducible in $\mathbb{F}_p$ ...
1
vote
2answers
46 views

Finding a gcd in the form of a monic polynomial

The question is to find the greatest common divisor (in the form of monic polynomial) in $\Bbb F_5[X]$ of $f=x^2-x+4$ and $g=x^3+2x^2+3x+2$ I used the Euclidian Algorithm for polynomials and found ...
0
votes
0answers
77 views

Multivariable irreducible polynomials over finite fields

It is not difficult to prove the following result, and it seems that it should be already proved. I would appreciate it if someone offer me some reference to it. For any $f(x_1,\dots, x_n)=\sum ...
0
votes
1answer
51 views

Solutions of $x^d=1$ in a finite field

Let's consider the polynomial $x^d-1$. Theory tells us that it can have at most $d$ roots in (any extension of) a given field. Here's my problem: let $A$ be the vector space spanned by ...
1
vote
1answer
35 views

When is the Frobenius endomorphims an isomorphism?

I did this problem, but now I'm left with more questions! Suppose $f(x)$ is a monic irreducible polynomial of degree $3$ over $GF(2)$. Prove that if $a$ is a root of $f$ in an extension of $GF(2)$, ...
3
votes
0answers
50 views

How to prove how many ireducible polynomials are in a polynomial ring over a finite field.

Can someone help me out with some problem concerning the cardinaliy of ireducible polynomials in $(\mathbb Z/p\mathbb Z)[x]$? Here first why the problem appeared, I want to prove that ...
3
votes
3answers
109 views

Homogenous polynomial over finite field having only trivial zero

Is there a way to construct homogenous polynomials of small degree over a certain finite field having only trivial zero? For instance, the polynomial $f (a, b, c) = a^3 + b^3 + c^3 - 3abc - 3a^2b - ...
0
votes
0answers
14 views

Univariate and Linear Representation Lemma

I'm trying to understand the proof of the lemma: Let $\mathbb{F}$ be a finite field with $q$ elements and $\mathbb{K}$ an extension field of degree $n$ of $\mathbb{F}$. Let $A$ be a linear mapping ...
4
votes
2answers
63 views

Prove two bases are dual in a finite field.

Let K be a finite field, $F=K(\alpha)$ a finite simple extension of degree $n$, and $ f \in K[x]$ the minimal polynomial of $\alpha$ over $K$. Let $\frac{f\left( x \right)}{x-\alpha }={{\beta ...
1
vote
1answer
52 views

Prove a polynomial in Fq is a permutation polynomial of Fqn with a necessary and sufficient condition

P.S This is the best Math Expression I can edit. I am real shameful, where can I find the introduction of typing in this webset? thank you Exercise7.13 Let\[f\left( x \right) = \sum\limits_{i = ...
2
votes
2answers
38 views

Irreducible quadratic in $\mathbb{Z}_p$

I want to show that for every prime $p$, there exists an irreducible quadratic in $\mathbb{Z}_p[x]$. So I'm looking for some $x^2+ax+b$ that's irreducible. But what $a,b$ choose we choose?
1
vote
2answers
43 views

Prove identity in quotient group

I'm studying for my algebra exam, and came across the following problem, which I'm not sure how to solve Let $f = X^2 - 1 \in \mathbb{F}_3[X]$ and $\alpha = X + \langle f \rangle \in ...
0
votes
2answers
51 views

Quotient group element is a unit

I'm studying up for my algebra exam, and I'm not exactly sure how to solve a problem like the following Let $f = X^2 + 1 \in \mathbb{F}_5[X]$, $R = \mathbb{F}_5[X]/\langle f \rangle$ and $\alpha = ...
2
votes
1answer
55 views

Prove that $K\times K[X]/(X^7-1)\cong K\times \dots \times K$

Given that $K$ is a finite field of order $q\equiv1\text{ mod } 7$, I have to prove that $$K\times K[X]/(X^7-1)\cong K\times \dots \times K\ (8 \text{ times } K).$$ It's the same to prove that ...
18
votes
1answer
170 views

How many pairs of nilpotent, commuting matrices are there in $M_n(\mathbb{F}_q)$?

As a follow-up to this question, I've been doing some work counting pairs of commuting, nilpotent, $n\times n$ matrices over $\mathbb{F}_q$. So far, I believe that for $n=2$, there are $q^3+q^2-q$ ...
0
votes
1answer
60 views

Show a polynomial is irreducible

I'm working through the proof of Hasse's theorem and I think I need to show that the polynomial $x^4 - 2ax^2 - 8bx + a^2$ is irreducible over $\mathbb{F}_p$, where $a$, $b$ are integers and $p$ is ...
3
votes
1answer
68 views

Units in finite polynomial rings

Are the units of the quotient ring $\mathbb{F}_2[x]/\langle x^k+1 \rangle$ known in general, where $\mathbb{F}_2$ is the finite field with two elements? I'm specifically interested in the case where ...
2
votes
0answers
23 views

Units in finite polynomial rings [duplicate]

Are the units of the quotient ring $\mathbb{F}_2[x]/\langle x^k+1 \rangle$ known in general, where $\mathbb{F}_2$ is the finite field with two elements? I'm specifically interested in the case where ...
1
vote
1answer
51 views

Is this a generator of a cyclic group?

Let $F=\mathbb Z/(p)$, where $p$ a prime number, $f(x)$ a monic irreducible polynomial in $K=F[x]$ of degree $n$, $K=F[x]/(f(x))$, and $E$ the multiplicative group of nonzero elements of $K$. Then ...
3
votes
1answer
91 views

polynomials factorization over rings and finite fields

Any nonzero polynomial over a subring $R$ of $\mathbb{C}$ is a product of irreducible polynomials over $R$. And for any subfield $K$ of $\mathbb{C}$, factorization of polynomials over $K$ into ...
2
votes
0answers
62 views

How to prove that if $f(x)$ is primitive over $GF(2^m)$ then its reciprocal is primitive too? [closed]

How to prove that if $f(x)$ is primitive over $\mathbb{GF}(2^m)$ then its reciprocal $f^*(x)$ is primitive too?
0
votes
1answer
104 views

Finding the monic generator of ideals of polynomials

Given $F$ a field, and $F^F$, the set of functions from $F$ to $F$, and define an evaluation map $e : F[x]\to F^F$ which sends a polynomial to the function which is computed using the polynomial as ...
0
votes
1answer
60 views

Help understanding fields and polynomials

Construct a field of 9 elements – construct the addition and multiplication tables. Begin with polynomials having coefficients $0$, $1$, and $2$ (integers modulo $3$) and use the modulus $X^2+X+2$ I ...