Fast legendre symbol calculation

Question

Let's say that I would like to calculate all legendre symbols from $1$ to $p-1$ $\pmod{p}$, is there a way to calculate them in an incremental way?. For example, an incremental table of legendre symbols could help to calculate them in a memoized algorithm, but let´s assume we can't do that due to processing limitations. Is there a nice solution?

Answer 1

There is less known about the non-multiplicative structure of legendre symbols. We know, that the legendre symbol is $1$ for exactly half of $\{1,\dots,p-1\}$ and $-1$ for the other half, but the way this values are distributed is not clear.

The complexity of the usual computation with the laws of quadratic reciprocity is logarithmic in $p$. So you could calculate all symbols in $\mathcal O(p\log p)$ time. Maybe you can spare a lot of calculation by memorizing all calculated symbols, but it gets easier:

If you need to calculate all symbols, just go by the definition. Compute $$1^2,\dots,\left(\frac{p-1}{2}\right)^2$$ This will give you exactly all quadratic residiues. You can further reduce costs here, by calculating the next square as $n^2=(n-1)^2+2n-1$. So, you just need to do $\frac{p-1}{2}$ iterations, in which you add twice and reduce modulo $p$ once.

I don't think, it gets more easier.

EDIT: After ThomasAndrews' legitimate comment, I dediced, to add some pseudo-code, which provides a fast implementation:

list = ()
s = 0
for i from 1 to (p-1) / 2:
   s = s + 2 * i - 1
   if s >= p:
        s = s - p
   list.append(s)

Now, list contains exactly the values, for which $\left(\frac{\cdot}{p}\right)=1$.

Answer 2

The quadratic reciprocity theorem might be useful.