平方剰余
数論において、p を法として平方数と合同である整数 q を、p を法とする平方剰余(へいほうじょうよ、quadratic residue)と呼ぶ。つまり、q が平方剰余であるとは、q に対し以下の条件を満たす整数 x が存在することを意味する:
x^2\equiv q \pmod{p}.
平方剰余でない数を平方非剰余(へいほうひじょうよ、quadratic nonresidue)と呼ぶ。
元々、合同算術という数論の一分野からの抽象的な数学的概念であった平方剰余は、現在様々な分野で応用されており、その応用先は音響工学から暗号化、大きな数の素因数分解にまで至る。
フェルマー、オイラー、ラグランジュ、ルジャンドルをはじめとする17〜18世紀の数論者たちはそれぞれ平方剰余についての定理を確立し、予想を打ち立てたが、最初の体系的な扱いはガウスのDisquisitiones ArithmeticaeのIV節 (1801) である。Article 95では、「平方剰余」と「平方非剰余」という用語を導入し、文脈から明らかであれば、形容詞「平方」を削除できると述べている。
与えられた n に対して、n を法とする平方剰余のリストは単に 0, 1, …, n − 1 を二乗するだけで得られる。a2 ≡ (n − a)2 (mod n) であるので、n を法とする平方数のリストは n に対して対称であり、リストアップは n まで続ければ十分である。これは下の表で確認できる。
つまり、n を法とする平方剰余の数は、n + 1(n が偶数)または n + 1(n が奇数)を超えることはない。
2つの剰余の積は常に剰余となる。
2 を法とすると、すべての整数が平方剰余となる。
オイラーの規準 (Euler's criterion) によると、奇素数 p を法とすると、p + 1 個の剰余(0を含む)と p − 1 個の非剰余が存在する。この場合、慣例として0を特殊なケースと見なし、体 Z/pZ のNを法とする整数の乗法群内に議論を限定する。(言い換えると、p を法とするゼロを除くすべての合同類は乗法逆元を持つ。これは合成数の法には当てはまらない。)
この規約に従うと、剰余の乗法逆元は剰余、非剰余の乗法逆元は非剰余であり、また、奇数の素数を法とすると剰余と非剰余が同数存在する。
素数を法とすると、2つの非剰余の積は剰余であり、非剰余と(非ゼロ)剰余の積は非剰余である。
平方剰余の相互法則への最初の補足は、p ≡ 1 (mod 4) ならば −1 は p を法とする平方剰余であり、p ≡ 3 (mod 4) ならば −1 は p を法とする非剰余である。これは以下のことを意味する。
p ≡ 1 (mod 4) ならば p を法とする負の剰余(絶対値が同じで符号を反転したもの)は剰余であり、負の非剰余は非剰余である。
p ≡ 3 (mod 4) ならば p を法とする負の剰余は非剰余であり、負の非剰余は剰余である。
すべての奇数の平方数は ≡ 1 (mod 8) であり、それ故に ≡ 1 (mod 4) でもある。a が奇数で、m = 8, 16 またはそれよりも大きな 2 のべき乗の場合、a は m を法とする剰余であり、これは a ≡ 1 (mod 8) と同値である。
たとえば、mod 32 の奇数の平方数は
12 ≡ 152 ≡ 1
32 ≡ 132 ≡ 9
52 ≡ 112 ≡ 25
72 ≡ 92 ≡ 49 ≡ 17
02 ≡ 82 ≡ 162 ≡ 0
22 ≡ 62 ≡ 102 ≡ 142 ≡ 4
42 ≡ 122 ≡ 16.
したがって、0 以外の数が 8, 16, … を法として剰余となるのは、その数が 4k(8n + 1) の形で表現できる場合でかつその場合に限る。
奇素数 p と互いに素な数 a が、p の任意のべき乗を法として剰余であるのは、p を法として剰余である場合でかつその場合に限る。
法が pn の場合、
pka は
剰余である(k ≥ n の場合)
非剰余である(k < n が奇数の場合)
剰余である(k < n が偶数で a が剰余の場合)
非剰余である(k < n が偶数で a が非剰余の場合)
ただし、2のべき乗と奇素数のべき乗では、ルールが異なることに注意せよ。
奇素数のべき乗 n = pk を法として、p と互いに素な剰余と非剰余の積は、p を法としたときと同じルールに従う。p は非剰余であり、一般に全ての剰余と非剰余に対して、その積の中の p のべき乗が n 以上ならば積がゼロとなることを除けば、同じルールに従う。
例えば 8 を法とすると、非剰余 3 と 5 の積は非剰余 7 であり、3, 5, 7 を互いに入れ替えた場合も同様である。実際、非剰余と1の乗法群はクラインの四元群を成す。
a が n を法として剰余である場合、a はすべての素数のべき乗 pk が n を割り切る pk を法として剰余である。
a が n を法として非剰余である場合、a は少なくとも1つの素数のべき乗 pk が n を割り切る pk を法として非剰余である。
合成数を法として、2つの剰余の積は剰余である。剰余と非剰余の積は、剰余、非剰余、またはゼロの場合がある。
たとえば、mod 6 の表から
1, 2, 3, 4, 5(太字は剰余)
剰余 3 と非剰余 5 の積は剰余 3 であるが、剰余 4と非剰余 2 の積は非剰余 2 である。
また、2つの非剰余の積は、剰余、非剰余、またはゼロのいずれかになる。
たとえば、mod 15 の表から
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14(太字は剰余)
非剰余2と非剰余8の積は剰余1だが、非剰余2と非剰余7の積は非剰余14である。
この現象は、抽象代数の言葉でよく説明できる。法と互いに素な合同類は、環 Z/nZ の単元群と呼ばれる乗法に関する群であり、平方数はその部分群となる。異なる非剰余は異なる剰余類に属している可能性があり、それらの積がどの類に属するかを予測する単純なルールは存在しない。素数を法として、平方数の部分群と単一の剰余類が存在するのみである。
たとえば15を法とする非剰余3と5の積、または非剰余5と剰余9の積、または2つの剰余9と10の積がすべてゼロであるという事実は、完全な環 Z/nZ の中にあることから生じ、この環は合成数 n の 零因子を持つ。
このため、一部の著者は、平方剰余 a は平方数であるだけでなく、法 n と互いに素でなければならないという定義を追加している。(a が n と互いに素となるのは、a2 が n と互いに素である場合でかつその場合に限る。)
これで話は片付くが、本記事では剰余が法と互いに素であるという定義は用いない。
ガウスは、R と N を使用して、それぞれ剰余性と非剰余性を表現した。
たとえば、2 R 7 と 5 N 7、また 1 R 8 と 3 N 8
この表記はコンパクトで、いくつかの目的には便利であるが、より有用な表記は二次指標とも呼ばれるルジャンドル記号であり、すべての整数 a および正の奇素数 p に対して次のように定義される。
\left( \frac{a}{p} \right) = \begin{cases}
\;\;\,0 &\text{ if }p \text { divides } a \\
+1 &\text{ if } a \operatorname{R} p \text{ and }p \text { does not divide } a \\
-1&\text{ if }a \operatorname{N} p \text{ and }p \text{ does not divide } a
\end{cases}
数値 ≡ 0 (mod p) を特別に扱う理由は2つある。1つは、これまで見てきたように、多くの公式や定理を簡単に説明できるためである。もう1つは、二次指標が乗算の下で、Nを法とする整数の乗法群から複素数への準同型であるためである。(\tfrac{np}{p}) = 0 とすると、その定義域をすべての整数の乗法半群に拡張することができる。
ガウスの表記法よりも優れている点の1つは、ルジャンドル記号が数式として使用できる関数であることである。また、三次剰余の相互法則、4次、および高次の剰余に簡単に一般化できる。
ルジャンドル記号を p が合成数である場合に一般化したものとしてヤコビ記号があるが、その特性はそれほど単純ではない。m が合成数で、ヤコビ記号が (\tfrac{a}{m}) = -1 ならば a N m であり、a R m ならば (\tfrac{a}{m}) = 1 である。しかし、(\tfrac{a}{m}) = 1 ならば、a R m と a N m のいずれなのかは判断できない。例えば、(\tfrac{2}{15}) = 1 と (\tfrac{4}{15}) = 1 に対して、2 N 15 と 4 R 15 である。m が素数の場合、ヤコビ記号とルジャンドル記号は同一のものとなる。
平方剰余は n を法としてランダムなパターンが見られ、これは音響や暗号などの応用で利用されているが、一方でその分布は規則性も示す。
算術級数の素数に関するディリクレの定理、平方剰余の定理、および中国の剰余定理 (CRT) を使うと、任意の M > 0 に対して、1, 2, …, M が全て素数 p を法として剰余であることが簡単に分かる。
例えば、p ≡ 1 (mod 8), (mod 12), (mod 5), (mod 28) ならば、平方剰余の定理から 2, 3, 5, 7 は素数 p を法として剰余であり、故に1〜10のすべての数字が剰余になる。CRTはこれが p ≡1 (mod 840) の場合と同じであり、ディリクレの定理はこの形式の素数の無限に存在すると主張する。これを満たす素数 p は 2521 が最小であり、実際に 12 ≡ 1, 10462 ≡ 2, 1232 ≡ 3, 22 ≡ 4, 6432 ≡ 5, 872 ≡ 6, 6682 ≡ 7, 4292 ≡ 8, 32 ≡ 9, 5292 ≡ 10 (mod 2521) となる。
こうした規則性の研究は、二進二次形式の類数の公式に関する(1830年代の)ディリクレの研究に由来する。q を素数、s を複素変数とし、ディリクレのL関数を次のように定義する。
L(s) = \textstyle\sum\limits_{n=1}^\infty \left( \dfrac{n}{q} \right)n^{-s}
ディリクレは、q ≡ 3 (mod 3) のとき、
L(1) = -\frac{\pi}{\sqrt{q} \textstyle\sum\limits_{n=1}^{q-1} \dfrac{n}{q} \left( \dfrac{n}{q} \right) > 0
となることを示した。したがってこの場合(素数 q ≡ 3 (mod 4))、平方剰余の和から 1, 2, …, q − 1 の範囲における非剰余の和を引いたものは負の数になる。
たとえば、11を法とすると
1, 2, 3, 4, 5, 6, 7, 8, 9, 10(太字は剰余)
1 + 4 + 9 + 5 + = 22, 2 + 6 + 7 + 8 + 10 = 33、そして差は −11 である。
実際、q > 3の場合、差は常に q の奇数倍になる。対照的に、平方剰余の和から 1, 2, …, q − 1 の範囲における非剰余の和を引いたものはゼロであり、両方の和が \frac{q(q-1)}{4} と等しいことを意味する。
ディリクレは素数 q ≡ 3 (mod 4) の場合も証明した。
L(1) = \frac{\pi}{\left( 2-\left( \frac{2}{q} \right) \right) \!\sqrt{q} \textstyle\sum\limits_{n=1}^{\frac{q-1}{2} \left( \dfrac{n}{q} \right) > 0.
これは、1, 2, …, q − 1 の範囲で、平方剰余が非剰余よりも多いことを意味する。
たとえば11を法とすると、6未満の剰余は4つ (1, 3, 4, 5) だが、非剰余は1つだけ (2) である。
これらの2つの定理に関する興味深い点は、これまでに知られているすべての証明が解析に基づくということである。どちらの定理についても、単純な証明あるいは直接の証明は発表されていない。
p と q が奇素数の場合、
「『p は q を法とする平方剰余』と『q は p を法とする平方剰余』が同値であること」は「p と q の少なくとも1つが4を法として1に合同である」と同値である。
つまり、
\left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}
である。\left( \frac{p}{q} \right) はルジャンドル記号である。
したがって、a と a を割り切らない奇素数 p に対して、以下のようになる。
素数 p を法として、n R p かつ n + 1 R p、または n N p と n + 1 R p 等となるペア n, n + 1 の数はほぼ同じである。より正確には、p を奇素数として、i, j = 0, 1 によって以下の集合を定義し
A_{ij} = \left\{ k\in\{1,2,\cdots,p-2 \}: \left( \frac{k}{p} \right) = (-1)^i \land \left( \frac{k+1}{p} \right) = (-1)^j \right\},
以下のように αij を定義する。
\alpha_{ij} = |A_{ij}|.
つまり、以下のようになる。
α00 は剰余に続く剰余の数
α01 は非剰余に続く剰余の数
α10 は剰余に続く非剰余の数
α11 は非剰余に続く非剰余の数
すると、p ≡ 1 (mod4) の場合、
\alpha_{00} = \frac{p-5}{4},\;\alpha_{01} =\alpha_{10} =\alpha_{11} = \frac{p-1}{4}
であり、p ≡ 3 (mod4) の場合、
\alpha_{01} = \frac{p+1}{4},\;\alpha_{00} =\alpha_{10} =\alpha_{11} = \frac{p-3}{4}.
である。
例:(太字は剰余)
mod 17
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
A00 = {1,8,15},
A01 = {2,4,9,13},
A10 = {3,7,12,14},
A11 = {5,6,10,11}.
mod 19
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
A00 = {4、5、6、16},
A01 = {1,7,9,11,17},
A10 = {3,8,10,15},
A11 = {2,12,13,14}.
ガウス (1828)は、p ≡ 1 (mod 4) ならば x4 ≡ 2 (mod p) という命題が p = a2 + 64 b2 と同値であることを証明し、この種の数え上げを導入した。
連続値 a に対する (\tfrac{a}{p}) の値はコイントスのような確率変数で擬似的に表現できる。具体的には、ポリアとイワン・ヴィノグラードフ (Vinogradov)が、1918年に(独立して)q をとする非主(non-principal)ディリクレ指標 χ(n) と任意の整数 M, N に対して、ランダウの記号を用いて以下のように表現できることを証明した。
\left| \textstyle\sum\limits_{n=M+1}^{M+N} \chi(n) \right| =O \left( \sqrt{q} \log q \right)
\chi(n) = \left( \frac{n}{q} \right)
とすると、長さ N の任意の区間における q を法とする平方剰余の数が以下のように表せる。
\frac{1}{2}N + O(\sqrt{q} \log q)
以下の式の証明は容易である。
\left| \textstyle\sum\limits_{n=M+1}^{M+N} \left( \dfrac{n}{q} \right) \right| < \sqrt{q} \log q
実際、
\left| \textstyle\sum\limits_{n=M+1}^{M+N} \left( \dfrac{n}{q} \right) \right| < \frac{4}{\pi^2} \sqrt{q} \log q+0.41 \sqrt{q} +0.61
となる。
ヒュー・モンゴメリー(Montgomery)とボブ・ヴォーン(Vaughan)は1977年にこれを改良し、一般化されたリーマン予想が真である場合、以下の式が成り立つことを示した。
\left| \textstyle\sum\limits_{n=M+1}^{M+N} \chi(n) \right| =O \left( \sqrt{q} \log \log q \right)
この結果から本質的に改良されたわけではないが、シューアは1918年に
\max_N \left| \textstyle\sum\limits_{n=1}^N \left( \dfrac{n}{q} \right) \right| > \dfrac{1}{2\pi} \sqrt{q}
を示し、レイモンド・ペイリー(Paley)は1932年に
\max_N \left| \textstyle\sum\limits_{n=1}^N \left( \dfrac{d}{n} \right) \right| > \dfrac{1}{7} \sqrt{d} \log \log d
を満たす d > 0 が無限に存在することを示した。
p を法とする最小平方剰余は明らかに1である。最小二次非剰余の大きさ n(p) の問題は難しいが、常に素数である。上記ポリア=ヴィノグラードフの不等式は O(\sqrt{p} \log p) を与える。無条件での最良推定値は、任意の θ > 1 に対して n(p) ≪ pθ というものであり、指標の和 (character sum) に関するバージェス (Burgess) の推定から得られた。一般化されたリーマン予想の仮定下では、アンケニー (Ankeny) が n(p) ≪ (log p)2 を得た。リニック (Linnik) は、n(p) > Xε となる X より小さい p の数は、ε に依存する定数によって制限されることを示した。
奇素数 p を法とする最小二次非剰余は次の通り。
2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 23, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 2, 5, 2, 2, 2, 7, 5, 2, 3, 2, 3, 2, 2, 37, 7, 2, 3, 5, 2, 3, 2, 3, 2, 2, 2, 11, 5, 2, 2, 5, 2, 2, 3, 7, 3, 2, 2, …A053760
p を奇素数とする。二次超過 (Quadratic excess) E(p) は、範囲 (0, p) の平方剰余の数から 範囲 (p, p) の平方剰余の数を引いたものである(A178153)。p ≡ 1 mod 4 となる p では、−1 が平方剰余であり、剰余は r ↔ p - r に対して対称であるので過剰はゼロである。p ≡ 3 mod 4 となる p では、超過 E は常に正である。
つまり、数値 a と法 n が与えられたときに、以下のタスクがどれほど難しいか、ということである。
x2 ≡ a (mod n) の解 x が存在するかどうかの判定
存在すると仮定して、その具体的な計算
ここでは、法が素数と合成数の場合で重要な違いが明らかになる。素数 p を法として、平方剰余 a は 1 + (a|p) 個の根を持つ(つまり、a N p の場合は根なし、a ≡ 0 (mod p) の場合は1個、a R p で (a, p) = 1 の場合は2個。)
一般に、もし法が合成数 n であれば、n を異なる素数のべき乗の積として表現したときに、その最初のものを法として根の数が n1 個、次のものを法として根の数が n2 個…と続けていくと、n を法として n1n2… 個の根が存在する。
素数のべき乗を法とする解を組み合わせて n を法とする解を作る理論的な方法は、中国の剰余定理と呼ばれ、効率的なアルゴリズムで実装できる。
例えば:
x2 ≡ 6 (mod 15) を解く。
x2 ≡ 6 (mod 3) は1つの解 x = 0, x2 ≡ 6 (mod 5) が2つの解 x = 1, 4 を持つ。
したがって、15を法として2つの解 x = 6, 9 が存在する。
x2 ≡ 4 (mod 15) を解く。
x2 ≡ 4 (mod 3) は2つの解 x = 1, 2, x2 ≡ 4 (mod 5) が2つの解 x = 2, 3 を持つ。
したがって、15を法として4つの解 x = 2, 7, 8, 13 が存在する。
x2 ≡ 7 (mod 15) を解く。
x2 ≡ 7 (mod 3) は2つの解 x = 1, 2 を持ち、x2 ≡ 7 (mod 5) は解が存在しない。
したがって、15を法として解が存在しない。
まず、法 n が素数である場合、ルジャンドル記号 \left( \frac{a}{n} \right) はユークリッドの互除法のバリエーションまたはオイラーの規準を使用して、すばやく計算できる。-1の場合、解は存在しない。
次に \left( \frac{a}{n} \right)=1 と仮定すると、n ≡ 3 (mod 4) の場合 ラグランジュは、解が以下の式によって与えられることを発見した。
x \equiv \pm\; a^{(n+1)/4} \pmod{n}
そしてルジャンドルは、n ≡ 5 (mod 8) の場合の同様の解を発見した。
x \equiv \begin{cases}
\pm\; a^{(n+3)/8} \pmod{n}
& \text{ if } a \text{ is a quartic residue modulo } n \\
\pm\; a^{(n+3)/8} 2^{(n-1)/4} \pmod{n}
& \text{ if } a \text{ is a quartic non-residue modulo } n
\end{cases}
しかし、素数 n ≡ 1 (mod 8) に対しては、既知の公式が存在しない。トネリ・シャンクスのアルゴリズム(1891年)とチポラのアルゴリズムは、それぞれすべての素数の法に使える効率的なアルゴリズムを発見した。どちらのアルゴリズムも n を法とする平方非剰余を見つける必要があり、そのための効率的な既知の決定論的アルゴリズムは存在しない。しかし、1 から n の間の数の半分は非剰余であるため、非剰余が見つかるまで、ランダムに数 x を選んでルジャンドル記号 \left( \frac{x}{n} \right) を計算すると、すぐに非剰余が求まる。このアルゴリズムをわずかに変形したものがトネリ・シャンクスのアルゴリズムである。
法 n が素数のべき乗 n = pe である場合、解は p を法として見つかるので、ヘンゼルの補題またはガウスのアルゴリズムを使用して n を法とする解に「持ち上げて」得られる。
法 n が素数のべき乗に素因数分解される場合、解は上記の通りである。
n \not \equiv 2 \pmod4 でクロネッカーの記号(Kronecker symbol)が\left( \tfrac{a}{n} \right) =-1 であれば、解は存在しない。n ≡ 2 (mod 4) で \left( \tfrac{a}{n/2} \right) =-1 である場合も、解は存在しない。「 n \not \equiv 2 \pmod4 かつ \left( \tfrac{a}{n} \right) =1」または「 n ≡ 2 (mod 4) かつ \left( \tfrac{a}{n/2} \right)=1」 ならば、解が存在する場合としない場合がある。
n の完全な素因数分解が不明な場合、「\left( \tfrac{a}{n} \right) =1 かつ n \not \equiv 2 \pmod4」または「n ≡ 2 (mod 4) かつ \left( \tfrac{a}{n/2} \right)=1」ならば、問題は n の素因数分解と等価であることが分かっている(つまり、どちらかの問題の効率的に解ければ、もう一方を効率的に解くことができる)。
上記の議論は、n の素因数を知ることでどのくらい根を効率的に見つけることができるかを示している。合成数を法とする平方根を見つけるための効率的なアルゴリズムがあったとしよう。平方合同 (congruence of squares) の記事では、x2 ≡ y2 (mod n) である二つの数 x, y の求め方について説明しており、x ≠ ±y であれば n は十分効率的に素因数分解される。ここで乱数を生成し、n を法として乱数を二乗し、効率的な平方根アルゴリズムで根を見つける。これを、最初に二乗した値(または n を法とする負の数)と等しくない数を返すまで繰り返した後に、平方合同で説明したアルゴリズムを用いる。素因数分解アルゴリズムの効率性は、この根探索器の特性そのものに依存するが(たとえば、すべての根を返すか?最小の根だけを返すか?ランダムな根を返すか?)、これは効率的である。
n を法として a が平方剰余であるか非剰余であるか( a R n または a N n と表される)の判定は、ルジャンドル記号を計算することで、素数 n に対して効率的に行うことができる。ただし、n が合成数の場合は平方剰余性問題 (quadratic residuosity problem) となり、これは素因数分解ほど計算難度の仮定かは分かっていないが、かなり難しいと考えられている。
一方、ある上限値 c より小さい x の解があるかどうかを判定する場合、この問題はNP完全である。ただし、これは c をパラメータとする固定パラメータ容易性問題である。
一般に、合成数 n を法として a が平方剰余であるかどうかを判定するには、次の定理を使用できる:
n > 1とし、gcd(a,n) = 1とする。x2 ≡ a (mod n) が解けることと以下の条件は同値である:
n のすべての奇数の約数 p について、ルジャンドル記号表現が \left( \frac{a}{p} \right) =1 である。
n が4割り切れるが8で割り切れない場合は a ≡ 1 (mod 4)。または n が8で割り切れる場合は a ≡ 1 (mod 8)。
注:この定理を使うに当たって本質的には n の素因数分解が既知である必要がある。また、gcd(a,n) = m の場合、合同関係は a/m ≡ x2/m (mod n/m) に還元することができるが、(m が平方数でない限り)これは平方剰余の問題の範疇を超える。
n = 1, 2, 3, … に対する n を法とする平方剰余の数のリストは、以下の通りである。