All Questions
7 questions
33
votes
3
answers
6k
views
Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...
- 19.6k
9
votes
1
answer
792
views
Reconstructing a polynomial from resultants
I am trying to compute a monic polynomial $f(x)$ with integer coefficients and known degree $d$. I am given $n$ pairwise coprime polynomials $g_1(x),\ldots,g_n(x)$, also with integer coefficients, ...
7
votes
1
answer
1k
views
Expressing primes $p\equiv 1 \pmod 3$ in the form $p = x^2 + xy + y^2$
Fermat famously showed that the only primes $p$ of the form $x^2 + y^2$ are the primes such that $p \equiv 1 \mod{4}$. Furthermore, we now know “effective” versions of Fermat's theorem, i.e. given a ...
- 1,703
3
votes
1
answer
195
views
Solutions to nonhomogeneous quadratic equation mod $N$
Is there any way to find non-trivial solutions to the equation $x^2 + y^2 - x \equiv 0 \mod{N}$? There are clearly several trivial solutions, for example $(x, y) = (0, 0), (1, 0), (2^{-1}, 2^{-1}), (2^...
- 1,703
3
votes
0
answers
110
views
Efficient computation of "higher order" Jacobi symbols
Let $N> 1$, and suppose $a \in (\mathbb{Z}/N\mathbb{Z})^{\times}$. There are efficient algorithms to compute the Jacobi symbol $\left(\frac{a}{N}\right)$ using quadratic reciprocity. Fix $k \geq 1$....
- 1,703
1
vote
0
answers
642
views
Factoring $N$ given a solution to $x^2 + y^2 \equiv 0 \pmod{N}$
Let $N$ be a composite integer, and suppose we are given a randomly generated solution $(x, y)$ of the equation $x^2 + y^2 \equiv 0 \pmod{N}$. By randomly generated, I mean that $(x, y)$ is selected ...
- 1,703
1
vote
0
answers
109
views
Integer factorization given modular square root of 2
Let $N$ be composite. It is well-known that if $x^2 \equiv 1 \pmod N$, and $x \neq \pm 1 \pmod N$, then a factor of $N$ is easily found by computing gcd($N$, $x + 1$). I'm curious if there is a ...
- 1,703