All Questions
Tagged with polynomials finite-fields
797
questions
4
votes
1
answer
2k
views
Question about LFSR
I am reading a paper and say this
"The idea is to load $f(X)$ into LFSR to multiply by $X$ mod $g(X)$(primitive polynomial deg $g=n$). We next compute a polynomial h(X) whose coefficients are given ...
- 1,254
2
votes
3
answers
988
views
Polynomials, finite fields and cardinality/dimension considerations
Can someone please give me a hint how to prove that the quotient ring $\mathbb{F}_p[x]/{\langle f\rangle}$, where $f$ is a irreducible polynomial of degree $k$ and $p$ is a prime (and $\langle f\...
user19053
54
votes
3
answers
18k
views
Irreducible polynomial which is reducible 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 $x^4+1=(x+1)^4\bmod 2$. Also $\bmod 3$ we have that $0,1,2$ are not ...
- 11.1k
17
votes
2
answers
22k
views
Reed Solomon Polynomial Generator
I am developing a sample program to generate a 2D Barcode, using Reed-Solomon error correction codes. By going through this article, I am developing the program. But I couldn't understand how he ...
- 389
1
vote
1
answer
316
views
Low degree approximation of the polynomial extension of the logical-or function
Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$).
Consider ...
user15676
2
votes
1
answer
357
views
Extending the logical-or function to a low degree polynomial over a finite field
Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$).
Is there ...
user15676
1
vote
1
answer
1k
views
Low degree extension
Let $v$ be a binary vector of dimension $n$. Assume that $n$ is a perfect square, then $v$ can be thought of as a function $f:[\sqrt n]\times[\sqrt n]\to \{0,1\}$, where $[\sqrt n]=\{1,\ldots,\sqrt n\}...
user15676
4
votes
2
answers
4k
views
Irreducible polynomial of $\mathrm{GF}(2^{16})$
I'm implementing some code for the Galois field $\mathrm{GF}(2^{16})$. Which irreducible polynomial do you recommend that I use?
- 143
2
votes
1
answer
217
views
Variation over univariate Schwartz–Zippel lemma
Let $n\in\mathbb{N}$ and let $q\in[n,2n]$ be a prime number.
In addition, let $s,s':\mathbb{F}_q\to\mathbb{F}_q$ be polynomials of degree $\sqrt{n}$ such that $s\neq s'$.
From the Schwartz–...
user15676
2
votes
1
answer
225
views
Extending a boolean function to a finite field
Let $f:\{1,2,\ldots,n\}\to\{-1,1\}$ be a boolean function. Can I extend $f$ to a polynomial of degree at most $n$ over $\mathbb{F}_q$, where $q\in[n,2n]$ is a prime number. i.e.,
is there a ...
user15676
5
votes
3
answers
347
views
Roots of $x^2 + 2x + 2$
I'm trying to show that there are infinitely many values of $p$ such that $x^2 + 2x + 2$ has no roots over $\mathbb{F}_p$. Is this easily solvable? (I kind of came up with it myself so I don't know.)...
- 4,075
2
votes
1
answer
108
views
Distinguishing vector distributions induced by polynomials
I am given two sequences of multivariate polynomials $\overline{p}=(p_1,p_2,\dots,p_k)$ and $\overline{q}=(q_1,q_2,\dots,q_k)$, all of them on the variables $x_1,\dots,x_n$ over some finite field $\...
- 19.4k
8
votes
2
answers
3k
views
Factoring $X^{16}+X$ over $\mathbb{F}_2$
I just asked wolframalpha to factor $X^{16}+X$ over $\mathbb{F}_2$. The normal factorization is
$$
X(X+1)(X^2-X+1)(X^4-X^3+X^2-X+1)(X^8+X^7-X^5-X^4-X^3+X+1)
$$
and over $GF(2)$ it is
$$
X(X+1)(X^2+...
- 83
10
votes
3
answers
2k
views
Intuition regarding Chevalley-Warning Theorem
Three versions of the theorem are stated on pages 1-2 in these notes by Pete L. Clark:
http://alpha.math.uga.edu/~pete/4400ChevalleyWarning.pdf
Could anyone offer some intuitive way to think about ...
- 6,584
68
votes
2
answers
33k
views
Number of monic irreducible polynomials of prime degree $p$ over finite fields
Suppose $F$ is a field s.t $\left|F\right|=q$. Take $p$ to be some prime. How many monic irreducible polynomials of degree $p$ do exist over $F$?
Thanks!
- 4,215