平方剰余

数論では、整数 qがnを法とした平方剰余 であるとは、nを法とした完全平方と合同であることを意味する。つまり、

x^{2}\equiv q{\pmod {n}}.

それ以外の場合、qはnを法とする二次非剰余です。

二次剰余は、音響工学から暗号化、大きな数の因数分解まで、さまざまな用途に使用されます。

歴史、慣習、基本的な事実

フェルマー、オイラー、ラグランジュ、ルジャンドルといった17世紀から18世紀の数論学者たちは、平方剰余に関する定理^[1]を確立し、予想^{[2]を形成したが、体系的に扱った最初の例は}ガウスの『算術論』（1801年）第4章である。第95条では「平方剰余」と「平方非剰余」という用語が導入され、文脈から明らかな場合は形容詞「平方」を省略してもよいとされている。

与えられたnについて、 nを法とする平方剰余のリストは、すべての数 0、1、...、n − 1を単純に2乗するだけで得られます。a ≡ b (mod n )はa ² ≡ b ² (mod n ) を意味するため、その他の平方剰余は、得られたリストのいずれかと合同 (mod n ) です。ただし、得られたリストは、互いに合同でない平方剰余 (mod n ) だけで構成されているわけではありません。a ² ≡( n − a ) ² (mod n ) であるため、リスト 1、2、...、n − 1 (またはリスト 0、1、...、n ) のすべての数を2乗して得られたリストは、その中点について対称 (mod n ) であり、したがって実際にはリスト 0、1、...、 n /2のすべての数を2乗するだけで済みます。このようにして得られたリストには、互いに合同な数 (mod n )がまだ含まれている可能性があります。したがって、 nを法とする互いに不同な平方剰余の数は、n /2 + 1（nが偶数）または（n + 1）/2（nが奇数）を超えることはできない。^[3] $\lfloor$ $\rfloor$

2 つの剰余の積は常に剰余です。

プライム係数

2 を法として、すべての整数は平方剰余です。

奇素数 pを法として、オイラーの基準により、( p + 1)/2個の剰余（0を含む）と( p − 1)/2個の非剰余が存在する。この場合、0を特別なケースとみなし、体の非零元の乗法群の範囲内で作業するのが慣例である。言い換えれば、pを法として0を除くすべての合同類には乗法逆が存在する。これは合成法には当てはまらない。^[4] $(\mathbb {Z} /p\mathbb {Z} )$

この慣例に従うと、剰余の逆数は剰余であり、非剰余の逆数は非剰余である。^[5]

この規則に従うと、奇数の素数を法として剰余数と非剰余数の数は等しくなります。^[4]

素数を法として、２つの非剰余数の積は剰余であり、非剰余数と（非ゼロの）剰余数の積は非剰余である。^[5]

二次相互法則の最初の補足^[6]は、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)のときのみである。 ^[7]

例えば、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。

^{したがって、非ゼロの数が 4 k} (8 n + 1)の形式である場合に限り、その数は 8、16 などを法とする剰余となります。

奇数素数pと互いに素な数aがpの任意のべき乗を法とした剰余である場合、かつそれがpを法とした剰余である場合に限ります。^[8]

係数がp ^{n の}場合、

次にp ^k a

k ≥ nのときp ^nを法とする剰余である

k < nが奇数の場合、p ⁿを法とする非剰余である

k < nが偶数でaが剰余であるとき、 p ⁿを法とする剰余である。

k < nが偶数でaが非剰余であるとき、 aはp ⁿを法とする非剰余である。^[9]

2 の累乗と奇数の素数の累乗ではルールが異なることに注意してください。

奇素数乗n = p ^{k を}法として、 p と互いに素な剰余と非剰余の積は、pを法として同じ規則に従います。pは非剰余であり、一般にすべての剰余と非剰余は同じ規則に従います。ただし、積におけるpのべき乗がn以上の場合には積がゼロになります。

8 を法として、非剰余数 3 と 5 の積は非剰余数 7 であり、3、5、7 の順列についても同様です。実際、非剰余数と 1 の乗法群は、クラインの 4 元群を形成します。

合成係数は素数ではない

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

もしa がnを法とする剰余ならば、n を割り切るすべての素数に対してa はp ^{k を}法とする剰余である。

a がn を法として非剰余である場合、少なくとも 1 つの素数n を法として^非剰余となる。

合成数を法として、2つの剰余の積は剰余となる。剰余と非剰余の積は、剰余、非剰余、またはゼロとなる。

たとえば、係数 6 の表から1、2、3、4、5 (剰余は太字)。
残基 3 と非残基 5 の積は残基 3 であり、残基 4 と非残基 2 の積は非残基 2 である。

また、2 つの非残基の積は、残基、非残基、またはゼロのいずれかになります。

たとえば、係数15の表から1、2、3、4、5、6、7、8、9、10、11、12、13、14 (剰余は太字) 。
非残基 2 と 8 の積は残基 1 であり、非残基 2 と 7 の積は非残基 14 である。

この現象は、抽象代数の語彙を用いると最もよく説明できます。法と互いに素な合同類は、乗法に関して環の単位群と呼ばれる群であり、平方数はその部分群です。異なる非剰余数は異なる剰余類に属する可能性があり、それらの積がどの剰余類に属するかを予測する単純な規則はありません。素数を法とすると、平方数の部分群と単一の剰余類のみがあります。 $(\mathbb {Z} /n\mathbb {Z} )$

例えば、15 を法として非剰余数 3 と 5 の積、非剰余数 5 と剰余数 9 の積、または 2 つの剰余数 9 と 10 がすべて 0 になるという事実は、合成数nに対して0 個の約数を持つ完全環での作業から得られます。 $(\mathbb {Z} /n\mathbb {Z} )$

このため、一部の著者^{[10]は、平方剰余}aは平方であるだけでなく、法nと互いに素でなければならないと定義に追加しています。（aがnと互いに素である場合、かつ^a2がnと互いに素である場合に限ります。）

物事は整理されますが、この記事では、留数が法と互いに素でなければならないと主張しているわけではありません。

表記

ガウス^[11]は、 $R$ と $Nを$ それぞれ残余性と非残余性を表すために使用した。

たとえば、

2 つの R 7

と

5 つの N 7

、または

1 つの R 8

と

3 つの N 8

。

この表記法は簡潔で、いくつかの目的には便利であるが、^[12]^[13]より便利な表記法はルジャンドル記号（2次特性とも呼ばれる）であり、これはすべての整数 $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}}

$数 \equiv 0 (mod p$ ) が特別扱いされる理由は2つあります。既に述べたように、多くの式や定理の記述が容易になるためです。もう1つの（関連する）理由は、二次指標が、 $p$ を法とする非零合同類の乗法群から乗法のもとでの複素数への準同型であることです。設定により、その定義域をすべての整数の乗法半群に拡張することができます。 ^[14] $({\tfrac {np}{p}})=0$

ガウスの記法に対するこの記法の利点の一つは、ルジャンドル記号が数式で使用できる関数であるという点である。^{[15]また、}3次、4次、さらに高次の剰余にも簡単に一般化できる。 ^[16]

$p$ の合成値に対するルジャンドル記号の一般化としてヤコビ記号がありますが、その性質はそれほど単純ではありません。m $が$ 合成値でヤコビ記号がN mの場合、 $a$ $N$ $m$ となり、 $R$ $m$ の場合 $、a$ $R$ $m$ かN mか分からない場合は、 $a$ $N$ $mとなります。例えば、$ $a$ N mかN m か分からない場合は、 $a N mか$ $R m か$ 分かりません。例えば、a N m か $R ...$ $({\tfrac {a}{m}})=-1,$ $({\tfrac {a}{m}})=1,$ $({\tfrac {a}{m}})=1$ $({\tfrac {2}{15}})=1$ $({\tfrac {4}{15}})=1$

平方剰余の分布

平方剰余はn を法としてかなりランダムなパターンで発生するように見え、これは音響や暗号化などのアプリケーションで利用されてきましたが、その分布には驚くべき規則性も見られます。

等差数列における素数に関するディリクレの定理、二次相互法、および中国剰余定理(CRT)を使用すると、任意のM > 0 に対して、数 1、2、...、Mがすべてpを法とする剰余となるような素数pが存在することが簡単にわかります。

例えば、p ≡ 1 (mod 8)、(mod 12)、(mod 5)、(mod 28) の場合、二次の相互法則により、2、3、5、7 はすべてpを法とする剰余となり、したがって 1 から 10 までのすべての数も p を法とする剰余となります。CRT によれば、これはp ≡ 1 (mod 840) と同じであり、ディリクレの定理によれば、この形の素数は無限個存在します。 2521 が最小で、実際は 1 ² ≡ 1、1046 ² ≡ 2、123 ² ≡ 3、2 ² ≡ 4、643 ^{2 ≡ 5、87}² ≡ 6、668 2 ≡ 7、429 2 ≡ 8、3 ² ≡ ^9、529 2 ^≡¹⁰ (mod 2521) となります。

ディリクレの公式

これらの規則性の最初のものは、ピーター・グスタフ・ルジューン・ディリクレによる1830年代の二元二次形式の類数の解析公式に関する研究に由来する。^[17]qを素数、sを複素変数とし、ディリクレL関数を次のように定義する。

L(s)=\sum _{n=1}^{\infty }\left({\frac {n}{q}}\right)n^{-s}.

ディリクレは、 q ≡ 3 (mod 4)の場合には、

L(1)=-{\frac {\pi }{\sqrt {q}}}\sum _{n=1}^{q-1}{\frac {n}{q}}\left({\frac {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 + 3 = 22、2 + 6 + 7 + 8 + 10 = 33、差は -11 です。

実際、q > 3の場合、差は常にqの奇数倍になります^。[18]対照的に、素数q ≡ 1 (mod 4) の場合、範囲 1、2、...、 q − 1の平方剰余の合計から非剰余の合計を引いた値はゼロになり、両方の合計が等しいことを意味します。^[19] ${\frac {q(q-1)}{4}}$

ディリクレはまた、素数q≡3（mod 4）に対して、

L(1)={\frac {\pi }{\left(2-\left({\frac {2}{q}}\right)\right)\!{\sqrt {q}}}}\sum _{n=1}^{\frac {q-1}{2}}\left({\frac {n}{q}}\right)>0.

これは、数 1、2、...、( q − 1)/2 の中には非剰余数よりも平方剰余数の方が多いことを意味します。

たとえば、11 を法として、6 未満の剰余は 4 つ (つまり 1、3、4、5) ありますが、非剰余は 1 つ (2) だけです。

これら2つの定理に関する興味深い事実は、既知の証明はすべて解析に依存しているということです。どちらの定理についても、これまで誰も単純または直接的な証明を発表したことはありません。^[20]

二次の相互性の法則

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の場合、次のようになります。

1つの	aがpを法とする平方剰余である場合、かつその場合に限り、	1つの	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 (mod 40)	−10	p ≡ 1、7、9、11、13、19、23、37 (mod 40)
11	p ≡ 1、5、7、9、19、25、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 のペアの数。より正確には、[ 21 ] ^[^22]ではp を奇数の素数とする。i 、 j = 0, 1 に対して、集合を定義する。

A_{ij}=\left\{k\in \{1,2,\dots ,p-2\}:\left({\frac {k}{p}}\right)=(-1)^{i}\land \left({\frac {k+1}{p}}\right)=(-1)^{j}\right\},

そして

\alpha _{ij}=|A_{ij}|.

つまり、

α ₀₀は残基が続く残基の数であり、

α ₀₁は非残基が続く残基の数であり、

α ₁₀は残基が続く非残基の数であり、

α ₁₁は、非残基の後に続く非残基の数です。

そしてp ≡ 1 (mod 4) の場合

\alpha _{00}={\frac {p-5}{4}},\;\alpha _{01}=\alpha _{10}=\alpha _{11}={\frac {p-1}{4}}

そしてp≡3（mod 4）の場合

\alpha _{01}={\frac {p+1}{4}},\;\alpha _{00}=\alpha _{10}=\alpha _{11}={\frac {p-3}{4}}.

例えば：（残基は太字）
モジュロ17
1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16
00 = {1,8,15} _,
A ₀₁ = {2,4,9,13},
10 = {3,7,12,14} _,
11 = {5,6,10,11} _。
モジュロ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},
10 = {3,8,10,15} _,
11 = {2,12,13,14} _。

ガウス（1828）^[23]は、p≡1（mod 4）ならばx4≡2（mod p ）^がp = a2 + 64 b2^の場合にのみ解けることを証明したときに^、この種のカウントを導入しました。

ポーリャとヴィノグラドフの不等式

の連続した値に対するの値は、コイン投げのような確率変数を模倣する。 [ ^24]具体的には、ポリアとヴィノグラドフは1918年に^[25] （独立に）任意の非主ディリクレ指標χ( n ) modulo qと任意の整数MとNに対して、 $({\tfrac {a}{p}})$

\left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log q\right),

ビッグO記法で設定

\chi (n)=\left({\frac {n}{q}}\right),

これは、長さNの任意の区間におけるqを法とする平方剰余の数が

{\frac {1}{2}}N+O({\sqrt {q}}\log q).

証明するのは簡単である^[26]

\left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\sqrt {q}}\log q.

実際、^[27]

\left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\frac {4}{\pi ^{2}}}{\sqrt {q}}\log q+0.41{\sqrt {q}}+0.61.

モンゴメリとヴォーンは1977年にこれを改良し、一般化リーマン予想が正しいならば

\left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log \log q\right).

この結果は大幅に改善することはできない。なぜなら、シュールは1918年に、

\max _{N}\left|\sum _{n=1}^{N}\left({\frac {n}{q}}\right)\right|>{\frac {1}{2\pi }}{\sqrt {q}}

そしてペイリーは1932年に

\max _{N}\left|\sum _{n=1}^{N}\left({\frac {d}{n}}\right)\right|>{\frac {1}{7}}{\sqrt {d}}\log \log d

d > 0が無限に存在します。

最小二次非剰余

pを法とする最小の平方剰余は明らかに 1 です。最小の平方非剰余n ( p )の大きさの問題はより微妙ですが、常に素数であり、7 は 71 で初めて現れます。

上記のポリア・ヴィノグラードフ不等式はO( √plogp )となる。

最良の無条件推定値は、任意のθ>1/4√eに対してn(p)≪pθであり、これはバージェスの特徴和の^推定値によって得られる。^[28]

一般化リーマン予想を仮定して、アンケニーはn ( p ) ≪ (log p ) ²を得た。^[29]

リンニックは、 n ( p )>Xε^となるようなXより小さいpの数はεに依存する定数で制限されることを示した。^[28]

奇数の素数pに対するpを法とする最小の二次非剰余数は次のとおりです。

2、2、3、2、2、3、2、5、2、3、2、...（OEISの配列A053760）

二次過剰

pを奇素数とする。平方剰余 E ( p )は、範囲(0, p /2)の平方剰余の数から範囲( p /2, p )の数を引いたものである（OEISの配列A178153 ）。pが1 mod 4と合同な場合、-1は平方剰余であり、剰余はr ↔ p − rに関して対称であるため、剰余は0となる。pが3 mod 4と合同な場合、剰余Eは常に正となる。^[30]

平方根を求める複雑さ

つまり、数aと法nが与えられたとき、それはどれほど難しいか？

x ² ≡ a (mod n )を解くxが存在するかどうかを調べる
存在すると仮定して、それを計算しますか?

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

一般に、合成係数n が異なる素数の累乗の積として表され、最初の素数を法とするn _{1 個の根、}_{2番目の素数を法とする}n 2 個の根、… がある場合、 nを法とするn ₁n ₂ … 個の根が存在します。

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

例えば：
x ² ≡ 6 (mod 15) を解きます。
x ² ≡ 6 (mod 3) には 0 という 1 つの解があります。x ² ≡ 6 (mod 5) には 1 と 4 という 2 つの解があります。
そして、15 を法とする解は 6 と 9 の 2 つあります。
x ² ≡ 4 (mod 15) を解きます。
x ² ≡ 4 (mod 3) には 1 と 2 の 2 つの解があります。x ² ≡ 4 (mod 5) には 2 と 3 の 2 つの解があります。
15 を法とする解は 2、7、8、13 の 4 つあります。
x ² ≡ 7 (mod 15) を解きます。
x ² ≡ 7 (mod 3) には 1 と 2 の 2 つの解がありますが、x ² ≡ 7 (mod 5) には解はありません。
そして 15 を法とする解は存在しません。

プライムまたはプライムべき乗係数

まず、法nが素数であれば、ルジャンドル記号はユークリッドの互除法^[32]の変形、またはオイラーの判定法を用いて素早く計算できる。それが-1であれば解は存在しない。次に、n≡3(mod 4)と仮定すると、ラグランジュは解が次のように与えられることを発見した。 $\left({\frac {a}{n}}\right)$ $\left({\frac {a}{n}}\right)=1$

x\equiv \pm \;a^{(n+1)/4}{\pmod {n}},

そしてルジャンドルはn≡5（mod 8）の場合には同様の解^{[33]を発見した。}

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) の場合、公式は知られていない。Tonelli ^[34] (1891年) とCipolla ^[35]は、すべての素数を法として動作する効率的なアルゴリズムを発見した。どちらのアルゴリズムも、 n を法とする二次の非剰余を求めることが必要であり、これを実行するための効率的な決定論的アルゴリズムは知られていない。しかし、1 からnまでの数の半分は非剰余であるため、数xをランダムに選び、非剰余が見つかるまでルジャンドル記号を計算すれば、すぐに非剰余が見つかるだろう。このアルゴリズムのわずかな変形がTonelli–Shanks アルゴリズムである。 $\left({\frac {x}{n}}\right)$

nが素数n = p ^eのべき乗である場合、 pを法とする解が求められ、ヘンゼルの補題またはガウスのアルゴリズムを使用してnを法とする解に「持ち上げる」ことができる。 ^[8]

複合弾性係数

係数nが素因数分解されている場合、その解決法は上で説明しました。

nが 2 を法として 4 とクロネッカー記号と合同でない場合、解は存在しません。nが2 を法として 4 と合同でない場合、またn が2 を法として 4 と合同でない場合、あるいはn が2 を法として 4 と合同でない場合、解が存在する場合と存在しない場合があります。 $\left({\tfrac {a}{n}}\right)=-1$ $\left({\tfrac {a}{n/2}}\right)=-1$ $\left({\tfrac {a}{n}}\right)=1$ $\left({\tfrac {a}{n/2}}\right)=1$

nの完全な因数分解が不明で、かつn が4 を法として 2 と合同でない場合、またはn が4 を法として 2 と合同で、かつである場合、問題はnの整数因数分解と同等であることが分かっています(つまり、どちらかの問題に対する効率的な解法を使用して、もう一方の問題を効率的に解決できます)。 $\left({\tfrac {a}{n}}\right)=1$ $\left({\tfrac {a}{n/2}}\right)=1$

上の議論は、 nの因数を知ることで効率的に平方根を求めることができることを示しています。合成数を法とする平方根を求める効率的なアルゴリズムがあるとしましょう。「平方の合同性」の記事では、 $x 2 \equiv y 2 (mod n)$ かつ $x \neq \pm y$ となる2つの数xとyを見つければ、 nを効率的に因数分解できると説明しています。乱数を生成し、それをnを法として二乗し、効率的な平方根アルゴリズムで根を求めます。最初に二乗した数（またはnを法とするその負の数）と等しくない数を返すまで繰り返し、その後、「平方の合同性」で説明されているアルゴリズムに従います。因数分解アルゴリズムの効率は、根を求めるアルゴリズムの正確な特性（例えば、すべての根を返すのか、最小の根だけを返すのか、ランダムに返すのかなど）に依存しますが、効率的です。^[36]

a が nを法とする平方剰余か非剰余か（ a R n または a N n と表記 $）の判定$ は $、素数 n$ の場合、ルジャンドル記号を計算することで効率的に行うことができます。しかし、合成数nの場合、これは平方剰余問題となります。これは因数分解ほど難しいとは知られていませんが、かなり難しいと想定されています。

一方、ある与えられた限界cより小さいxの解が存在するかどうかを知りたい場合、この問題はNP完全です。^[37]しかし、これはcをパラメータとする固定パラメータ問題です。

一般に、aが合成数nを法とした平方剰余であるかどうかを判断するには、次の定理を用いることができる。^[38]

$n > 1$ 、 $gcd(a, n) = 1$ とします。すると、 $x 2 \equiv a (mod n)$ が解けるのは、以下の場合のみです。

nのすべての奇数素因数pを表すルジャンドル記号。 $\left({\tfrac {a}{p}}\right)=1$
nが 4 で割り切れるが 8 で割り切れない場合は $a$ $\equiv 1 (mod 4) 、$ nが 8 で割り切れる場合 $はa \equiv 1 (mod 8) 。$

注：この定理は、本質的にnの因数分解が既知であることを前提としています。また、 $gcd(a, n) = mの場合には、合同式は$ $a / m \equiv x 2 / m (mod n / m)$ と簡約できますが、この場合、平方剰余の問題は問題から除外されます（mが平方数でない限り）。

平方剰余の数

nを法とした平方剰余の数のリスト（n = 1、2、3 ...）は次のようになります。

1、2、2、2、3、4、4、3、4、6、6、4、7、8、6、...（OEISのシーケンスA000224）

nを法とする平方数を数える公式はスタングルによって与えられている。^[39]

平方剰余の応用

音響

音響拡散装置は原始根や平方剰余などの数論的概念に基づいている。 ^[40]

グラフ理論

ペイリーグラフは、素数p ≡ 1 (mod 4)ごとに 1 つずつ存在する密な無向グラフで、無限の会議グラフ族を形成し、無限の対称会議行列族を生成します。

Paley ダイグラフは、各p ≡ 3 (mod 4)ごとに 1 つずつある Paley グラフの有向類似物であり、反対称の会議行列を生成します。

これらのグラフの構築には、平方剰余が使用されます。

暗号化

大きな合成数nを法とする数の平方根を求めることが因数分解（一般的に難しい問題と考えられている）と等価であるという事実は、ラビン署名や忘却転送などの暗号方式の構築に利用されてきた。二次剰余問題は、ゴールドワッサー・ミカリ暗号の基礎となっている。

離散対数も同様の問題であり、暗号化にも使用されます。

素数判定

オイラーの判定基準は、ルジャンドル記号 ( a | p )の式であり、pは素数です。pが合成数の場合、式は ( a | p ) を正しく計算する場合としない場合があります。与えられた数nが素数か合成数かを判断するソロベイ–シュトラッセンの素数判定では、ランダムに a を選び、ユークリッドの互除法 [41] の修正版とオイラーの判定基準 [42] を使用して ( a | n ) を計算します。結果が^一致し^ない場合はnは合成数です。結果が一致する場合は、n は合成数か素数かのどちらかです。合成数nの場合、範囲 2、3、...、 n − 1 にあるaの少なくとも 1/2 で「 nは合成数」が返されますが、素数nの場合はどれも返されません。 aのさまざまな値を使用してもnが合成数であることが証明されない場合は、「可能性のある素数」と呼ばれます。

ミラー・ラビン素数判定も同じ原理に基づいています。決定論的なバージョンもありますが、その証明は一般化リーマン予想に依存します。この判定の出力は「nは間違いなく合成数である」または「n が素数であるか、一般化リーマン予想が偽である」のいずれかです。もし後者の出力が合成数nに対して起こった場合、一般化リーマン予想は偽となり、これは数学の多くの分野に影響を与えるでしょう。

整数因数分解

ガウスは『算術論』第6章^[43]で、平方剰余と平方相互法則を使った2つの因数分解アルゴリズムについて論じている。

いくつかの現代的な因数分解アルゴリズム（ディクソンのアルゴリズム、連分数法、二次ふるい法、数体ふるい法など）は、因数分解となる平方数の合同性を見つけるために、（因数分解される数を法とする）小さな二次剰余を生成しようとします。数体ふるい法は、知られている中で最も高速な汎用因数分解アルゴリズムです。

平方剰余表

次の表（OEISのシーケンスA096008）は、1から75を法とする平方剰余を列挙しています（赤い数字はnと互いに素でないことを意味します）。（ nと互いに素な平方剰余については（OEISのシーケンスA096103）、0以外の平方剰余については（OEISのシーケンス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

二次剰余（A048152、A343720も参照）
×	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
× ²	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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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
モッド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

参照

注記

^ レメマイヤー、第1章
^ レマーマイヤー、6～8ページ、16ページ以降
^ ガウス、DA、第94条
^ ab Gauss, DA, 96条
^ ab Gauss, DA, 98条
^ ガウス、DA、第111条
^ ガウス、DA、第103条
^ ab Gauss, DA, 記事101
^ ガウス、DA、第102条
^ 例えば、アイルランド＆ローゼン 1990、p. 50
^ ガウス、DA、第131条
^ 例えばハーディとライトはそれを使用している
^ Gauss, DA、第230条以降。
^ この定義域の拡張はL関数を定義するために必要です。
^ 例については、ルジャンドル記号#ルジャンドル記号の性質を参照
^ レマーマイヤー、111～112ページ
^ Davenport 2000, pp. 8–9, 43–51. これらは古典的な結果である。
^ Davenport 2000, pp. 49–51, （ ヤコビ予想、ディリクレ証明）
^ ハドソン、リチャード・H. (1976)、「数論における古典定理の一般化」、計算数学、30 (135): 649– 656、doi :10.2307/2005336、MR 0404112
^ ダベンポート 2000、9ページ
^ レマーマイヤー、29ページ例1.22; 26～27ページ、第10章を参照
^ クランドール＆ポメランス、例2.38、pp 106–108
^ ガウス、理論 der biquadratischen Reste、Erste Abhandlung (『 Untersuchungen über hohere Arithmetik』の 511 ～ 533 ページ)
^ Crandall & Pomerance, ex 2.38, pp 106–108 では、類似点と相違点について議論されています。例えば、 n枚のコインを投げると、 n / 2回表が出た後、その回数だけ裏が出る可能性はありますが（可能性は低いですが）、VP不等式により、剰余についてはそのような可能性は排除されます。
^ Davenport 2000, pp. 135–137, (P–V の証明 (実際、big-O は 2 に置き換えることができる); Paley、Montgomery、Schur のジャーナル参考文献)
^ Planet Math: ポリア・ヴィノグラドフ不等式の証明（外部リンク）。証明は1ページの長さで、ガウス和に関する基本的な事実のみを必要とする。
^ Pomerance & Crandall, ex 2.38 pp.106–108. T. Cochrane, "On a trigonometric inequality of Vinogradov", J. Number Theory , 27:9–16, 1987の結果
^ ab Friedlander, John B. ; Iwaniec, Henryk (2010). Opera De Cribro .アメリカ数学会. p. 156. ISBN 978-0-8218-4970-5. Zbl 1226.11099。
^ モンゴメリー、ヒュー・L. (1994).解析的数論と調和解析の接点に関する10の講義.アメリカ数学会. p. 176. ISBN 0-8218-0737-4. Zbl 0814.11001。
^ ベイトマン, ポール・T. ; ダイアモンド, ハロルド・G. (2004).解析的数論. ワールド・サイエンティフィック. p. 250. ISBN 981-256-080-7. Zbl 1074.11001。
^ Bach & Shallit 1996、p. 104 ff; O(log ² m ) ステップが必要です。ここで、m はnを割り切る素数の数です。
^ Bach & Shallit 1996, p. 113; 計算にはO(log a log n )ステップが必要 $\left({\frac {a}{n}}\right)$
^ レマーマイヤー、29ページ
^ Bach & Shallit 1996、p. 156 ff; このアルゴリズムには O(log ⁴n ) ステップが必要です。
^ Bach & Shallit 1996、p. 156 ff; このアルゴリズムは O(log ³ n ) ステップを必要とし、非決定論的でもある。
^ クランドール＆ポメランス、例6.5＆6.6、p.273
^ マンダース＆アドルマン 1978
^ バートン、デイヴィッド (2007). 『初等数論』ニューヨーク: マグロウヒル. p. 195.
^ Stangl, Walter D. (1996年10月), "Counting Squares in ℤn" (PDF) , Mathematics Magazine , 69 (4): 285– 289, doi :10.2307/2690536, JSTOR 2690536, 2015年12月24日時点のオリジナル(PDF)からアーカイブ, 2015年3月24日取得
^ Walker, R. 「モジュラー音響拡散要素の設計と応用」（PDF） BBC調査部. 2016年10月25日閲覧。
^ バッハ＆シャリット 1996年、113ページ
^ Bach & Shallit 1996, pp. 109–110; オイラーの基準はO(log ³ n )ステップを必要とする
^ ガウス、DA、芸術329–334

参考文献

『算術論』は、ガウスのキケロ語ラテン語から英語とドイツ語に翻訳されました。ドイツ語版には、彼の数論に関するすべての論文、すなわち、二次の相互法則のすべての証明、ガウス和の符号の決定、双二次の相互法則の研究、そして未発表のノートが収録されています。

ガウス、カール・フリードリヒ（1986年）、Disquisitiones Arithemeticae、クラーク、アーサー・A.訳（第2版訂正）、ニューヨーク：シュプリンガー、ISBN 0-387-96254-9
Gauss, Carl Friedrich (1965)、Untersuchungen über hohere Arithmetik [ Disquisitiones Arithemeteticae & other places on Number Theory ]、Maser, H. 訳 (第 2 版)、ニューヨーク: チェルシー、ISBN 0-8284-0191-8
バッハ、エリック、シャリット、ジェフリー（1996年）、効率的アルゴリズム、アルゴリズム的数論、第1巻、ケンブリッジ：MIT出版、ISBN 0-262-02405-5
クランドール、リチャード；ポメランス、カール（2001）『素数：計算的視点』ニューヨーク：シュプリンガー、ISBN 0-387-94777-9
ダヴェンポート、ハロルド（2000年）、乗法数論（第3版）、ニューヨーク：シュプリンガー、ISBN 0-387-95097-4
ゲイリー、マイケル・R. ;ジョンソン、デイビッド・S. (1979)、「コンピュータとイントラクタビリティ：NP完全性理論へのガイド」、WHフリーマン、ISBN 0-7167-1045-5A7.1: AN1、249ページ。
ハーディ、GH ;ライト、EM（1980）『数論入門』（第5版）、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-853171-5
アイルランド、ケネス、ローゼン、マイケル（1990年）、現代数論への古典的入門（第2版）、ニューヨーク：シュプリンガー、ISBN 0-387-97329-X
Lemmermeyer、Franz (2000)、相反性の法則: オイラーからエイゼンシュタインまで、ベルリン: Springer、ISBN 3-540-66957-4
Manders, Kenneth L.; Adleman, Leonard (1978)、「NP-二項二次方程式の完全決定問題」、Journal of Computer and System Sciences、16 (2): 168– 184、doi : 10.1016/0022-0000(78)90044-2。

外部リンク

ワイスタイン、エリック・W.「二次剰余」。MathWorld。
PlanetMathにおける Pólya–Vinogradov 不等式の証明。

[1] レメマイヤー、第1章

[2] レマーマイヤー、6～8ページ、16ページ以降

[3] ガウス、DA、第94条

[Gauss,_DA,_art._96-4] Gauss, DA, 96条

[Gauss,_DA,_art._98-5] Gauss, DA, 98条

[6] ガウス、DA、第111条

[7] ガウス、DA、第103条

[Gauss,_DA,_art._101-8] Gauss, DA, 記事101

[9] ガウス、DA、第102条

[10] 例えば、アイルランド＆ローゼン 1990、p. 50

[11] ガウス、DA、第131条

[12] 例えばハーディとライトはそれを使用している

[13] Gauss, DA、第230条以降。

[14] この定義域の拡張はL関数を定義するために必要です。

[15] 例については、ルジャンドル記号#ルジャンドル記号の性質を参照

[16] レマーマイヤー、111～112ページ

[17] Davenport 2000, pp. 8–9, 43–51. これらは古典的な結果である。

[18] ^ Davenport 2000, pp. 49–51, （ ヤコビ予想、ディリクレ証明）

[19] ハドソン、リチャード・H. (1976)、「数論における古典定理の一般化」、計算数学、30 (135): 649– 656、doi :10.2307/2005336、MR 0404112

[20] ダベンポート 2000、9ページ

[21] レマーマイヤー、29ページ例1.22; 26～27ページ、第10章を参照

[22] クランドール＆ポメランス、例2.38、pp 106–108

[23] ガウス、理論 der biquadratischen Reste、Erste Abhandlung (『 Untersuchungen über hohere Arithmetik』の 511 ～ 533 ページ)

[24] Crandall & Pomerance, ex 2.38, pp 106–108 では、類似点と相違点について議論されています。例えば、 n枚のコインを投げると、 n / 2回表が出た後、その回数だけ裏が出る可能性はありますが（可能性は低いですが）、VP不等式により、剰余についてはそのような可能性は排除されます。

[25] Davenport 2000, pp. 135–137, (P–V の証明 (実際、big-O は 2 に置き換えることができる); Paley、Montgomery、Schur のジャーナル参考文献)

[26] Planet Math: ポリア・ヴィノグラドフ不等式の証明（外部リンク）。証明は1ページの長さで、ガウス和に関する基本的な事実のみを必要とする。

[27] Pomerance & Crandall, ex 2.38 pp.106–108. T. Cochrane, "On a trigonometric inequality of Vinogradov", J. Number Theory , 27:9–16, 1987の結果

[FI156-28] Friedlander, John B. ; Iwaniec, Henryk (2010). Opera De Cribro .アメリカ数学会. p. 156. ISBN 978-0-8218-4970-5. Zbl 1226.11099。

[29] モンゴメリー、ヒュー・L. (1994).解析的数論と調和解析の接点に関する10の講義.アメリカ数学会. p. 176. ISBN 0-8218-0737-4. Zbl 0814.11001。

[30] ベイトマン, ポール・T. ; ダイアモンド, ハロルド・G. (2004).解析的数論. ワールド・サイエンティフィック. p. 250. ISBN 981-256-080-7. Zbl 1074.11001。

[31] Bach & Shallit 1996、p. 104 ff; O(log ² m ) ステップが必要です。ここで、m はnを割り切る素数の数です。

[32] Bach & Shallit 1996, p. 113; 計算にはO(log a log n )ステップが必要 $\left({\frac {a}{n}}\right)$

[33] レマーマイヤー、29ページ

[34] Bach & Shallit 1996、p. 156 ff; このアルゴリズムには O(log ⁴n ) ステップが必要です。

[35] Bach & Shallit 1996、p. 156 ff; このアルゴリズムは O(log ³ n ) ステップを必要とし、非決定論的でもある。

[36] クランドール＆ポメランス、例6.5＆6.6、p.273

[37] マンダース＆アドルマン 1978

[38] バートン、デイヴィッド (2007). 『初等数論』ニューヨーク: マグロウヒル. p. 195.

[39] Stangl, Walter D. (1996年10月), "Counting Squares in ℤn" (PDF) , Mathematics Magazine , 69 (4): 285– 289, doi :10.2307/2690536, JSTOR 2690536, 2015年12月24日時点のオリジナル(PDF)からアーカイブ, 2015年3月24日取得

[40] Walker, R. 「モジュラー音響拡散要素の設計と応用」（PDF） BBC調査部. 2016年10月25日閲覧。

[41] バッハ＆シャリット 1996年、113ページ

[42] Bach & Shallit 1996, pp. 109–110; オイラーの基準はO(log ³ n )ステップを必要とする

[43] ガウス、DA、芸術329–334

v t e 数論
フィールド	代数的数論（類体論、非可換類体論、岩澤理論、岩澤・テイト理論、クンマー理論）解析的数論（L関数の解析理論、確率的数論、ふるい理論）幾何数論計算数論超越数論ディオファントス幾何学（アラケロフ理論、ホッジ・アラケロフ理論）算術的組合せ論（加法数論）数論幾何学（遠アーベル幾何学、p進ホッジ理論）算術位相幾何学算術力学
重要な概念	数字 0 自然数団結素数合成数有理数無理数代数的数超越数 p進数（p進解析）算術モジュラー演算中国剰余定理算術関数
高度な概念	二次形式モジュラーフォーム L関数ディオファントス方程式ディオファントス近似非合理性の尺度単純な連分数
カテゴリトピックのリストレクリエーショントピックのリストウィキブックウィキバーシティ

v t e 多項式と多項式関数と多項式方程式
学位別	ゼロ多項式（次数未定義または−1または−∞）定数関数 (0) 線形関数（1）線形方程式二次関数 (2) 二次方程式三次関数 (3) 三次方程式四次関数 (4) 四次方程式五次関数 (5) 六次方程式（6）敗血症方程式（7）
プロパティ別	一変量二変量多変量単項式二項式三項式還元不可能スクエアフリー均質な準均質
ツールとアルゴリズム	因数分解最大公約数分割ホーナーの評価法多項式恒等式検定結果判別式グレブナー基底

v t e 幾何学
歴史タイムライン幾何学トピックのリスト幾何学の基礎幾何学のアウトライン
ユークリッド幾何学	凸型離散平面幾何学固体アフィン三角法球状一般化された
基本概念（ユークリッド）	ポイントライン飛行機空間距離角度平行垂直三角形丸ポリゴン合同類似性ユークリッドの原論ユークリッド空間座標系デカルト座標ポーラー寸法 2D 3D
非ユークリッド幾何学	非ユークリッド空間楕円形双曲線球状
方法または構造に基づく	代数的算術ディオファントス差動リーマンシンプレクティック絶対解析幾何学複雑な計算コンフォーマル離散フラクタル幾何群論情報非アルキメデス的非可換射影的スペクトルサーストンメトリック幾何学幾何学的測度理論幾何学的解析
トポロジー	トポロジー一般的な集合論的連続体代数的非可換差動幾何学的低次元組み合わせ位相力学結び目理論シンプレクティック位相幾何学
リスト	幾何学トピックのリスト組み合わせ計算幾何学のトピック微分幾何学のトピック初等幾何学の公式リーマン幾何学の公式幾何学のトピック結び目理論のトピック数値計算幾何学のトピックポリゴン形状トポロジー一般的な位相幾何学幾何学のアウトライン
用語集	代数幾何学代数的位相幾何学算術とディオファントス幾何学古典代数幾何学微分幾何学と位相幾何学トポロジー数学記号リーマン幾何学と計量幾何学比喩的な名前を持つ図形シンプレクティック幾何学
その他	有限幾何学入射幾何学整列した幾何学
関連している	幾何代数群論環理論場の理論多様体上の微積分ベクトル計算フラクタル解析調和解析数の幾何学格子理論楕円曲線統計的形状分析空間統計幾何学的データ分析幾何学の基礎公理体系構成幾何学遠アーベル幾何学
カテゴリー: 幾何学三角法トポロジーカテゴリ:幾何学の歴史

v t e 代数
概要歴史
エリア	抽象代数代数幾何学代数多様体スキーム代数的数論カテゴリー理論可換代数初等代数学ホモロジー代数 K理論線形代数多重線形代数非可換代数秩序理論表現論普遍代数
基本概念	代数式方程式（一次方程式、二次方程式）関数（多項式関数）不等式（線形不等式）演算（加算、乗算）関係（同値関係）変数
代数構造	分野（理論）グループ（理論）モジュール（理論）リング（理論）ベクトル空間（ベクトル）
線形代数と多重線形代数	基礎行列式固有値と固有ベクトル内積空間（ドット積）ヒルベルト空間線形写像（行列）線形部分空間（アフィン空間）ノルム（ユークリッドノルム）直交性（直交補集合）ランクトレース
代数写像	準同型（群準同型、環準同型）同型性自己準同型性自己同型性カーネル（代数）
代数的構成	合成代数外積代数自由オブジェクト(自由グループ、...) 幾何代数（マルチベクトル）多項式環（多項式）商オブジェクト(商グループ、...) 対称代数テンソル代数
トピックリスト	代数構造
用語集	場の理論線形代数秩序理論環理論
カテゴリ