All Questions
23
questions
1
vote
1
answer
43
views
Quadratic residues of low degree polynomials in $\mathbb{F}_p$
Let $(\frac{a}{p})$ denote the Legendre symbol. Let $P$ be a polynomial over $\mathbb{F}_p$ of degree $d$. I would like to upper bound
$$\Big\lvert\,\mathbb{E}_a \Big(\frac{P(a)}{p}\Big)\Big\rvert$$
...
- 175
2
votes
1
answer
311
views
Modulo calculation on a polynomial, in NASA tutorial on Reed-Solomon codes
I am reading Geisel's tutorial$^{\color{red}{\star}}$ on Reed-Solomon codes, in which a Galois Field is developed. The elements of the field are generated as consecutive powers of $X$, modulo an ...
- 143
5
votes
1
answer
224
views
Does there exist a polynomial indicator function over $\mathbb{Z}_p[x_1,\dots,x_{p^3}]$ of degree at most $O(p^2)$?
The Problem
Let $p$ be a prime. Does there exist a $p^3$-variable polynomial $P$ over $\mathbb{Z}_p[x_1,\dots,x_{p^3}]$ such that
$P(\boldsymbol{0}) \equiv 0 \ (p)$
$P(\boldsymbol{x}) \equiv 1 \ (p)$ ...
- 2,740
0
votes
2
answers
269
views
Incorrect result for extended euclidean algorithm for polynomials
I am trying to follow an algorithm but I cannot get the correct result. I don't know if the calculations are wrong (would be surprised, since I checked them carefully with an online SageMath engine), ...
- 239
1
vote
0
answers
48
views
Prove $x^4 + 1$ factors in $F_p[x]$ for all primes $p$ (Question from Rotman Abstract Algebra)
Rotman wants me to prove the above in a very specific way:
Step 1: Prove that if p is a prime with $p\equiv 3$ mod 4, then either $a^2 \equiv 2$ mod p is solvable or $a^2 \equiv -2$ mod p is solvable. ...
- 23
1
vote
2
answers
54
views
Find inverse element of $1+2\alpha$ in $\mathbb{F}_9$
Let $$\mathbb{F}_9 = \frac{\mathbb{F}_3[x]}{(x^2+1)}$$ and consider $\alpha = \bar{x}$. Compute $(1+2 \alpha)^{-1}$
I think I should use the extended Euclidean algorithm: so I divide $x^2 +1 $ by $(...
- 185
1
vote
1
answer
52
views
Why is $x^4+x^2+1$ over $𝔽_2$ a reducible polynomial? What do I misunderstand?
I don't quite understand when a polynomial is irreducible and when it's not.
Take $x^2 +1$ over $𝔽_3$.
As far as I know, I have to do the following:
0 1 2 using $x \in 𝔽_3$
1 2 2 using $p(x)$
I ...
- 931
1
vote
1
answer
94
views
Find prime fields over which a polynomial has roots.
Suppose we have a polynomial
$$h(x) = a_n x^n + \dots + a_1 x + 1$$
Given the values $a_1,\ldots,a_n$, how to determine whether there exists such prime $p$ that $h(x)$ has roots over the field $\...
- 3,212
1
vote
1
answer
49
views
Number of roots of $f(x,y)\equiv0\bmod p$?
Given a prime $p$ and degree $d$ is it possible to define polynomials $f(x,y)\in\mathbb Z[x,y]$ with total degree $d$ and number of roots at most $t$ where $t$ is any integer in $[0,B]$ for some upper ...
- 6,245
0
votes
0
answers
55
views
Modular Polynomial Arithmetic in Schoof's Algorithm
I've been trying to implement Schoof's Algorithm, and I understand it except for one part.
Near the bottom of page 7 of this paper is where my issue is: http://www-users.math.umn.edu/~musiker/schoof....
- 1
1
vote
3
answers
568
views
Help on solutions of the congruence $f(x)=x^3+4x+8 \equiv 0 \pmod {15}$
I'm doing a little exercise, solve the congruence $f(x)=x^3+4x+8 \equiv 0 \pmod {15}$.
I know that $15=3 \times 5$ and they are relatively prime, so I can split the congruence into:
a) $f(x) \equiv ...
- 500
1
vote
1
answer
417
views
How to find the root of the polynomial $x^2+x+1$ over $\mathbb{Z}_2$ in this field?
I am having some troubles understanding the proof for a statement. The question is:
Suppose R is the polynomial ring $\mathbb{Z}_2[x]$. Let $(x^4+x+1)$, I, be the principal ideal of this ring. ...
- 393
4
votes
3
answers
588
views
Solving roots of a polynomial on $\mathbb{Z}_p$
This is probably a simple question. and I would like to work out an example.
How do we solve $x^2 + x + [1] = 0$ over the field $\mathbb{Z}_7$?
I tried a simple case, for example: $[4] x - [3] = 0$, ...
- 1,143
0
votes
0
answers
69
views
What is an efficient way of evaluating a polynomial when its roots are known?
Hypothesis: All calculations and polynomials are defined over a finite field of prime order.
Assume we know all roots $r_i$ of a polynomial: $P(x)=(x-r_1)(x-r_2)...(x-r_n)$ and a set of x-...
- 21
6
votes
1
answer
590
views
Does every polynomial over a finite field have a square root modulo an irreducible polynomial?
Given a polynomial $p \in \operatorname{GF}(2^m)[x]$ and an irreducible polynomial $g \in GF(2^m)[x]$, is there a $d \in \operatorname{GF}(2^m)[x]$ such that $d^2(x) = p \pmod{g(x)}$?
In other words, ...
- 75