平方剰余
素数 p を法として、n R p かつ n + 1 R p、または n N p と n + 1 R p 等となるペア n, n + 1 の数はほぼ同じである。より正確には、p を奇素数として、i, j = 0, 1 によって以下の集合を定義し
A i j = { k ∈ { 1 , 2 , ⋯ , p − 2 } : ( k p ) = ( − 1 ) i ∧ ( k + 1 p ) = ( − 1 ) j } , {\displaystyle 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 を定義する。
α i j = | A i j | . {\displaystyle \alpha _{ij}=|A_{ij}|.}
つまり、以下のようになる。
α00 は剰余に続く剰余の数
α01 は非剰余に続く剰余の数
α10 は剰余に続く非剰余の数
α11 は非剰余に続く非剰余の数
すると、p ≡ 1 (mod4) の場合、
α 00 = p − 5 4 , α 01 = α 10 = α 11 = p − 1 4 {\displaystyle \alpha _{00}={\frac {p-5}{4}},\;\alpha _{01}=\alpha _{10}=\alpha _{11}={\frac {p-1}{4}}}
しかし、素数 n ≡ 1 (mod 8) に対しては、既知の公式が存在しない。トネリ(英語版)(1891年)とチポラ(英語版)は、それぞれすべての素数の法に使える効率的なアルゴリズムを発見した。どちらのアルゴリズムも n を法とする平方非剰余を見つける必要があり、そのための効率的な既知の決定論的アルゴリズムは存在しない。しかし、1 から n の間の数の半分は非剰余であるため、非剰余が見つかるまで、ランダムに数 x を選んでルジャンドル記号 ( x n ) {\displaystyle \left({\frac {x}{n}}\right)} を計算すると、すぐに非剰余が求まる。このアルゴリズムをわずかに変形したものがトネリ・シャンクスのアルゴリズム(英語版)である。
法 n が素数のべき乗 n = p である場合、解は p を法として見つかるので、ヘンゼルの補題またはガウスのアルゴリズムを使用して n を法とする解に「持ち上げて」得られる。