平方剰余
次の表(オンライン整数列大辞典の数列 A096008)は、法 1から75までの平方剰余のリストである(赤字は、n と互いに素ではないことを意味する)。(n と互いに素な平方剰余については A096103 を、非ゼロな平方剰余については A046071 を参照せよ。)
法 n が素数のべき乗に素因数分解される場合、解は上記の通りである。
n ≢ 2 ( mod 4 ) {\displaystyle n\not \equiv 2{\pmod {4}}} でクロネッカー記号(英語版)(Kronecker symbol)が ( a n ) = − 1 {\displaystyle \left({\tfrac {a}{n}}\right)=-1} であれば、解は存在しない。n ≡ 2 (mod 4) で ( a n / 2 ) = − 1 {\displaystyle \left({\tfrac {a}{n/2}}\right)=-1} である場合も、解は存在しない。「 n ≢ 2 ( mod 4 ) {\displaystyle n\not \equiv 2{\pmod {4}}} かつ ( a n ) = 1 {\displaystyle \left({\tfrac {a}{n}}\right)=1} 」または「 n ≡ 2 (mod 4) かつ ( a n / 2 ) = 1 {\displaystyle \left({\tfrac {a}{n/2}}\right)=1} 」 ならば、解が存在する場合としない場合がある。
Disquisitiones Arithmeticae§VIで、ガウスは平方剰余と平方剰余の相互法則を使用する2つの素因数分解アルゴリズムについて説明している。
最新の素因数分解アルゴリズムのいくつか(ディクソンのアルゴリズム(英語版) (Dixon's algorithm)、連分数法(英語版) (continued fraction method)、二次ふるい法(英語版) (quadratic sieve)、数体ふるい(英語版) (number field sieve) など)は、素因数分解につながる平方合同(英語版)を探す中で、(素因数分解される数を法とする)小さい平方剰余を生成する。数体ふるいは、既知の最も高速な汎用素因数分解アルゴリズムである。
大きな合成数 n を法とする数値の平方根を見つけることは、素因数分解(これは難しい(英語版)と広く信じられている)に相当するという事実は、Rabin暗号や紛失転送プロトコルなどの暗号化スキームの構築に使用されている。平方剰余性問題(英語版)は、ゴールドワッサー-ミカリ暗号(英語版)の基礎を成す。
離散対数も暗号化で用いられる同様の問題である。