二次剰余

オイラーの基準によれば、奇素数pを法として、( p + 1)/2 個の剰余（0 を含む）と ( p − 1)/2 個の非剰余が存在する。この場合、0 を特殊なケースとみなし、体の非零要素の乗法群内で計算するのが一般的である。${\displaystyle (\mathbb {Z} /p\mathbb {Z} )}$つまり、pを法とするゼロ以外のすべての合同類には乗法逆元が存在する。これは合成法では当てはまらない。^{[ 4 ]}

この慣例に従うと、剰余の乗法逆元は剰余であり、非剰余の逆元は非剰余である。^{[ 5 ]}

この慣例に従うと、奇素数を法とした場合、剰余と非剰余の数は等しくなります。^{[ 4 ]}

素数を法として、2つの非剰余の積は剰余であり、非剰余と（ゼロでない）剰余の積は非剰余である。^{[ 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。

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

奇素数pと互いに素な数aは、 pの任意のべき乗を法とする剰余数であるのは、a がpを法とする剰余数である場合に限る。^{[ 8 ]}

絶対値がp ^{n の}場合、

次にp ^k a

k ≥ nの場合、p ^{n を}法とする剰余となる。

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

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

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

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

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

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

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

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

a がn を法とする非剰余であるならば、a はn を割り切る少なくとも 1 つの素数のべき乗p ^{k を}法とする非剰余である。

合成数を法とした場合、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である。

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

例えば、15を法として、非残基3と5の積、あるいは非残基5と残基9の積、あるいは2つの残基9と10の積がすべてゼロになるという事実は、完全な環で作業することによって得られる。${\displaystyle (\mathbb {Z} /n\mathbb {Z} )}$合成数nに対して零約数を持つ。

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

整理しやすくなるとはいえ、この記事では剰余が法と互いに素でなければならないとは主張していません。

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

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

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

${\displaystyle 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の範囲の二次剰余の合計から非剰余の合計を引いた値はゼロであり、これは両方の合計が等しいことを意味します。$\displaystyle {\frac {q(q-1)}{4}}}$[ ^{19 ]​}

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

${\displaystyle 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 を法とする2次剰余である) は、( q がpを法とする2次剰余である) のときのみ成り立ち、( pとqの少なくとも一方が4 を法とする 1 に合同である) のときのみ成り立ちます。

つまり：

$\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}}$

どこ${\displaystyle \left({\frac {p}{q}}\right)}$はルジャンドル記号です。

したがって、数aとaを割り切らない奇素数pについては、次のようになります。

素数pを法として、 n ∈ pかつ n + 1 ∈ pとなるペアn , n + 1 、またはn ∈ pかつn + 1 ∈ pとなるペアの数などはほぼ等しい。より正確には、^{[ 21 ] [ 22 ]} p を奇素数とする。i, j = 0, 1 に対して、集合を定義する。

${\displaystyle 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\},}$

そして

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

つまり、

α ₀₀は、残基が続く残基の数です。

α ₀₁は、非残基が続く残基の数です。

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

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

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

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

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

${\displaystyle \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​​​​​​​​​​​​​​

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

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

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

A ₁₁ = {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},

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

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

ガウス（1828）^{[ 23 ]}は、 p ≡ 1 (mod 4) ならばx ⁴ ≡ 2 (mod p ) はp  = a ² + 64 b ²の場合に限り解けることを証明したときに、この種の計数法を導入しました。    

値${\displaystyle ({\tfrac {a}{p}})}$連続する値については、コイン投げのようなランダム変数を模倣します。^{[ 24 ]}具体的には、PólyaとVinogradovは1918年に（独立に）任意の非主ディリクレ指標χ( n ) mod qと任意の整数MとNに対して、次のことを証明しました。^{[ 25 ]}

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

ビッグオー記法で。

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

これは、任意の長さNの区間におけるqを法とする 2 乗剰余の数が次のようになることを示している。

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

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

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

実際、^{[ 27 ]}

${\displaystyle \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年にこれを改良し、一般化されたリーマン予想が真であれば、

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

この結果は大幅に改善できない。なぜなら、シュールは1918年に次のことを証明していたからである。

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

そしてペイリーは1932年に、

${\displaystyle \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( √ p log p )を与える。

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

一般化リーマン予想を仮定すると、アンケニーはn ( p ) ≪ (log p ) ^{2 を}得た。^{[ 29 ]}

Linnikは、 n ( p ) > Xε^となるようなXより小さいpの数は、εに依存する定数によって制限されることを示した。^{[ 28 ]}

奇素数pに対する最小の二次非剰余 mod 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に関して対称であるため、剰余はゼロとなる。pが3 mod 4 に合同な場合、剰余Eは常に正となる。^{[ 30 ]}

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

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

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

${\displaystyle 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) の場合、既知の公式はありません。トネリ^{[ 34 ]} (1891 年) とチポラ^{[ 35 ]}は、すべての素数法に対して機能する効率的なアルゴリズムを発見しました。どちらのアルゴリズムも、 n を 法とする二次非剰余を見つける必要がありますが、これを行うための効率的な決定論的アルゴリズムは知られていません。しかし、1 からnまでの数の半分は非剰余であるため、ランダムに数xを選択し、ルジャンドル記号を計算することで、${\displaystyle \left({\frac {x}{n}}\right)}$非残基が見つかるまで繰り返すと、すぐに非残基が生成されます。このアルゴリズムのわずかな変形として、トネリ・シャンクスアルゴリズムがあります。

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

法nが素数のべき乗に因数分解されている場合、その解は上記で説明したとおりである。

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

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

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

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

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

一般に、a が合成数nを法とする二次剰余であるかどうかを判断するには、次の定理を使用できます。^{[ 38 ]}

n > 1とし、gcd( a , n ) = 1 とする。このとき、x ² ≡ a (mod n )が解けるのは、次の条件を満たす場合に限る。

• ルジャンドル記号${\displaystyle \left({\tfrac {a}{p}}\right)=1}$nのすべての奇素因数pについて。
• 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が平方数でない限り）。

• ${\displaystyle s(2^{n})={\frac {2^{n-1}+4}{3}}}$たとえ${\displaystyle n}$
• ${\displaystyle s(2^{n})={\frac {2^{n-1}+5}{3}}}$奇数の場合${\displaystyle n}$

• ${\displaystyle s(p)={\frac {p+1}{2}}}$
• ${\displaystyle s(p^{2})={\frac {p^{2}-p+2}{2}}}$
• ${\displaystyle s(p^{n})={\frac {p^{n+1}+p+2}{2(p+1)}}}$たとえ${\displaystyle n\geq 3}$
• ${\displaystyle s(p^{n})={\frac {p^{n+1}+2p+1}{2(p+1)}}}$奇数の場合${\displaystyle n\geq 3}$

音響拡散器は、原始根や二次剰余などの数論的概念に基づいている。^{[ 40 ]}

ペイリーグラフは、各素数p ≡ 1 (mod 4)に対して 1 つずつ存在する密な無向グラフであり、無限のカンファレンスグラフの族を形成し、無限の対称カンファレンス行列の族を生み出します。

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

これらのグラフの構築には、二次剰余が用いられる。

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

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

オイラーの判定法は、 p が素数である場合のルジャンドル記号 ( a | p )の公式です。p が合成数の場合、この公式は ( a | p ) を正しく計算する場合としない場合があります。与えられた数nが素数か合成数かを判定するSolovay–Strassen 素数判定法は、ランダムにaを選択し、ユークリッドのアルゴリズム^{[ 41 ]}の修正版とオイラーの判定法 [ 42 ] を使用して ( a | n ) を計算します。^{結果が一致}しない場合は、nは合成数です。結果が一致する場合は、n は合成数か素数かのどちらかです。合成数nの場合、2, 3, ..., n − 1の範囲の aの値の少なくとも 1/2 が「 nは合成数です」を返します。素数nの場合は、そのような値は返されません。多くの異なるaの値を使用してもnが合成数であることが証明されない場合、n は「可能性のある素数」と呼ばれます。

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

『算術研究』第6節^{[ 43 ]}において、ガウスは2次剰余と2次相互法則を用いた2つの因数分解アルゴリズムについて論じている。

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