Let's say that I'm looking for all quadratic residues of a number. THe example from my book is 31. So I can just evaluate $i^2\equiv{a}\pmod{31}$, for $i=1..15$. While not a terribly difficult task, this seems to take a while for large moduli. Is there, other than writing an algorithm on a computer program, a quick way to determine just exactly which numbers are residues and non-residues? Are there patterns for particular numbers like composite vs. prime, specific multiples carry particular types of residues?
EDIT: I should mentioned that I already know how to show the existence of residues using Euler's criterion / the Legendre symbol. I'm specifically looking for a tip/method to determine the actual residues other than "plug and chug".
In your case, $31$ is prime, so you want to check if the Legendre symbol of $a$ is $1$. If it is, then if you manage to find a primitive root $\pmod{31}$, you can use this primitive root to find a quadratic residue for $a$. A primitive root is simply a generator for the group of units of $\mathbb F_p$, i.e. the integers $\pmod p$ with $0$ removed.
Therefore you want algorithms that find primitive roots fast, assuming you work modulo a large prime power (or modulo some number which admits a primitive root, I don't remember exactly the characterization). I'm afraid I'm not a specialist in those algorithms, but I know the literature is out there.
Hope that helps,