2
$\begingroup$

What is an efficient algorithm to find the first number $n$ such that $n^2 \equiv -1 \mod p$ for a prime $p$, if such an $n$ exists?

Is there anything better than the brute-force approach up to $p-1 \over 2$?

I know this is simple to find for primes of the form $n^2+1$ because $n^2 \equiv -1 \mod (n^2+1)$, resulting in $n$, but is there a fast way for a generic case $n$?

Ex:

  • $p = 29, n = \pm 12$
  • $p = 37, n = \pm 6$
  • $p = 41, n = \pm 9$
  • $p = 53, n = \pm 23$
$\endgroup$
7
  • 2
    $\begingroup$ Find a $k$ with $\left(\frac{k}{p}\right) = -1$. Then $k^{(p-1)/4}$ does the trick. The smallest quadratic nonresidue is typically small. $\endgroup$ Jul 31 '14 at 22:11
  • 1
    $\begingroup$ You want the smallest, so yes, you take the modulus, and it could be that $p - (k^{(p-1)/4}\bmod p)$ is smaller, so we need a $\pm$. $\endgroup$ Jul 31 '14 at 22:22
  • 1
    $\begingroup$ And, following up on @DanielFischer's comment, the most efficient way to find a quadratic non-residue is guess-and-check. Probabilistic, yes, but, ... :) $\endgroup$ Jul 31 '14 at 22:26
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Cipolla%27s_algorithm $\endgroup$
    – Will Jagy
    Jul 31 '14 at 22:30
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm $\endgroup$
    – Will Jagy
    Jul 31 '14 at 22:30
1
$\begingroup$

Such an $n$ exists iff $p=1 \mod 4$. And also $p=1 \mod 4$ iff $p=x^2+y^2$ for integers $x, y$. Then the solution is $n=\frac{x}{y} \mod p$. This could be faster using $1\le x\le \sqrt{p}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.