Legendre Symbol

• $p$ 奇素数の法, 整数 $a$ に対して $(\frac{a}{p})\equiv a^{\frac{p-1}{2}}$ が

  • 1: 平方剰余(QR)
  • -1: 平方剰余ではない(Non-QR)
  • 0: $a\equiv 0$

• 性質: QR = 1, NQR = -1 となるので

  • QR * QR = QR
  • QR * NQR = NQR
  • NQR * NQR = QR

• $p\equiv 3(\mathrm{mod}4)$ のとき

  • $2=\frac{(p-1)+2}{2}=\frac{p+1}{4}\ast 2$ となり, 平方根の次数がわかる
  • Site Unreachable
  • オイラーの規準 - Wikipedia
    • なぜ a^(p-1)/2 % p == 1 になるかが乗っている