平方剰余

数論において、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 を二乗するだけで得られる。a² ≡ (n − a)² (mod n) であるので、n を法とする平方数のリストは n/2 に対して対称であり、リストアップは n/2 まで続ければ十分である。これは下の表で確認できる。

つまり、n を法とする平方剰余の数は、n/2 + 1（n が偶数）または n + 1/2（n が奇数）を超えることはない。

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

素数の法

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

オイラーの規準 (Euler's criterion) によると、奇素数 p を法とすると、p + 1/2 個の剰余（0を含む）と p − 1/2 個の非剰余が存在する。この場合、慣例として0を特殊なケースと見なし、体 Z/pZ の非ゼロ要素の乗法群内に議論を限定する。（言い換えると、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 の奇数の平方数は

1² ≡ 15² ≡ 1

3² ≡ 13² ≡ 9

5² ≡ 11² ≡ 25

7² ≡ 9² ≡ 49 ≡ 17

そして偶数のものは

0² ≡ 8² ≡ 16² ≡ 0

2² ≡ 6² ≡ 10² ≡ 14² ≡ 4

4² ≡ 12² ≡ 16.

したがって、0 以外の数が 8, 16, … を法として剰余となるのは、その数が 4^k(8n + 1) の形で表現できる場合でかつその場合に限る。

奇素数 p と互いに素な数 a が、p の任意のべき乗を法として剰余であるのは、p を法として剰余である場合でかつその場合に限る。

法が pⁿ の場合、

p^ka は

剰余である（k ≥ n の場合）

非剰余である（k < n が奇数の場合）

剰余である（k < n が偶数で a が剰余の場合）

非剰余である（k < n が偶数で a が非剰余の場合）

ただし、2のべき乗と奇素数のべき乗では、ルールが異なることに注意せよ。

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

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

素数のべき乗以外の合成数の法

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

a が n を法として剰余である場合、a はすべての素数のべき乗 p^k が n を割り切る p^k を法として剰余である。

a が n を法として非剰余である場合、a は少なくとも1つの素数のべき乗 p^k が n を割り切る p^k を法として非剰余である。

合成数を法として、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 と互いに素となるのは、a² が 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つは、二次指標が乗算の下で、pを法とする非ゼロ合同類の乗法群から複素数への準同型であるためである。$({\tfrac {np}{p}})=0$ とすると、その定義域をすべての整数の乗法半群に拡張することができる。

ガウスの表記法よりも優れている点の1つは、ルジャンドル記号が数式として使用できる関数であることである。また、3次、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 が最小であり、実際に 1² ≡ 1, 1046² ≡ 2, 123² ≡ 3, 2² ≡ 4, 643² ≡ 5, 87² ≡ 6, 668² ≡ 7, 429² ≡ 8, 3² ≡ 9, 529² ≡ 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/2 の範囲で、平方剰余が非剰余よりも多いことを意味する。

たとえば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 に対して、以下のようになる。

a	a が p を法として平方剰余になる同値条件	a	a が p を法として平方剰余になる同値条件
1	（すべての素数p ）	−1	p ≡1 (mod 4)
2	p ≡1, 7 (mod 8)	−2	p ≡1, 3 (mod 8)
3	p ≡1, 11 (mod 12)	−3	p ≡1 (mod 3)
4	（すべての素数p）	−4	p ≡1 (mod 4)
5	p ≡1, 4 (mod 5)	−5	p ≡1, 3, 7, 9 (mod 20)
6	p ≡1, 5, 19, 23 (mod 24)	−6	p ≡1, 5, 7, 11 (mod 24)
7	p ≡1, 3, 9, 19, 25, 27 (mod 28)	−7	p ≡1, 2, 4 (mod 7)
8	p ≡1, 7 (mod 8)	−8	p ≡1, 3 (mod 8)
9	（すべての素数p ）	−9	p ≡1 (mod 4)
10	p ≡1, 3, 9, 13, 27, 31, 37, 39, 43 (mod 40)	−10	p ≡1, 7, 9, 11, 13, 19, 23, 37 (mod 40)
11	p ≡1, 5, 7, 9, 19, 26, 35, 37, 39, 43 (mod 44)	−11	p ≡1, 3, 4, 5, 9 (mod 11)
12	p ≡1, 11 (mod 12)	−12	p ≡1 (mod 3)

「平方剰余の相互法則」も参照

剰余と非剰余のペア

素数 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}|.$

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

α₀₀ は剰余に続く剰余の数

α₀₁ は非剰余に続く剰余の数

α₁₀ は剰余に続く非剰余の数

α₁₁ は非剰余に続く非剰余の数

すると、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

A₀₀ = {1,8,15},

A₀₁ = {2,4,9,13},

A₁₀ = {3,7,12,14},

A₁₁ = {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₀₀ = {4、5、6、16},

A₀₁ = {1,7,9,11,17},

A₁₀ = {3,8,10,15},

A₁₁ = {2,12,13,14}.

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

ポリア＝ヴィノグラドフの不等式 (Pólya-;Vinogradov inequality)

連続値 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/4√e に対して n(p) ≪ p^θ というものであり、指標の和 (character sum) に関するバージェス (Burgess) の推定から得られた。一般化されたリーマン予想の仮定下では、アンケニー (Ankeny) が n(p) ≪ (log p)² を得た。リニック (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/2) の平方剰余の数から 範囲 (p/2, p) の平方剰余の数を引いたものである（オンライン整数列大辞典の数列 A178153）。p ≡ 1 mod 4 となる p では、−1 が平方剰余であり、剰余は r ↔ p - r に対して対称であるので過剰はゼロである。p ≡ 3 mod 4 となる p では、超過 E は常に正である。

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

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

1. x² ≡ a (mod n) の解 x が存在するかどうかの判定
2. 存在すると仮定して、その具体的な計算

ここでは、法が素数と合成数の場合で重要な違いが明らかになる。素数 p を法として、平方剰余 a は 1 + (a|p) 個の根を持つ（つまり、a N p の場合は根なし、a ≡ 0 (mod p) の場合は1個、a R p で (a, p) = 1 の場合は2個。）

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

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

例えば：

x² ≡ 6 (mod 15) を解く。

x² ≡ 6 (mod 3) は1つの解 x = 0, x² ≡ 6 (mod 5) が2つの解 x = 1, 4 を持つ。

したがって、15を法として2つの解 x = 6, 9 が存在する。

x² ≡ 4 (mod 15) を解く。

x² ≡ 4 (mod 3) は2つの解 x = 1, 2, x² ≡ 4 (mod 5) が2つの解 x = 2, 3 を持つ。

したがって、15を法として4つの解 x = 2, 7, 8, 13 が存在する。

x² ≡ 7 (mod 15) を解く。

x² ≡ 7 (mod 3) は2つの解 x = 1, 2 を持ち、x² ≡ 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 = p^e である場合、解は p を法として見つかるので、ヘンゼルの補題またはガウスのアルゴリズムを使用して n を法とする解に「持ち上げて」得られる。

合成数の法

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

$n\not \equiv 2{\pmod {4}}$ でクロネッカー記号(Kronecker symbol)が$\left({\tfrac {a}{n}}\right)=-1$ であれば、解は存在しない。n ≡ 2 (mod 4) で $\left({\tfrac {a}{n/2}}\right)=-1$ である場合も、解は存在しない。「 $n\not \equiv 2{\pmod {4}}$ かつ $\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{\pmod {4}}$」または「n ≡ 2 (mod 4) かつ $\left({\tfrac {a}{n/2}}\right)=1$」ならば、問題は n の素因数分解と等価であることが分かっている（つまり、どちらかの問題の効率的に解ければ、もう一方を効率的に解くことができる）。

上記の議論は、n の素因数を知ることでどのくらい根を効率的に見つけることができるかを示している。合成数を法とする平方根を見つけるための効率的なアルゴリズムがあったとしよう。平方合同 (congruence of squares) の記事では、x² ≡ y² (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とする。x² ≡ 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 ≡ x²/m (mod n/m) に還元することができるが、（m が平方数でない限り）これは平方剰余の問題の範疇を超える。

平方剰余の数

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, …（オンライン整数列大辞典の数列 A000224）

n を法とする平方数の数を数える式は、スタングル (Stangl) によって与えられる。

平方剰余の応用

音響

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

グラフ理論

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

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

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

暗号

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

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

素数判定

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

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

素因数分解

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

最新の素因数分解アルゴリズムのいくつか（ディクソンのアルゴリズム (Dixon's algorithm)、連分数法 (continued fraction method)、二次ふるい法 (quadratic sieve)、数体ふるい (number field sieve) など）は、素因数分解につながる平方合同を探す中で、（素因数分解される数を法とする）小さい平方剰余を生成する。数体ふるいは、既知の最も高速な汎用素因数分解アルゴリズムである。

平方剰余の表

次の表（オンライン整数列大辞典の数列 A096008）は、法 1から75までの平方剰余のリストである（赤字は、n と互いに素ではないことを意味する）。（n と互いに素な平方剰余については A096103 を、非ゼロな平方剰余については A046071 を参照せよ。）

n	法 n の平方剰余	n	法 n の平方剰余	n	法 n の平方剰余
1	0	26	0, 1, 3, 4, 9, 10, 12, 13, 14, 16, 17, 22, 23, 25	51	0, 1, 4, 9, 13, 15, 16, 18, 19, 21, 25, 30, 33, 34, 36, 42, 43, 49
2	0, 1	27	0, 1, 4, 7, 9, 10, 13, 16, 19, 22, 25	52	0, 1, 4, 9, 12, 13, 16, 17, 25, 29, 36, 40, 48, 49
3	0, 1	28	0, 1, 4, 8, 9, 16, 21, 25	53	0, 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52
4	0, 1	29	0, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28	54	0, 1, 4, 7, 9, 10, 13, 16, 19, 22, 25, 27, 28, 31, 34, 36, 37, 40, 43, 46, 49, 52
5	0, 1, 4	30	0, 1, 4, 6, 9, 10, 15, 16, 19, 21, 24, 25	55	0, 1, 4, 5, 9, 11, 14, 15, 16, 20, 25, 26, 31, 34, 36, 44, 45, 49
6	0, 1, 3, 4	31	0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28	56	0, 1, 4, 8, 9, 16, 25, 28, 32, 36, 44, 49
7	0, 1, 2, 4	32	0, 1, 4, 9, 16, 17, 25	57	0, 1, 4, 6, 7, 9, 16, 19, 24, 25, 28, 30, 36, 39, 42, 43, 45, 49, 54, 55
8	0, 1, 4	33	0, 1, 3, 4, 9, 12, 15, 16, 22, 25, 27, 31	58	0, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28, 29, 30, 33, 34, 35, 36, 38, 42, 45, 49, 51, 52, 53, 54, 57
9	0, 1, 4, 7	34	0, 1, 2, 4, 8, 9, 13, 15, 16, 17, 18, 19, 21, 25, 26, 30, 32, 33	59	0, 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27, 28, 29, 35, 36, 41, 45, 46, 48, 49, 51, 53, 57
10	0, 1, 4, 5, 6, 9	35	0, 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, 30	60	0, 1, 4, 9, 16, 21, 24, 25, 36, 40, 45, 49
11	0, 1, 3, 4, 5, 9	36	0, 1, 4, 9, 13, 16, 25, 28	61	0, 1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 52, 56, 57, 58, 60
12	0, 1, 4, 9	37	0, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36	62	0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28, 31, 32, 33, 35, 36, 38, 39, 40, 41, 45, 47, 49, 50, 51, 56, 59
13	0, 1, 3, 4, 9, 10, 12	38	0, 1, 4, 5, 6, 7, 9, 11, 16, 17, 19, 20, 23, 24, 25, 26, 28, 30, 35, 36	63	0, 1, 4, 7, 9, 16, 18, 22, 25, 28, 36, 37, 43, 46, 49, 58
14	0, 1, 2, 4, 7, 8, 9, 11	39	0, 1, 3, 4, 9, 10, 12, 13, 16, 22, 25, 27, 30, 36	64	0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57
15	0, 1, 4, 6, 9, 10	40	0, 1, 4, 9, 16, 20, 24, 25, 36	65	0, 1, 4, 9, 10, 14, 16, 25, 26, 29, 30, 35, 36, 39, 40, 49, 51, 55, 56, 61, 64
16	0, 1, 4, 9	41	0, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40	66	0, 1, 3, 4, 9, 12, 15, 16, 22, 25, 27, 31, 33, 34, 36, 37, 42, 45, 48, 49, 55, 58, 60, 64
17	0, 1, 2, 4, 8, 9, 13, 15, 16	42	0, 1, 4, 7, 9, 15, 16, 18, 21, 22, 25, 28, 30, 36, 37, 39	67	0, 1, 4, 6, 9, 10, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 29, 33, 35, 36, 37, 39, 40, 47, 49, 54, 55, 56, 59, 60, 62, 64, 65
18	0, 1, 4, 7, 9, 10, 13, 16	43	0, 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41	68	0, 1, 4, 8, 9, 13, 16, 17, 21, 25, 32, 33, 36, 49, 52, 53, 60, 64
19	0, 1, 4, 5, 6, 7, 9, 11, 16, 17	44	0, 1, 4, 5, 9, 12, 16, 20, 25, 33, 36, 37	69	0, 1, 3, 4, 6, 9, 12, 13, 16, 18, 24, 25, 27, 31, 36, 39, 46, 48, 49, 52, 54, 55, 58, 64
20	0, 1, 4, 5, 9, 16	45	0, 1, 4, 9, 10, 16, 19, 25, 31, 34, 36, 40	70	0, 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, 30, 35, 36, 39, 44, 46, 49, 50, 51, 56, 60, 64, 65
21	0, 1, 4, 7, 9, 15, 16, 18	46	0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18, 23, 24, 25, 26, 27, 29, 31, 32, 35, 36, 39, 41	71	0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 24, 25, 27, 29, 30, 32, 36, 37, 38, 40, 43, 45, 48, 49, 50, 54, 57, 58, 60, 64
22	0, 1, 3, 4, 5, 9, 11, 12, 14, 15, 16, 20	47	0, 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 42	72	0, 1, 4, 9, 16, 25, 28, 36, 40, 49, 52, 64
23	0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18	48	0, 1, 4, 9, 16, 25, 33, 36	73	0, 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 19, 23, 24, 25, 27, 32, 35, 36, 37, 38, 41, 46, 48, 49, 50, 54, 55, 57, 61, 64, 65, 67, 69, 70, 71, 72
24	0, 1, 4, 9, 12, 16	49	0, 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46	74	0, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36, 37, 38, 40, 41, 44, 46, 47, 48, 49, 53, 58, 62, 63, 64, 65, 67, 70, 71, 73
25	0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24	50	0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24, 25, 26, 29, 31, 34, 36, 39, 41, 44, 46, 49	75	0, 1, 4, 6, 9, 16, 19, 21, 24, 25, 31, 34, 36, 39, 46, 49, 51, 54, 61, 64, 66, 69

平方剰余

x	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
x2	1	4	9	16	25	36	49	64	81	100	121	144	169	196	225	256	289	324	361	400	441	484	529	576	625
mod 1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
mod 2	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
mod 3	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1
mod 4	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
mod 5	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0
mod 6	1	4	3	4	1	0	1	4	3	4	1	0	1	4	3	4	1	0	1	4	3	4	1	0	1
mod 7	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2
mod 8	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1
mod 9	1	4	0	7	7	0	4	1	0	1	4	0	7	7	0	4	1	0	1	4	0	7	7	0	4
mod 10	1	4	9	6	5	6	9	4	1	0	1	4	9	6	5	6	9	4	1	0	1	4	9	6	5
mod 11	1	4	9	5	3	3	5	9	4	1	0	1	4	9	5	3	3	5	9	4	1	0	1	4	9
mod 12	1	4	9	4	1	0	1	4	9	4	1	0	1	4	9	4	1	0	1	4	9	4	1	0	1
mod 13	1	4	9	3	12	10	10	12	3	9	4	1	0	1	4	9	3	12	10	10	12	3	9	4	1
mod 14	1	4	9	2	11	8	7	8	11	2	9	4	1	0	1	4	9	2	11	8	7	8	11	2	9
mod 15	1	4	9	1	10	6	4	4	6	10	1	9	4	1	0	1	4	9	1	10	6	4	4	6	10
mod 16	1	4	9	0	9	4	1	0	1	4	9	0	9	4	1	0	1	4	9	0	9	4	1	0	1
mod 17	1	4	9	16	8	2	15	13	13	15	2	8	16	9	4	1	0	1	4	9	16	8	2	15	13
mod 18	1	4	9	16	7	0	13	10	9	10	13	0	7	16	9	4	1	0	1	4	9	16	7	0	13
mod 19	1	4	9	16	6	17	11	7	5	5	7	11	17	6	16	9	4	1	0	1	4	9	16	6	17
mod 20	1	4	9	16	5	16	9	4	1	0	1	4	9	16	5	16	9	4	1	0	1	4	9	16	5
mod 21	1	4	9	16	4	15	7	1	18	16	16	18	1	7	15	4	16	9	4	1	0	1	4	9	16
mod 22	1	4	9	16	3	14	5	20	15	12	11	12	15	20	5	14	3	16	9	4	1	0	1	4	9
mod 23	1	4	9	16	2	13	3	18	12	8	6	6	8	12	18	3	13	2	16	9	4	1	0	1	4
mod 24	1	4	9	16	1	12	1	16	9	4	1	0	1	4	9	16	1	12	1	16	9	4	1	0	1
mod 25	1	4	9	16	0	11	24	14	6	0	21	19	19	21	0	6	14	24	11	0	16	9	4	1	0

関連項目

• オイラーの規準
• ガウスの補題 (数論)
• ゾロタレフの補題(Zolotarev's lemma)
• 指標の和(Character sum)
• 平方剰余の相互法則
• 平方剰余コード(Quadratic residue code)

参考文献

Disquisitiones Arithmeticaeは、ガウスの古典ラテン語から英語とドイツ語に翻訳されている。ドイツ語版には、数論に関するガウスのすべての論文が含まれている（平方剰余のすべての証明、ガウス和の符号の決定、四次剰余の相互法則の研究、および未発表のノート）。

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second corrected ed.), New York: Springer, ISBN 0-387-96254-9 
• Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen über hohere Arithmetik [Disquisitiones Arithemeticae & other papers on number theory] (second ed.), New York: Chelsea, ISBN 0-8284-0191-8 
• Bach, Eric; Shallit, Jeffrey (1996), Efficient Algorithms, Algorithmic Number Theory, I, Cambridge: The MIT Press, ISBN 0-262-02405-5 
• Crandall, Richard; Pomerance, Carl (2001), Prime Numbers: A Computational Perspective, New York: Springer, ISBN 0-387-94777-9 
• Davenport, Harold (2000), Multiplicative Number Theory (third ed.), New York: Springer, ISBN 0-387-95097-4 
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, https://archive.org/details/computersintract0000gare  A7.1: AN1, pg.249.
• Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (fifth ed.), Oxford: Oxford University Press, ISBN 978-0-19-853171-5, https://archive.org/details/introductiontoth00hard 
• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (second ed.), New York: Springer, ISBN 0-387-97329-X 
• Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66957-4 
• Manders, Kenneth L.; Adleman, Leonard (1978), “NP-Complete Decision Problems for Binary Quadratics”, Journal of Computer and System Sciences 16 (2): 168–184, doi:10.1016/0022-0000(78)90044-2. 

外部リンク

• 『平方剰余と基本的な問題』 - 高校数学の美しい物語
• Weisstein, Eric W. "Quadratic Residue". mathworld.wolfram.com (英語).
• Proof of Pólya–Vinogradov inequality - PlanetMath.（英語）