All Questions

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$....

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 ...

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 ...