Quadratic reciprocity: Tell if $c$ got quadratic square root mod $p$

Question

I am reading the wiki article about Quadratic reciprocity and I don't understand how can I tell if some integer $c$ got quadratic root mod $p$?

So far I am using brute search to find $y$ such that

• $x= c\mod p$
• $y^2 \equiv x \bmod p$ for some $y \in \{0,1,\ldots,p\}$

How can I use Quadratic reciprocity to speed up my search?

Answer 1

$\newcommand{\jaco}[2]{\left(\frac{#1}{#2}\right)}$You need to know $$\jaco{ab}p=\jaco ap \jaco bp \tag1$$ $$\jaco ap=\jaco bp {\rm\ if\ }a\equiv b\bmod p\tag2$$ $$\jaco{-1}p=(-1)^{(p-1)/4}\tag3$$ $$\jaco2p=(-1)^{(p^2-1)/8}\tag4$$ and quadratic reciprocity to determine whether $c$ has a square root modulo a prime $p$. You use (2) to replace the top number, if necessary, by a number less than the bottom number. You use (1) to turn it into a problem where the top numbers are all primes (or $-1$). You use quadratic reciprocity to turn small over large into large over small, so you can use (2). Eventually, it all comes down to lots of uses of (3) and (4). Well, I guess you also need $$\jaco{a^2}p=1\tag5$$

Edit: so, let's do $\jaco{13}{17}$. None of the formulas (1), ..., (5) is helpful here, so we turn to quadratic reciprocity. In this situation, it tells us $\jaco{13}{17}=\jaco{17}{13}$. Now (2) says $\jaco{17}{13}=\jaco4{13}$. Then (5) says $\jaco4{13}=1$. Thus, 13 has a square root modulo 17.

Answer 2

Eventually I came up with this java code below, that solves the problem quite fast.

I used the basic Legendre Symbol rule.

$$\left(\frac ap\right)\equiv a^{\frac{p-1}{2}}\pmod p$$

This turns the problem in to calculating $b$ such that $a^c\equiv b(\mod p)$ where $c$ is very large number. I used Billy idea to calculate the mod of power $a$ and than recursively calculate the power of the result $\log c$ times. I used Siddhartha Sharma cleaver approach to implement it.

This is the result. Complexity $O(\log p)$

boolean isRootInQuadraticResidues(BigInteger n, BigInteger p) {
    BigInteger tow = BigInteger.valueOf(2);
    BigInteger x = n.mod(p);
    if (p.equals(tow)) {
        return x.mod(tow).equals(BigInteger.ONE);
    }
    long exponent = p.subtract(BigInteger.ONE).divide(tow).longValue();
    return modularExponentiation(x.longValue(), exponent, p.longValue()) == 1;
}

// based on https://math.stackexchange.com/a/453108/101178
long modularExponentiation(long value, long exponent, long mod) {
    long result = 1;
    while (exponent > 0) {
        if ((exponent & 1) == 1) {
            value = value % mod;
            result = (result * value) % mod;
            result = result % mod;
        }
        exponent = exponent >> 1;
        value = value % mod;
        value = (value * value) % mod;
        value = value % mod;
    }
    return result;
}