All Questions
Tagged with polynomials finite-fields
797
questions
0
votes
0
answers
70
views
Show that the polynomial $x^4+x+1$ is primitive over $\mathbb{F}_2$ [duplicate]
I've been struggling for hours and so far have shown the polynomial is irreducible, $p(0) \neq 0$, and monic.
All there is left to prove is that the polynomial is of order $15$.
Then I can use a ...
0
votes
0
answers
30
views
If f(x) is a permutation polynomial defined over the finite field GF(q), then so is g(x) = a f(x + b) + c for all a ≠ 0, b and c in GF(q)
"If f(x) is a permutation polynomial defined over the finite field GF(q), then so is g(x) = a f(x + b) + c for all a ≠ 0, b and c in GF(q)"
Hey guys,
I've been seeing this statement as an ...
1
vote
0
answers
50
views
The invertible polynomial are only the one of degree 1
( with $\mathbb{Z}_n$ I mean $\frac{ \mathbb{Z} }{ n\mathbb{Z} }$ )
Theorem :
Let $\psi,\phi \in \mathbb{K}[x]$ be such that
$$\psi(\phi(x)) = x = \phi(\psi(x)) \; \forall x \in \mathbb{K}$$
Then ...
1
vote
1
answer
89
views
prove $f(x)$ and $g(x)$ have the same number of roots in $\mathbb{F}_{p}$
Suppose $p$ is a prime,and $f(x)=\sum\limits_{k=0}^{p-1}k!x^{k}$, $g(x)=\sum\limits_{k=0}^{p-1}\frac{1}{k!}x^{k}$,prove $f,g$ have the same number of roots in $\mathbb{F}_{p}$
I tried to consider the ...
0
votes
0
answers
86
views
How to calculate the exponentiation of a polynomial with modulo and a residue ring
For example,
How to efficiently calculate how much does $(x^3+1)^{40}$ equal to if it is in the field of $\mathbb{Z}/3\mathbb{Z}[x]/(x^4+x-1)$?
0
votes
0
answers
92
views
Find the inverse of x^7 + x^6 + x^3 + x + 1 in Rijndael's finite field
I managed to calculate the GCD($x^7 + x^6 + x^3 + x + 1$, $x^8 + x^4 + x^3 + x + 1$) and I did some steps of the xgcd but I don't know exactly how to 'group' the polynomials.
Field: $F2^8 / m(x)$
$m(x)...
2
votes
2
answers
183
views
Show that $2$ is a square in $\mathbb{F}_p$, using an element $\alpha$ obtained from an extension field as a root.
This problem asks me to show that $2$ is a square in $\mathbb{F}_p$ iff $p \equiv \pm 1$ mod $8$ through a number of steps, the first step is the following problem:
Let $p$ be an odd prime and let $\...
1
vote
1
answer
82
views
A divisibility problem in GF(3m+1)
The following is a problem about polynomials over finite fields I am trying to solve.
The problem:
Let $p$ be a prime of the form $p=3m+1.$
I want to prove that $p(x)=(x+1)^{2m+1}+(x+1)^{m+1}+x+1$ is ...
4
votes
2
answers
228
views
Help with a finite field exercise. How to find the minimal polynomial of a given root in a given field.
I need a help with this exercise.
(i) Find a primitive root $\beta$ of $\mathbb{F}_2[x]/(x^4+x^3+x^2+x+1)$.
(ii) Find the minimal polynomial $q(x)$ in $\mathbb{F}_2[x]$ of $\beta$.
(iii) Show that $\...
0
votes
1
answer
36
views
How to check an element of $\mathbb{F}_p$ belongs (or not) to a sequence defined by a rational function?
Let $\mathbb{F}_p$ be a prime field (p being a large prime) and a sequence $(u_n)_{n\geq0}$ defined by $$u_{n+1}=\frac{N(u_n)}{D(u_n)}$$ with $u_0 \in \mathbb{F}_p$, N and D being two polynomials.
...
6
votes
2
answers
173
views
When does linear polynomials commute over finte field?
I have posted a question yesterday in When does degree 1 polynomial commute?. Which describes about any linear polynomial $ax+b$ commute(in the sense of compostion) with other polynomial of degree $...
2
votes
2
answers
850
views
Generating irreducible polynomials for binary numbers
From a paper, there is a discussion about generating irreducible polynomials for a certain degree as can be seen below.
The reference is wolfram, but it is not clear how those polynomials are ...
1
vote
1
answer
41
views
Reduced degrees of polynomials over a finite field
Theorems for polynomials over infinite fields are often modified for a finite field $\mathbb{F}_q$ by reducing the exponents of each monomial in the polynomial so that they are of the form $X^k$ where ...
4
votes
1
answer
78
views
When a square of a polynomial root is in $\mathbb{F}_p$
Let $p > 5$ be prime. If $1 + 5x^2 + 5x^4$ has a root in $w \in \mathbb{F}_{p^2}$, then does $-1 + x + x^2$ have a root in $\mathbb{F}_p$? If $w$ is a root of the former, then $5w^2 + 2$ is a root ...
0
votes
0
answers
37
views
Polynomial of degree 3 with coefficients over $\mathbb{F}_3$ has always a root in GF(27) [duplicate]
Prove or give a counterexample:
Every polynomial of degree 3 having coefficients over $\mathbb{F}_3$ has always a root in $\mathbb{F}_{27}$.
I noticed that $\mathbb{F}_{27} = \mathbb{F}_{3}[x]/(f)$, ...