整数論において奇素数\(p\)をModulusとしたとき, \(a \in GF(p)\)について $$ x^{2} \equiv a \, mod \, p $$ となる \(x\)が存在するとき\(a\)を\(p\)の平方剰余であるという. \(a\)が平方剰余であるかどうか(上式で解を持つかどうか)を判定するのに使われ…