quadratic residues

Work in Progress

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 , the Mobius map is a bijection with inverse . This repairs the extracted assignment typo ; the intended contradiction is .

For , the number of pairs satisfying is

The assignment’s line saying a nonresidue lies in is a transcription error; it should say .