0
votes
1answer
51 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
22 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
36 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
32 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
13 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 + ...
10
votes
1answer
50 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, ...
6
votes
1answer
31 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 \ ?$$
10
votes
1answer
143 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 ...
5
votes
1answer
78 views

Difficult 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
49 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
145 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
60 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
33 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
64 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
48 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
32 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
47 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
91 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
54 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
44 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
36 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
42 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
44 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
51 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 ...
6
votes
0answers
48 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
51 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
60 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
22 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
45 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
67 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
51 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
82 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
57 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 ...
0
votes
1answer
59 views

Solving an equation in a field.

I need to know the way to solve equations like this: $$(x^2+1)f(x) = 1 \pmod{x^3+1}$$ over a field $F_{3}[x]$. Thanks in advance for any help.
4
votes
3answers
121 views

$x^5-1$ completely splits in $\mathbb F_{16}$

I need to prove that $x^5-1$ completely splits in $\mathbb F_{16}$. This means it has exactly $5$ unique roots in $\mathbb F_{16}$. I have only found the following way: find an irreducible polynomial ...
1
vote
2answers
60 views

Inverse of polynomial over $\mathbb F_3$ finite field, quotient space

A question about quotient spaces, something I do not fully understand yet, and can use some help. $A = \mathbb F_3[x]$, $P = x^3-x+2\in A$ 1) Show that $P$ is irreducible (I did it, it has no roots ...
1
vote
1answer
47 views

Factoring a polynomial over finite field $\,F_3$ that has a root

A question I am struggling with. We are asked to factor $\,f(x)=x^2+x+1$ over the field $F_3 =\{0,1,2\}$ So, I checked for a root, and I saw that $f(1) = 1^2+1+1 =0$ (because $3=0$ in $F_3$) that ...
1
vote
1answer
49 views

Matrix polynomial factorization

This is about exercise 1207 from the book "Problems and Solutions in Mathematics", 2nd edition, by Ta-Tsien. Let $p$ be a prime and let $V$ be an $n$-dimensional vector space over the finite field ...
0
votes
1answer
67 views

Example of Linear System of Polynomials over finite field

I'm trying to find any system of polynomial over finite field (solvable in $K[x]_{m(x)}$) with characteristic two. I want please any example of $a_{ij}$ and $b_k$ ...
2
votes
1answer
373 views

How many irreducible factors does $x^n-1$ have over finite field?

The polynomial $x^n-1$ is needed to be factorized into irreducibles over finite field $\mathrm{F}_q$. How many are them? I guess the question is about of number of cyclotomic cosets. Let $p$ be the ...
4
votes
2answers
295 views

When is a cyclotomic polynomial over a finite field a minimal polynomial?

When is the cyclotomic polynomial $f(x)$ over a finite field $\mathrm{F}_q$ also the minimal polynomial of some element $\alpha \in \mathrm{F}_q$?
1
vote
0answers
97 views

Determine generator over $GF(2^4)$

Working in $GF(2^4$) Field generated modulus $x^4+x^3+x^2+x+1$. Find a generator of $F$. What I have figured out so far - $16$ polynomials to consider. If $b$ is generator then start with $b = x + ...
1
vote
1answer
60 views

An algebraically closed field with characteristic $p>0$

I want to know about an algebraically closed field that is not of characteristic $0$. I really don't know about infinite fields with characteristic $p$ so I will appreciate your comments.
0
votes
4answers
70 views

Galois field and polynomials?

Show there are only two polynomials of degree 3 over $\mathbb{F}_2$ such that it is irreducible and all other degree 3 polynomials can be reduced. So $x^2 = x$ and $x = -x$ I cant think of anything ...
6
votes
3answers
48 views

Find the minimal $n$ such that there exists $[n,n-5]$ cyclic binary code with generator polynomial $g(x)=1+x^4+x^5$

Find the minimal $n$ for there exists $[n,n-5]$ cyclic binary code with generator polynomial $g(x)=1+x^4+x^5$. I couldn't figure out the answer. The only way I could think of is find out all the ...
0
votes
1answer
271 views

finding the inverse of an element in finite field

how can I able to solve the inverse of $x^6+x^4+x+1$ in the field $\mathbb{Z}_2[x]/(x^8+x^4+x^3+x+1)$ can someone help me please to solve the problem. actually I want to know the process of ...
1
vote
1answer
60 views

Finding a root and reduce a function over a finite field

Let $F= \Bbb Z_2[x]/ \langle f \rangle$ with $f=x^3+x+1 \in \Bbb Z_2[x]$. Now consider f as an element of $F[x]$ and a) show that there exists $\alpha \in F$ with $f(a)=0$ b) find $g \in F[x]$ with ...
1
vote
1answer
71 views

how to find generator in $ F_2[x]/(f(x))$?

a finite field $F_{2^n}\cong F_2[x]/(f(x))$($f(x)$is irreducible polynomial with the degree of $n$), so the elements in $F_{2^n}$ can be seen a polynomial modular $f(x)$, that is ...
1
vote
2answers
106 views

how many elements are there in this field

$\mathbb Z_2[x]/\langle x^3+x^2+1\rangle $, I understand it is a field as $\langle x^3+x^2+1\rangle $ ideal is maximal ideal as the polynomial is irreducible over $Z_2$. but I want to know how many ...