平方剰余

数論において、p}} を法として平方数と合同である整数 q}} を、p}} を法とする平方剰余と呼ぶ。つまり、q}} が平方剰余であるとは、q}} に対し以下の条件を満たす整数 x}} が存在することを意味する：

平方剰余でない数を平方非剰余と呼ぶ。

元々、合同算術という数論の一分野からの抽象的な数学的概念であった平方剰余は、現在様々な分野で応用されており、その応用先は音響工学から暗号化、大きな数の素因数分解にまで至る。

1. 歴史、規約、および基本的な事実
------------------

フェルマー、オイラー、ラグランジュ、ルジャンドルをはじめとする17〜18世紀の数論者たちはそれぞれ平方剰余についての定理を確立し、予想を打ち立てたが、最初の体系的な扱いはガウスの//Disquisitiones Arithmeticae//のIV節  である。Article 95では、「平方剰余」と「平方非剰余」という用語を導入し、文脈から明らかであれば、形容詞「平方」を削除できると述べている。

与えられた n}} に対して、n}} を法とする平方剰余のリストは単に 0, 1, …, Nowrap を二乗するだけで得られる。//a//sup であるので、n}} を法とする平方数のリストは sfrac に対して対称であり、リストアップは sfrac まで続ければ十分である。これは下の表で確認できる。

つまり、n}} を法とする平方剰余の数は、sfracまたは sfracを超えることはない。

2つの剰余の積は常に剰余となる。

1.1. 素数の法
---------

2 を法とすると、すべての整数が平方剰余となる。

オイラーの規準  によると、奇素数 //p// を法とすると、//p// + 1 個の剰余と //p// − 1 個の非剰余が存在する。この場合、慣例として0を特殊なケースと見なし、体 Z///p//Z のNを法とする整数の乗法群内に議論を限定する。

この規約に従うと、剰余の乗法逆元は剰余、非剰余の乗法逆元は非剰余であり、また、奇数の素数を法とすると剰余と非剰余が同数存在する。

素数を法とすると、2つの非剰余の積は剰余であり、非剰余と剰余の積は非剰余である。

平方剰余の相互法則への最初の補足は、//p// ≡ 1  ならば −1 は //p// を法とする平方剰余であり、//p// ≡ 3  ならば −1 は //p// を法とする非剰余である。これは以下のことを意味する。

//p// ≡ 1  ならば //p// を法とする負の剰余は剰余であり、負の非剰余は非剰余である。

//p// ≡ 3  ならば //p// を法とする負の剰余は非剰余であり、負の非剰余は剰余である。

1.2. 素数のべき乗の法
-------------

すべての奇数の平方数は ≡ 1  であり、それ故に ≡ 1  でもある。//a// が奇数で、//m// = 8, 16 またはそれよりも大きな 2 のべき乗の場合、//a// は //m// を法とする剰余であり、これは //a// ≡ 1  と同値である。

たとえば、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, … を法として剰余となるのは、その数が 4//k//}} の形で表現できる場合でかつその場合に限る。奇素数 //p// と互いに素な数 //a// が、//p// の任意のべき乗を法として剰余であるのは、//p// を法として剰余である場合でかつその場合に限る。

法が //pn}}// の場合、

//pk}}a// は 剰余である 非剰余である 剰余である 非剰余であるただし、2のべき乗と奇素数のべき乗では、ルールが異なることに注意せよ。

奇素数のべき乗 //n// = //pk}}// を法として、//p// と互いに素な剰余と非剰余の積は、//p// を法としたときと同じルールに従う。//p// は非剰余であり、一般に全ての剰余と非剰余に対して、その積の中の //p// のべき乗が //n// 以上ならば積がゼロとなることを除けば、同じルールに従う。

例えば 8 を法とすると、非剰余 3 と 5 の積は非剰余 7 であり、3, 5, 7 を互いに入れ替えた場合も同様である。実際、非剰余と1の乗法群はクラインの四元群を成す。

1.3. 素数のべき乗以外の合成数の法
-------------------

この場合の基本的な事実は

//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///n//Z の単元群と呼ばれる乗法に関する群であり、平方数はその部分群となる。異なる非剰余は異なる剰余類に属している可能性があり、それらの積がどの類に属するかを予測する単純なルールは存在しない。素数を法として、平方数の部分群と単一の剰余類が存在するのみである。たとえば15を法とする非剰余3と5の積、または非剰余5と剰余9の積、または2つの剰余9と10の積がすべてゼロであるという事実は、完全な環 Z///n//Z の中にあることから生じ、この環は合成数 //n// の 零因子を持つ。

このため、一部の著者は、平方剰余 //a// は平方数であるだけでなく、法 //n// と互いに素でなければならないという定義を追加している。

これで話は片付くが、本記事では剰余が法と互いに素であるという定義は用いない。

2. 記法
-----

ガウスは、R}} と N}} を使用して、それぞれ剰余性と非剰余性を表現した。

たとえば、2 R 7}} と 5 N 7}}、また 1 R 8}} と この表記はコンパクトで、いくつかの目的には便利であるが、より有用な表記は二次指標とも呼ばれるルジャンドル記号であり、すべての整数 //a// および正の奇素数 p}} に対して次のように定義される。

数値 ≡ 0  を特別に扱う理由は2つある。1つは、これまで見てきたように、多くの公式や定理を簡単に説明できるためである。もう1つは、二次指標が乗算の下で、Nを法とする整数の乗法群から複素数への準同型であるためである。 とすると、その定義域をすべての整数の乗法半群に拡張することができる。

ガウスの表記法よりも優れている点の1つは、ルジャンドル記号が数式として使用できる関数であることである。また、三次剰余の相互法則、4次、および高次の剰余に簡単に一般化できる。

ルジャンドル記号を p}} が合成数である場合に一般化したものとしてヤコビ記号があるが、その特性はそれほど単純ではない。m}} が合成数で、ヤコビ記号が ならば //a// N //m//}} であり、//a// R //m//}} ならば である。しかし、 ならば、//a// R //m//}} と //a// N //m//}} のいずれなのかは判断できない。例えば、 と に対して、2 N 15}} と 4 R 15}} である。m}} が素数の場合、ヤコビ記号とルジャンドル記号は同一のものとなる。

3. 平方剰余の分布
----------

平方剰余は //n// を法としてランダムなパターンが見られ、これは音響や暗号などの応用で利用されているが、一方でその分布は規則性も示す。

算術級数の素数に関するディリクレの定理、平方剰余の定理、および中国の剰余定理  を使うと、任意の //M// > 0 に対して、1, 2, …, //M// が全て素数 //p// を法として剰余であることが簡単に分かる。

例えば、//p// ≡ 1 , , ,  ならば、平方剰余の定理から 2, 3, 5, 7 は素数 //p// を法として剰余であり、故に1〜10のすべての数字が剰余になる。CRTはこれが //p// ≡1  の場合と同じであり、ディリクレの定理はこの形式の素数の無限に存在すると主張する。これを満たす素数 //p// は 2521 が最小であり、実際に 12}} ≡ 1, 10462}} ≡ 2, 1232}} ≡ 3, 22}} ≡ 4, 6432}} ≡ 5, 872}} ≡ 6, 6682}} ≡ 7, 4292}} ≡ 8, 32}} ≡ 9, 5292}} ≡ 10  となる。

3.1. ディリクレの公式
-------------

こうした規則性の研究は、二進二次形式の類数の公式に関するディリクレの研究に由来する。//q// を素数、//s// を複素変数とし、ディリクレのL関数を次のように定義する。

ディリクレは、//q// ≡ 3  のとき、

となることを示した。したがってこの場合、平方剰余の和から 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 の範囲における非剰余の和を引いたものはゼロであり、両方の和が と等しいことを意味する。

ディリクレは素数 //q// ≡ 3  の場合も証明した。

これは、1, 2, …, //q// − 1 の範囲で、平方剰余が非剰余よりも多いことを意味する。

たとえば11を法とすると、6未満の剰余は4つ  だが、非剰余は1つだけ  である。 これらの2つの定理に関する興味深い点は、これまでに知られているすべての証明が解析に基づくということである。どちらの定理についても、単純な証明あるいは直接の証明は発表されていない。

3.2. 平方剰余の相互法則
--------------

//p// と //q// が奇素数の場合、

「『//p// は //q// を法とする平方剰余』と『//q// は //p// を法とする平方剰余』が同値であること」は「//p// と //q// の少なくとも1つが4を法として1に合同である」と同値である。つまり、

である。 はルジャンドル記号である。

したがって、//a// と //a// を割り切らない奇素数 //p// に対して、以下のようになる。



3.3. 剰余と非剰余のペア
--------------

素数 //p// を法として、//n// R //p//}} かつ //n// + 1 R //p//}}、または //n// N //p//}} と //n// + 1 R //p//}} 等となるペア //n//, //n// + 1}} の数はほぼ同じである。より正確には、//p// を奇素数として、//i//, //j// = 0, 1 によって以下の集合を定義し

以下のように //αij}}// を定義する。

つまり、以下のようになる。

α00}} は剰余に続く剰余の数 α01}} は非剰余に続く剰余の数 α10}} は剰余に続く非剰余の数 α11}} は非剰余に続く非剰余の数すると、//p// ≡ 1  の場合、

であり、//p// ≡ 3  の場合、

である。

例： mod 171, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 //A//00}} = {1,8,15}, //A//01}} = {2,4,9,13}, //A//10}} = {3,7,12,14}, //A//11}} = {5,6,10,11}.mod 19

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 //A//00}} = {4、5、6、16}, //A//01}} = {1,7,9,11,17}, //A//10}} = {3,8,10,15}, //A//11}} = {2,12,13,14}.

ガウス は、//p// ≡ 1  ならば //x//4}} ≡ 2  という命題が //p// = //a//2}} + 64 //b//2}} と同値であることを証明し、この種の数え上げを導入した。

3.4. ポリア＝ヴィノグラドフの不等式 
---------------------------------------------------

連続値 //a// に対する の値はコイントスのような確率変数で擬似的に表現できる。具体的には、ポリアとイワン・ヴィノグラードフ が、1918年に//q// をとする非主ディリクレ指標 χ と任意の整数 //M//, //N// に対して、ランダウの記号を用いて以下のように表現できることを証明した。

ここで

とすると、長さ //N// の任意の区間における //q// を法とする平方剰余の数が以下のように表せる。

以下の式の証明は容易である。

実際、

となる。

ヒュー・モンゴメリーとボブ・ヴォーンは1977年にこれを改良し、一般化されたリーマン予想が真である場合、以下の式が成り立つことを示した。

この結果から本質的に改良されたわけではないが、シューアは1918年に

を示し、レイモンド・ペイリーは1932年に

を満たす //d// > 0 が無限に存在することを示した。

3.5. 最小二次非剰余
------------

//p// を法とする最小平方剰余は明らかに1である。最小二次非剰余の大きさ //n// の問題は難しいが、常に素数である。上記ポリア＝ヴィノグラードフの不等式は を与える。無条件での最良推定値は、任意の //θ// > sfrac に対して //n// ≪ //pθ}}// というものであり、指標の和  に関するバージェス  の推定から得られた。一般化されたリーマン予想の仮定下では、アンケニー  が //n// ≪ 2}} を得た。リニック  は、//n// > //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, …

3.6. 二次超過
---------

//p// を奇素数とする。二次超過  //E// は、範囲  の平方剰余の数から 範囲  の平方剰余の数を引いたものである。//p// ≡ 1 mod 4 となる //p// では、−1 が平方剰余であり、剰余は //r// ↔ //p// - //r//}} に対して対称であるので過剰はゼロである。//p// ≡ 3 mod 4 となる //p// では、超過 //E// は常に正である。

4. 平方根を見つけることの複雑さ
-----------------

つまり、数値 //a// と法 //n// が与えられたときに、以下のタスクがどれほど難しいか、ということである。

//x//2}} ≡ //a//  の解 //x// が存在するかどうかの判定
存在すると仮定して、その具体的な計算ここでは、法が素数と合成数の場合で重要な違いが明らかになる。素数 //p// を法として、平方剰余 //a// は 1 +  個の根を持つ

一般に、もし法が合成数 //n// であれば、//n// を異なる素数のべき乗の積として表現したときに、その最初のものを法として根の数が //n//1}} 個、次のものを法として根の数が //n//2}} 個…と続けていくと、//n// を法として //n//1}}//n//2}}… 個の根が存在する。

素数のべき乗を法とする解を組み合わせて //n// を法とする解を作る理論的な方法は、中国の剰余定理と呼ばれ、効率的なアルゴリズムで実装できる。

例えば： //x//2}} ≡ 6  を解く。 //x//2}} ≡ 6  は1つの解 //x// = 0, //x//2}} ≡ 6  が2つの解 //x// = 1, 4 を持つ。 したがって、15を法として2つの解 //x// = 6, 9 が存在する。 x2}} ≡ 4  を解く。 x2}} ≡ 4  は2つの解 //x// = 1, 2, x2}} ≡ 4  が2つの解 //x// = 2, 3 を持つ。 したがって、15を法として4つの解 //x// = 2, 7, 8, 13 が存在する。 x2}} ≡ 7  を解く。 x2}} ≡ 7  は2つの解 //x// = 1, 2 を持ち、//x//2}} ≡ 7  は解が存在しない。 したがって、15を法として解が存在しない。

4.1. 素数または素数べき乗の法
-----------------

まず、法 //n// が素数である場合、ルジャンドル記号 はユークリッドの互除法のバリエーションまたはオイラーの規準を使用して、すばやく計算できる。-1の場合、解は存在しない。

次に と仮定すると、//n// ≡ 3  の場合 ラグランジュは、解が以下の式によって与えられることを発見した。

そしてルジャンドルは、//n// ≡ 5  の場合の同様の解を発見した。

しかし、素数 //n// ≡ 1  に対しては、既知の公式が存在しない。トネリ・シャンクスのアルゴリズムとチポラのアルゴリズムは、それぞれすべての素数の法に使える効率的なアルゴリズムを発見した。どちらのアルゴリズムも //n// を法とする平方非剰余を見つける必要があり、そのための効率的な既知の決定論的アルゴリズムは存在しない。しかし、1 から //n// の間の数の半分は非剰余であるため、非剰余が見つかるまで、ランダムに数 //x// を選んでルジャンドル記号 を計算すると、すぐに非剰余が求まる。このアルゴリズムをわずかに変形したものがトネリ・シャンクスのアルゴリズムである。

法 //n// が素数のべき乗 //n// = //pe}}// である場合、解は //p// を法として見つかるので、ヘンゼルの補題またはガウスのアルゴリズムを使用して //n// を法とする解に「持ち上げて」得られる。

4.2. 合成数の法
----------

法 //n// が素数のべき乗に素因数分解される場合、解は上記の通りである。

でクロネッカーの記号が であれば、解は存在しない。//n// ≡ 2  で である場合も、解は存在しない。「 かつ 」または「 //n// ≡ 2  かつ 」 ならば、解が存在する場合としない場合がある。

//n// の完全な素因数分解が不明な場合、「 かつ 」または「//n// ≡ 2  かつ 」ならば、問題は //n// の素因数分解と等価であることが分かっている。

上記の議論は、//n// の素因数を知ることでどのくらい根を効率的に見つけることができるかを示している。合成数を法とする平方根を見つけるための効率的なアルゴリズムがあったとしよう。平方合同  の記事では、//x//sup である二つの数 //x//, //y// の求め方について説明しており、//x// ≠ ±//y//}} であれば //n// は十分効率的に素因数分解される。ここで乱数を生成し、//n// を法として乱数を二乗し、効率的な平方根アルゴリズムで根を見つける。これを、最初に二乗した値と等しくない数を返すまで繰り返した後に、平方合同で説明したアルゴリズムを用いる。素因数分解アルゴリズムの効率性は、この根探索器の特性そのものに依存するが、これは効率的である。//n// を法として //a// が平方剰余であるか非剰余であるかの判定は、ルジャンドル記号を計算することで、素数 //n// に対して効率的に行うことができる。ただし、//n// が合成数の場合は平方剰余性問題  となり、これは素因数分解ほど計算難度の仮定かは分かっていないが、かなり難しいと考えられている。

一方、ある上限値 //c// より小さい //x// の解があるかどうかを判定する場合、この問題はNP完全である。ただし、これは //c// をパラメータとする固定パラメータ容易性問題である。

一般に、合成数 //n// を法として //a// が平方剰余であるかどうかを判定するには、次の定理を使用できる：

//n// > 1}}とし、1=gcd = 1}}とする。//x//sup が解けることと以下の条件は同値である：

//n// のすべての奇数の約数 //p// について、ルジャンドル記号表現が である。
//n// が4割り切れるが8で割り切れない場合は //a// ≡ 1 }}。または //n// が8で割り切れる場合は //a// ≡ 1 }}。注：この定理を使うに当たって本質的には //n// の素因数分解が既知である必要がある。また、1=gcd = //m//}} の場合、合同関係は //a/////m// ≡ //x//sup に還元することができるが、これは平方剰余の問題の範疇を超える。

5. 平方剰余の数
---------

//n// = 1, 2, 3, … に対する //n// を法とする平方剰余の数のリストは、以下の通りである。

1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, …//n// を法とする平方数の数を数える式は、スタングル  によって与えられる。

6. 平方剰余の応用
----------

6.1. 音響
-------

サウンドディフューザーは、原始根や平方剰余などの数論的概念に基づいている。

6.2. グラフ理論
----------

ペイリーグラフ  は、各素数 //p// ≡ 1  がカンファレンスグラフの無限族を形成する稠密な無向グラフであり、これによって対称カンファレンス行列  の無限族が導かれる。

ペイリー双グラフ  はペイリーグラフを有向グラフとしたもので、素数は //p// ≡ 3  を用い、反対称カンファレンス行列が導かれる。

これらのグラフの作成には、平方剰余が用いられる。

6.3. 暗号
-------

大きな合成数 //n// を法とする数値の平方根を見つけることは、素因数分解に相当するという事実は、Rabin暗号や紛失転送プロトコルなどの暗号化スキームの構築に使用されている。平方剰余性問題は、ゴールドワッサー-ミカリ暗号の基礎を成す。

離散対数も暗号化で用いられる同様の問題である。

6.4. 素数判定
---------

オイラーの規準は、//p// が素数であるルジャンドル記号  の公式である。//p// が合成数の場合、公式は  を正しく計算できる場合もできない場合もある。与えられた数 //n// が素数であるか合成数であるかについてのソロベイ-シュトラッセン素数判定法は、ランダムな //a// を選び、ユークリッドの互除法の修正とオイラーの基準を使用して  を計算する。結果が一致しない場合、//n// は合成数である。一致する場合、//n// は合成数または素数である。合成数 //n// に対して、2, 3, …, //n// − 1 の範囲中、少なくとも半分の //a// では「//n// は合成数」と判定されるが、素数 //n// に対しては何も出力しない。多くの異なる //a// を試しても //n// が合成数と判定されなければ、//n// は確率的素数と呼ばれる。

ミラー–ラビン素数判定法も同じ原理に基づく。この判定法は決定論的なバージョンがあるが、これが正しく判定できるかの証明は一般化されたリーマン仮説  依存する。この判定法の出力は、「//n// は完全に合成数」または「//n// は素数かGRHは偽である」のいずれかである。合成数 //n// に対して出力が後者の場合、GRHは偽になり、数学の多くの分野に影響を及ぼす可能性がある。

6.5. 素因数分解
----------

//Disquisitiones Arithmeticae'§VI//で、ガウスは平方剰余と平方剰余の相互法則を使用する2つの素因数分解アルゴリズムについて説明している。

最新の素因数分解アルゴリズムのいくつかは、素因数分解につながる平方合同を探す中で、小さい平方剰余を生成する。数体ふるいは、既知の最も高速な汎用素因数分解アルゴリズムである。

7. 平方剰余の表
---------

次の表は、法 1から75までの平方剰余のリストである。



8. 関連項目
-------

オイラーの規準
ガウスの補題 
ゾロタレフの補題
指標の和
平方剰余の相互法則
平方剰余コード

9. 脚注
-----

10. 参考文献
--------

//Disquisitiones Arithmeticae//は、ガウスの古典ラテン語から英語とドイツ語に翻訳されている。ドイツ語版には、数論に関するガウスのすべての論文が含まれている。

last=Garey A7.1: AN1, pg.249.

11. 外部リンク
---------