平方剰余

　$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$ といった具合です。

　$\FF_p = \ZZ/p\ZZ$ が体であることから、 $0$ でない剰余類のうち半分の $(p-1)/2$ 個が平方剰余、残る $(p-1)/2$ 個が平方非剰余であることがわかります。 これは、$0$ 以外の実数のうち半分の正の数が平方数で、残る半分の負の数が非平方数であることに類似した現象です。

　平方剰余の考え方は、公開鍵暗号の分野でも、二次篩法、楕円曲線の有理点計算、ゼロ知識証明、コイントス･プロトコルなど幅広い応用を持ちますので、 平方剰余か否かの判定や、平方根計算などの高速なアルゴリズムが必要となります。

平方剰余記号

　平方剰余か否かを表す簡明な記号がありまして、平方剰余記号（ルジャンドル記号）と言い、 $$\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\ $ の情報は独立であるはずなのですが、 平方剰余に関してはそうではないところが興味深いところです。

　ガウス先生は相互法則の証明を７通り(?)も発明しました。 相互法則はきっと他の対象についてもみつかるに違いない。 そのとき、自分が発明した７通りの証明法のいずれかが適用できるのではないか。 そう考えられてのことだそうです。 偉大な数学者はそれほどまでに未来を見通すものなのです。