12
$\begingroup$

Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre symbol $(a/p)$?

By the AKS primality test, it suffices to assume $p$ is prime. I know of two tricks to compute the Legendre symbol: quadratic reciprocity and Euler's criterion. The difficulty with naive application of quadratic reciprocity is that, in the worst case, I am led to factor, but I don't know how to do this efficiently. On the other hand, Euler's criterion naturally leads to an attractive repeated squaring algorithm, but the final multiplications are between integers of length at least $O(p)$.

Here's a related question. The accepted answer indicates that quadratic reciprocity should solve my problem, but perhaps that answer implicitly uses a factoring oracle. If not, I would love a reference that shows "the complexity of the usual computation with the laws of quadratic reciprocity is logarithmic in $p$."

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
20
$\begingroup$

For quadratic reciprocity, you need the Jacobi symbol. It's an extension of the Legendre symbol to composite $p$ that still satisfies quadratic reciprocity, so you can just apply quadratic reciprocity to your heart's content without worrying about primality. The Jacobi symbol does not generally tell you whether a number is a perfect square, so it doesn't have the same interpretation as the Legendre symbol, but it agrees with the Legendre symbol whenever $p$ is prime (so it will tell you the answer in your case, even though the intermediate results are a little strange).

However, Euler's criterion already works in polynomial time. You want to compute $a^{(p-1)/2}$ modulo $p$. As you observed, repeated squaring is a good way to deal with the fact that the exponent $(p-1)/2$ is large. Aside from that, you just need to do arithmetic modulo $p$, since you can reduce each intermediate calculation modulo $p$ before continuing. Thus, it can be done in polynomial time. (In your question, you said you need integers of length $p$, but it should be $\log p$.)

Improve this answer
$\endgroup$
6
  • 9
    $\begingroup$ Just a quibble, but when using quadratic reciprocity via the Jacobi symbol, you do still need to do a tiny amount of factorization, namely factoring out powers of 2 before flipping. (There's always at least one person in the class who forgets to do this on the exam!) $\endgroup$
    – Joe Silverman
    May 24, 2014 at 15:16
  • 5
    $\begingroup$ While Euler’s criterion works, an algorithm similar to the binary GCD algorithm using quadratic reciprocity is much faster (and simpler). Even better, one can adapt the Half-GCD algorithm to compute Jacobi (and Legendre) symbols in essentially linear time. $\endgroup$
    – Emil Jeřábek
    May 24, 2014 at 15:19
  • $\begingroup$ I don't think that quadratic reciprocity is much faster then Euler's criterion. Both need about log p steps, which in one case consist of a product and a modular reduction, and in the other case of a modular reduction and some overhead. With some care you can avoid "if", but still you have to extract the last bits and one sign. I would guess that quadratic reciprocity overtakes Euler between 50 and 100 digits, but only if you took great care in coding reciprocity. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    May 26, 2014 at 12:31
  • $\begingroup$ @Jan-Christoph Schlage-Puchta: Not really. You may be thinking of a different algorithm, because one step of the binary Jacobi algorithm amounts to a subtraction, a right shift, and a little O(1) overhead. This is $O(n)$ time, with a very small constant implied in the O. In contrast, the product and modular reduction you need for one step for Euler’s criterion will be worse than $n\log n$ even if you use FFT multiplication (which is realistically useful only for numbers with thousands of digits), and $O(n^2)$ for schoolbook multiplication. $\endgroup$
    – Emil Jeřábek
    May 26, 2014 at 13:52
  • 1
    $\begingroup$ An if can only cost as much if all your branches are mispredicted, which suggests there is something wrong with the code. By choosing wisely the representation of the sign, you can easily arrange that its updates can be done branch-free with simple bitwise operations, and Euler also needs an if per iteration anyway. I seriously doubt that Euler's criterion could be implemented faster than the binary Jacobi algorithm for anything except possibly single-word inputs, where it depends too much on details of the computing environment. $\endgroup$
    – Emil Jeřábek
    May 28, 2014 at 20:24
1
$\begingroup$

You can take a look on this talk by Brent and Zimmermann in 2010.

https://maths-people.anu.edu.au/~brent/pd/Brent_ACCMCC_10.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ A link to the Brent/Zimmermann paper "An O(M(n)log n) algorithm for the Jacobi symbol" was already given four years ago in the comment by Emil Jeřábek. $\endgroup$
    – jeq
    Oct 17, 2018 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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