0

Using the formula $$\left(\frac{a}{p}\right) \equiv a^{\frac{p - 1}{2}} \pmod{p}$$ for the Legendre symbol $\left(\frac{a}{p}\right),$ it takes only $O(\log p)$ steps to compute $\left(\frac{a}{p}\right)$ for any $a$ and $p,$ using fast modular exponentiation.

However, after reading about the quadratic reciprocity law, $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}},$$ ($q$ and $p$ are odd primes) and seeing that this can be computed in $O(1)$ time, I would like to know if it is possible to compute $\left(\frac{q}{p}\right)$ in $O(1)$ for any odd primes $q$ and $p.$

Venkataram Sivaram
  • 125
  • What does "$O(\log n)$" mean when you never defined $n$? By the way, the efficient way to compute Legendre symbols is not with the quadratic reciprocity law for Legendre symbols, but with the reciprocity law for Jacobi symbols, which are more general and have the advantage that their calculation requires no factoring except for removing powers of 2. – KCd Jul 28 '20 at 01:30
  • $O(1)$ strikes me as rather optimistic. – Angina Seng Jul 28 '20 at 01:39

0 Answers0