1
vote
1answer
34 views

polynomial over finite field, roots forming additive subgroup

Let $q=2^h$ and $t=2^r$ for some $h\ge r$ and denote by $\mathbb{F}_q$ the finite field of order $q$. (since the previous, simple version was wrong, I'm posting here a new version) Let $f$ be a ...
4
votes
3answers
109 views

Polynomials over $\mathbb{F}_2$ with certain values in $\mathbb{F}_4$

Let $\mathbb{F}_4=\{0,1,u,u^2\}$ be the field with $4$ elements. Is there a polynomial $p \in \mathbb{F}_2[x,y]$ with the following property? (1) For $r,s \in \mathbb{F}_4$, we have $p(r,s)=u ...
1
vote
2answers
14 views

Implications of zero elemntary symmetric polynomials over a finite field

For a prime $q$ and an integer $n<q$, consider working over the finite field of $q^n$ elements. Denote by $s_n^k$ the $k$-th elementary symmetric polynomial in $n$ variables. That is, ...
8
votes
0answers
115 views

On the maximum number of polynomials in a certain subspace

I've already asked this question on mathoverflow, but no one answered. So I put this problem also here. Sorry for that. Let $\mathbb F_q$ be a finite field and let $e, k$ be positive integers with ...
3
votes
1answer
45 views

Square-free factorization of polynomials over finite fields

For any $f\in\mathbb{F}_q[X]$, I want to derive an algorithm which computes a factorization $$f=\prod_{i=1}^kf_i^i\tag{1}$$ with square-free polynomials $f_i$. My Ideas: If $f'=0$, we're done ...
2
votes
0answers
54 views

How to prove that all primitive polynomials are irreducible

Let $F$ be a finite field, and $F[X]$ set of all polynomials in $F$, how to prove that: why all primitive polynomials $\;$ $f \in F[X]$ $\;$ must be an irreducible. Note: Polynomial primitive is an ...
1
vote
1answer
49 views

Proving degree $n$ have at last $n$ roots in $F_q[X]$

How to prove that in $F_{q}[X]$ of degree $n$, have $n$ roots?
4
votes
2answers
55 views

Show that if $\mathrm{Tr}(y)=0$ then there exists a $x$ such that $x^p-x=y$.

We have the Trace map defined by: $$ \mathrm{Tr}\colon \mathbb{F}_q\rightarrow\mathbb{F}_q\colon x\mapsto x+x^p+x^{p^2}+\cdots+x^{p^{n-1}}, $$ where $q=p^n$. Now I have to prove that if ...
1
vote
0answers
63 views

GCD of high order polynomials(modulo large prime)

I want to solve the following question: Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to ...
1
vote
1answer
40 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
31 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
92 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
97 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
136 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
27 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
86 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 ...
-1
votes
3answers
110 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
44 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
326 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
73 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
61 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
29 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
41 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
63 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
41 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
43 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
31 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
34 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
154 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 ...
3
votes
1answer
112 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
102 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
195 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 ...
1
vote
0answers
68 views

Remainder and quotient of polynomial division in $\mathbb Z_7[x]$

Find the quotient and remainder of: $$ \frac {x^4 + [3]x^3 + [5]x} {x^2 + [2]} ; \mathbb Z_7[x]$$ Would the answer be the same if it wasn't in $\mathbb Z_7[x]$. Namely: Quotient: $x^2 +[3]x - ...
2
votes
1answer
72 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
52 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
79 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
52 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
40 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
52 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
122 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
16 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
64 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
54 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
39 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
56 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 = ...