1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You cannot really speed up the search. You can decide if $c$ has a square-root $\bmod p$ or not in many cases. There are algorithms to compute a square-root (especially for prime $p$), see here for further information: en.wikipedia.org/wiki/…. In the general case you need the prime factorization of $p$. $\endgroup$ – gammatester Feb 1 '16 at 10:20
  • $\begingroup$ @gammatester: You certainly can speed up the search. $\endgroup$ – TonyK Feb 1 '16 at 16:59
  • $\begingroup$ @Ilya, I must say you are making heavy weather of this Quadratic Sieve project of yours! Instead of posting more and more questions here, I suggest that you obtain Prime Numbers: A Computational Perspective by Richard Crandall and Carl Pomerance. $\endgroup$ – TonyK Feb 1 '16 at 17:04
  • $\begingroup$ If you only need to answer whether there exists a square root (i.e., whether $c$ is a quadratic residue modulo a prime $p$), then using quadratic reciprocity for Legendre symbol is a very efficient way to go. If you need to find the square root, than you can have a look into the suggestions in this MO post: Is there an efficient algorithm for finding a square root modulo a prime power?. (However, this is a more difficult problem.) $\endgroup$ – Martin Sleziak Feb 2 '16 at 7:20
  • $\begingroup$ @MartinSleziak I am after: "Whether $c$ is a quadratic residue modulo a prime $p$". I found a good solution in my answer. Now when I implement the quadratic sieve algorithm, I am able to build B-Smooth vector of size 1,000,000 primes in less than a hour. Also I am aware of how to calculate it's optimal size. $\endgroup$ – Ilya Gazman Feb 2 '16 at 8:27
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you please provide an example with $c = 13$ and $p = 17$ $\endgroup$ – Ilya Gazman Feb 1 '16 at 11:39
  • $\begingroup$ Why don't you get started, and if you get stuck, I'll pitch in? You're trying to calculate the symbol $\Bigl({13\over17}\Bigr)$ – which formula can you use first? $\endgroup$ – Gerry Myerson Feb 1 '16 at 11:46
  • $\begingroup$ I am at very beginning of this. I am developer, I implemented the quadratic thieve and now I am trying to improve the initialization part where I need to pick up the B-smooth values. So I don't know what "symbol" is. I don't know how to apply the formulas that you showed me. May be with a complete example I get it. I hope I am not asking to much. $\endgroup$ – Ilya Gazman Feb 1 '16 at 12:02
  • $\begingroup$ You have linked to the wikipedia essay on quadratic reciprocity. The very first equation there is the law of quadratic reciprocity, and it uses the $\Bigl({p\over q}\Bigr)$ symbol. If you don't understand that symbol, then that's the question you should be posting (or at the very least, that's the information you should include in your question, that you don't know what that symbol means). If you don't tell people what you do and don't know, you make it very hard for them to write answers that will help you. Bye-bye. $\endgroup$ – Gerry Myerson Feb 1 '16 at 12:16
  • $\begingroup$ @GerryMyerson The reason I have edited to your post is that I think that $\left(\frac{a}{p}\right)$ is more usual symbol in this context than $\Bigl({a\atop p}\Bigr)$. I have edited it using a macro, so if you prefer some other version, it is easy to change it back by simply changing the macro. (So only change in one place is needed.) $\endgroup$ – Martin Sleziak Feb 1 '16 at 16:41
0
$\begingroup$

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;
}
$\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.