quadratic residues
Summary
Legendre symbol
Concept
Quadratic residues (Definition 2.4.1)
- a residue that can be “square rooted”
Even powers of the generator (Theorem 2.4.3)
- modulo a prime, squares are exactly the even powers of a generator
- each square has two roots
implicitly
is an odd prime, ie. every prime except 2, we care about large primes, so 2 can be ignored for the most part
Half of the exponents are even
Each quadratic residue has 2 roots
note that if
is odd, then one of the roots can also be a quadratic residue
Legendre symbol (Definition 2.4.4)
Euler’s criterion (Theorem 2.4.5)
- determining if the number is a quadratic residue efficiently using modular exponentiation via square-and-multiply
there is an
algorithm to compute the legendre symbol using the law of quadratic reciprocity, but its out of scope for co485
Existence of roots
- we can find a
th root by finding - done efficiently with modular inversion(EEA) and modular exponentiation
Finding square roots (Lemma 2.4.6)
- square roots need separate treatment because
Law of quadratic reciprocity
- for distinct odd primes
Application
Quadratic residues of
Deriving the legendre symbol with euler’s theorem/fermat’s little theorem
The Legendre symbol over
For odd prime
For
The assignment’s line saying a nonresidue lies in