オイラーの規準 \quad ― 塩田研一覚書帳 ―
平方剰余
$p$ を奇素数とするとき、$\bmod p\ $の世界の平方数を平方剰余と呼びます。例えば $$ (\pm 1)^2 \equiv 1,\quad (\pm 2)^2 \equiv 4,\quad (\pm 3)^2 \equiv 2 \quad ( \bmod 7\ ) $$ ですので、$\bmod 7\ $ の平方剰余は $1$, $2$, $4$。これに対し $3$, $5$, $6$ は $\bmod 7\ $ の平方非剰余と呼びます。 ただし $0$ はどちらにも入れません。$\bmod 13$ では $$ (\pm 1)^2 \equiv 1,\ (\pm 2)^2 \equiv 4,\ (\pm 3)^2 \equiv 9, \ (\pm 4)^2 \equiv 3 ,\ (\pm 5)^2 \equiv 12 ,\ (\pm 6)^2 \equiv 10 \ ( \bmod 13\ ) $$ ですので、平方剰余は $1$, $3$, $4$, $9$, $10$, $12$, 平方非剰余は $2$, $5$, $6$, $7$, $8$, $11$ といった具合です。平方剰余記号
平方剰余か否かを表す簡明な記号がありまして、平方剰余記号（ルジャンドル記号）と言い、 $$ \left(\frac{a}{p}\right)=\left\{ \begin{array}{rl} 0 & a \equiv 0 \ ( \bmod\, p\, ) \mbox{ のとき}\\ 1 & a \mbox{ が $\bmod\, p$ の平方剰余のとき} \\ -1 & a \mbox{ が $\bmod\, p$ の平方非剰余のとき} \\ \end{array} \right. $$ で定義されます。 （見た目は括弧付きの分数と同じですので、状況からそのどちらなのかを判断しなければなりません。）オイラーの規準
平方剰余記号については、次の「オイラーの規準」という法則が成り立ちます： $$ \left(\frac{a}{p}\right)\equiv a^{(p-1)/2} \ (\,\bmod\,p\,) $$ 上のように全ての剰余の２乗を計算してみなくてもこの法則を使えば $$ \left(\frac{3}{61}\right)\equiv 3^{(61-1)/2}\equiv 3^{30}\equiv 205891132094649\equiv 1 \ (\,\bmod\,61\,) $$ という計算で平方剰余か否かが判定できます。 公開鍵暗号で使うような大きな整数に対しては更に高速べき乗法を使うと、$O(\log^3p)$ の計算量でその判定ができます。ヤコビ記号
平方剰余記号の引数 $p$ を素数に限らず一般の正奇数に拡張したヤコビ記号の計算規則を利用すると、その計算量を $O(\log^2p)$ に減らすことができます。 このとき大活躍するのが「相互法則」と呼ばれる摩訶不思議な法則です。 2つの異なる奇素数 $p$, $q$ について、$p$ が $\bmod q\ $ で平方剰余であるか否か、と、$q$ が $\bmod p\ $ で平方剰余であるか否かの関係が明確にわかるというものです: $$ \renewcommand{\arraystretch}{2.1} \left(\frac{q}{p}\right) =\left\{ \begin{array}{rl} \displaystyle{-\left(\frac{p}{q}\right)} & p \equiv q \equiv 3 \ ( \bmod\, 4\, ) \mbox{ のとき}\\ \displaystyle{\left(\frac{p}{q}\right)} & \mbox{それ以外} \\ \end{array} \right. $$ 中国剰余定理によれば $\bmod p\ $ の情報と $\bmod q\ $ の情報は独立であるはずなのですが、 平方剰余に関してはそうではないところが興味深いところです。