2
$\begingroup$

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".

$\endgroup$

1 Answer 1

3
$\begingroup$

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,

$\endgroup$
3
  • 1
    $\begingroup$ Thank you. I should have mentioned that I already learned the Legendre symbol for existence. I appreciate the help. $\endgroup$ Feb 6, 2014 at 0:33
  • $\begingroup$ @ChristopherErnst : You can still edit your question to say so. I would not be surprised if someone gave a better answer than me. $\endgroup$ Feb 6, 2014 at 0:36
  • $\begingroup$ Thanks again. I will do that! $\endgroup$ Feb 6, 2014 at 0:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .