이차 잔차

수론에서, 정수 q는 완전 제곱 모듈 n과 일치하면 2차 잔차 모듈 n이라고 불린다. 즉, 다음과 같은 정수 x가 존재하면 다음과 같다.

$(\displaystyle x^{2}\equiv qpmod {n}).}$

그렇지 않으면 q를 2차 비잔류 모듈로 n이라고 합니다.

원래 모듈식 산술로 알려진 수 이론의 분과에서 나온 추상적인 수학적 개념이었던 2차 잔류물은 이제 음향 공학에서 암호학, 그리고 많은 수의 인수 분해에 이르는 응용 분야에서 사용됩니다.

역사, 관습 및 기본적인 사실

페르마, 오일러, 라그랑주, 레전드르, 그리고 17세기와 18세기의 다른 수 이론가들은 2차 잔기에 대한 이론을^[1] 확립하고 추측을^[2] 형성했지만, 첫 번째 체계적인 처리는 가우스의 디스퀴제 산술 (1801)의 § IV (1801)제95조는 '4차 잔차'와 '4차 비잔차'라는 용어를 도입하고, 문맥이 명확할 경우 '4차 잔차'라는 형용사를 삭제할 수 있다고 규정하고 있다.

주어진 n에 대하여, 2차 잔차 모듈로 n의 리스트는 숫자 0, 1, ..., n - 1을 제곱하는 것만으로 얻을 수 있다. a(n - a)(²mod n) 때문에, 제곱² 모듈로 n의 리스트는 n/2 주위에 대칭이며, 리스트는 그 높이만 올라가면 된다.이는 아래 표에 나와 있습니다.

따라서 2차 잔차 모듈 n의 수는 n/2 + 1(짝수) 또는 (n + 1)/2(n 홀수)^[3]를 초과할 수 없습니다.

2개의 잔류물의 곱은 항상 잔류물이다.

소수 계수

모듈로 2, 모든 정수는 2차 잔차이다.

모듈로 홀수 소수 p는 오일러 기준에 따라 (p + 1)/2 잔기(0 포함)와 (p - 1)/2 비잔기이다.이 경우 0을 특수한 경우로 간주하고 필드 Z/pZ의 0이 아닌 요소의 곱셈 그룹 내에서 작업하는 것이 일반적입니다.(즉, 0 modulo p를 제외한 모든 합치 클래스는 곱셈 역수를 가진다.복합 모듈리에는 해당되지 않습니다.)^[4]

이 규칙에 따라 잔기의 곱셈 역수는 잔기이고, 비잔기의 역수는 비잔기이다.^[5]

이 규칙에 따라 홀수 소수점에는 동일한 수의 잔류물과 비잔류가 ^[4]존재한다.

모듈로 프라임, 2개의 비잔류 곱은 잔류물, 비잔류 및 (비제로) 잔류물의 곱은 비잔류이다.^[5]

2차 상호성의 법칙에 대한 첫 번째^[6] 보충은 p 1 1(mod 4)이면 -1이 2차 잔차 모듈로 p이고 p ( 3(mod 4)이면 -1이 비잔차 모듈로 p라는 것이다.이것은 다음을 의미합니다.

p ≤ 1(mod 4)이면 잔류 모듈로 p의 음이 잔류물이고 비잔류 음이 비잔류이다.

p ≤ 3(mod 4)이면 잔류 모듈로 p의 음이 비잔류이고, 비잔류 음이 잔류물이다.

주배율

모든 홀수 제곱은 1 1(mod 8)이므로 1 1(mod 4)도 됩니다.a가 홀수이고 m = 8, 16 또는 그보다 높은 2의 거듭제곱일 경우 a는 ≤ 1(mod 8)^[7]인 경우에만 잔차 모듈로 m이다.

예를 들어 mod(32) 홀수 제곱은 다음과 같습니다.

1² 15² 15 11

3² 13² 13 99

5² 11² 11 25 25

7² 、 9² 、 49 、 17

짝수들은

0² 8² 8 1616² 0 0

2² 6² 6 1010² 14² 14 44

4² 12² 12 16 16

따라서 0이 아닌 숫자는 4(8n + 1)의 형태일^k 경우에만 잔차 모드 8, 16 등이 됩니다.

홀수 소수 p에 대한 상대 소수인 수는 잔류 모듈로 ^[8]p인 경우에만 p의 거듭제곱인 잔류 모듈로이다.

계수가 p이면ⁿ

그럼^k 파

k n n일 경우 잔류 모듈로ⁿ p이다.

k < n이 홀수일 경우 비잔류 모듈로ⁿ p가 됩니다.

k < n이 짝수이고 a가 잔기일 경우 잔기 모듈로ⁿ p이다.

k < n이 짝수이고 가 비잔류일 경우 는 비잔류 ^[9]모듈로 p 입니다ⁿ.

2의 거듭제곱과 홀수 소수의 거듭제곱에 따라 규칙이 다르다는 점에 유의하십시오.

modulo 홀수 prime^k power n = p, 비교적 prime to p의 곱은 mod p와 동일한 규칙을 준수한다. p는 비잔류이며, 일반적으로 모든 잔류와 비잔류물은 동일한 규칙을 준수하지만, 제품 내 p의 검정력이 n이면 0이 된다.

모듈로 8, 비잔류 3과 5의 곱은 비잔류 7이며 3, 5, 7의 배열도 마찬가지이다.실제로 비잔류 및 1의 곱셈군은 클라인 4군을 형성한다.

복합계수가 주출력이 아닙니다)

이 경우의 기본적인 사실은

a가 잔차 모듈로 n이면 a는 n을 나누는 모든 소수 전력에 대한 잔차 모듈로^k p이다.

a가 비잔류 모듈로 n일 경우, a는 n을 나누는 적어도1개의 주승에 대한 비잔류 모듈로^k p입니다.

합성수를 모듈로 하면, 두 잔기의 곱은 잔류물이다.잔기와 비잔기의 곱은 잔기, 비잔기 또는 0일 수 있다.

예를 들어 모듈러스 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이다.

이 현상은 추상대수의 어휘를 사용하여 가장 잘 설명할 수 있다.계수 대비 상대적으로 소수인 합치 클래스는 곱셈 중인 군으로, 고리 Z/nZ의 단위 그룹이라고 하며, 제곱은 그것의 부분군입니다.다른 비레지드는 서로 다른 코셋에 속할 수 있으며, 어떤 코셋에 해당 제품이 속할지를 예측하는 단순한 규칙은 없습니다.소수를 구하면, 제곱의 부분군과 단일 코세트만 존재합니다.

예를 들어 모듈로 15가 비잔류 3, 5 또는 비잔류 5와 잔류물 9의 곱, 또는 2개의 잔류물 9, 10이 모두 0인 것은 복합 n의 제수가 0인 풀링 Z/nZ에서 작용하기 때문이다.

이러한 이유로 일부^[10] 저자들은 2차 잔차 a가 제곱이어야 할 뿐만 아니라 계수 n에 대한 상대적인 소수여야 한다는 정의를 추가한다. (a는 a가 n에 대한 공동임인 경우에만² n에 대한 공동임이다.)

더 깔끔하게 만들기는 하지만, 이 기사는 잔류물이 계수와 동일해야 한다고 주장하지는 않는다.

표기법

가우스는^[11] 각각 R과 N을 사용하여 잔존도와 비잔존도를 표시했다.

예를 들어, 2 R 7과 5 N 7 또는 1 R 8과 3 N 8입니다.

비록 이 표기법이 작고 어떤 목적을 ^[12][13]위해 편리하지만, 더 유용한 표기법은 2차 문자라고도 불리는 Legendre 기호이다. 이것은 모든 정수 a와 양의 홀수 소수 p에 대해 정의된다.

${\displaystyle \leftfrac {a} {p} \right} = scases {case} \ ; \ ; 0 & { \ text { divide } ptext { } a \ operatorname {R } ptext { } 및 } ptext { divide } a \ } \ operatorname { R } ptext { R } ptext {R} \ 1 & {\ 1 & { text { text { text {\ } } } } } }} } } }$

번호 0(mod p)이 특별히 취급되는 이유는 두 가지가 있습니다.우리가 보았듯이, 그것은 많은 공식과 정리를 말하기가 더 쉬워진다.다른 (관련된) 이유는 2차 문자는 0이 아닌 합동 클래스 모듈로 p의 곱셈 그룹에서 곱셈 아래의 복소수까지의 동형사상이라는 것이다.${\displaystyle 설정\frac{}{}}$( ${\displaystyle \frac{n}{}\frac{}{}}$ ) $=$ { $displaystyle({\tfrac {np}{p$}})= $0}$이면 해당 도메인을 ^[14]모든 정수의 곱셈 반군으로 확장할 수 있습니다.

가우스에 비해 이 표기법의 한 가지 장점은 Legendre 기호가 ^[15]공식에서 사용할 수 있는 함수라는 것입니다.또한 입방정,^[16] 사분정 및 고출력 잔류물로 쉽게 일반화할 수 있습니다.

복합값인 p, Jacobi 기호에는 일반화가 있지만, 그 특성은 단순하지 않습니다. m이 복합값이고 Jacobi 기호$({\displaystyle \frac{m}{})}$ ${\displaystyle =}$ -$$이면 Nm$,$R M이면 M$frac$${a}$ {m})입니다$.$${\displaystyle \frac{a}{}}$ m${\displaystyle }$) $=$ $({\tfrac$ {$a}{$m}})=1$}$우리는$$ R m인지 N m인지 알 수 없습니다.예를 들어 $({\displaystyle \frac{2}{}}$ 15${\displaystyle )}$ $=$ ${\displaystyle 1}${$displaystyle({\tfrac {2}{15$})=$1$}$$및 (${\displaystyle \frac{4}{}}$ 15${\displaystyle )}$ $=$ {$displaystyle({\tfrac {4}{15$})=$1$이지만 2 N 15 및 4 R 15입니다.m이 소수이면 Jacobi 기호와 Legendre 기호가 일치합니다.

2차 잔류물의 분포

2차 잔류물은 다소 랜덤한 패턴 모듈로 발생하는 것으로 보이며, 음향학 및 암호학 등의 응용 분야에서 이용되어 왔지만, 이들의 분포도 몇 가지 두드러진 규칙성을 보인다.

산술 급수에서 소수점에 대한 디리클레의 정리, 2차 역수의 법칙 및 중국 나머지의 정리(CRT)를 사용하면, 숫자 1, 2, ..., M이 모두 잔기 모듈로 p인 M > 0에 대해 소수 p가 있음을 쉽게 알 수 있다.

예를 들어, p ( 1 (mod 8), (mod 12), (mod 5), (mod 28)의 경우, 2차 상호성의 법칙에 따라 모두 잔기 모듈로 p가 되며, 따라서 모든 숫자 1~10이 된다.CRT는 이것이 p 1 1 (mod 840)과 동일하며, Dirichlet의 정리에 따르면 이 형태의 소수는 무한하다고 합니다. 2521이 가장 작고, 실제로² 1 , 1²,1046 , 2²,123 , 3², 2 , 4, 643² , 5², 87 , 6,668² , 7,8²², 429 ≡ 339.

디리클레 공식

이러한 규칙성 아래의 첫번째 2진 2차 형태의 반 번호에 대한 분석적 공식에 페터 구스타프 르죈 디리클레의 작품(1830년대에)에서 비롯된다.[17]q 소수, 복잡한 변수 가운데를 디리클레 L-function 설명하겠습니다.

${\displaystyle L(s)=\sum_{n=1}({\frac{n}{q}}\right)n^{-s}.}$

디리클레 만약 q ≡ 3(모드 4), 보여 주었다.

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

이 경우에는 그러므로,(총리 q≡ 3(모드 4)), 2차 잔류물의 합에서 nonresidues의 범위 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의 차이는 언제나 이상한 배수 만약q>3.[18]대조적으로 총리 q, ≡ 1(모드 4), 2차 잔류물의 합에서 nonresidues의 범위 1에 그 금액, 2,...,q − 10이다는 돈을 동등한 q(q− 1)4{\displaystyle{\frac{q(q-1)}{4}}}.[표창 필요한]을 의미한다.

디리클레 또한 총리 q3(모드 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.}$

이는 그 중 nonresidues 1,2,...,(q− 1)/2보다 더 2차 잔류물이라는 것을 암시한다.

예를 들어, 11의 나머지 4명 잔류물 6(즉 1,3,4및 5)보다 오직 하나의nonresidue(2) 있다.

이 두 이론의 흥미로운 사실은 알려진 모든 증명들이 분석에 의존한다는 것이다; 아무도 두 ^[19]진술의 단순하거나 직접적인 증거를 발표한 적이 없다.

2차 상호성의 법칙

p와 q가 홀수 소수인 경우:

(p는 2차 잔차 mod q)가 (q는 2차 잔차 mod p)인 경우에만 (p와 q 중 적어도 하나가 1 mod 4와 일치한다.)

즉, 다음과 같습니다.

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

$({\displaystyle }$ ${\displaystyle \frac{p}{}}$q$$) { $displaystyle \left$( { \ $frac${$p$} { q$}$} \ $right$ )는$$ Legendre 기호입니다.

따라서 a를 나누지 않는 숫자 a와 홀수 소수 p의 경우:

a	a는 다음의 경우에만 2차 잔차 mod p입니다.	a	a는 다음의 경우에만 2차 잔차 mod p입니다.
1	(prime p마다)	−1	p 1 1 (mod 4)
2	p 1 1, 7 (mod 8 )	−2	p 1 1, 3 (mod 8 )
3	p 1 1, 11 (mod 12)	−3	p 1 1 (mod 3)
4	(prime p마다)	−4	p 1 1 (mod 4)
5	p 1 1, 4 (mod 5 )	−5	p 1 1, 3, 7, 9 (mod 20)
6	p 1 1, 5, 19, 23 (mod 24)	−6	p 1 1, 5, 7, 11 (mod 24)
7	p 1 1, 3, 9, 19, 25, 27 (mod 28)	−7	p 1 1, 2, 4 (mod 7)
8	p 1 1, 7 (mod 8 )	−8	p 1 1, 3 (mod 8 )
9	(prime p마다)	−9	p 1 1 (mod 4)
10	p 1 1, 3, 9, 13, 27, 31, 37, 39 (mod 40)	−10	p 1 1, 7, 9, 11, 13, 19, 23, 37 (mod 40)
11	p 1 1, 5, 7, 9, 19, 25, 35, 37, 39, 43 (mod 44)	−11	p 1 1, 3, 4, 5, 9 (mod 11)
12	p 1 1, 11 (mod 12)	−12	p 1 1 (mod 3)

잔류물과 비잔류물 쌍

소수 p를 곱하면 n R p와 n + 1 R p 또는 n p와 n + 1 R p 등이 거의 같다.더 ^[20][21]정확히는 p가 홀수 소수라고 하자.i, j = 0, 1의 경우 집합을 정의합니다.

$\displaystyle A_{ij}=\left\{k\in \{1,2,\flac,p-2\}:\leftflac {k}{p}=flac{i}\land \leftflac {k+1}{p}\right}=fland 1)^{j}\right}\light}$

그리고 렛

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

그것은,

α는₀₀ 잔류물이 뒤따르는 개수이다.

α는₀₁ 비잔류(non-residue)가 뒤따르는 잔류물의 수이다.

α는₁₀ 잔류물이 뒤따르는 비잔류 수이고,

α는₁₁ 비잔류 뒤에 이어지는 비잔류 수입니다.

p p 1 ( mod 4 )의 경우

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

p 3 3 ( mod 4 )의 경우

$\displaystyle \alpha _{01}=p+1}{4},\alpha _{00}=\alpha _{10}=\alpha _{11}=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)^[22]는 p 1 1(mod 4)이면⁴ x 2 2(mod p)는 p = a² + 64² b일 경우에만 풀 수 있다는 것을 증명했을 때 이러한 종류의 카운팅을 도입했다.

풀랴-비노그라도프 부등식

연속된 코인 ^[23]플립과 같은 랜덤 변수 값에 대한 ($)$ {$displaystyle({\tfrac {a}{p}})}$의${\displaystyle }$값은 코인 플립과 같은 랜덤 변수를 모방합니다.특히 1918년 폴랴와 비노그라도프는 모든^[24] 비원칙 디리클레 문자 δ(n) 모듈로 q와 정수 M과 N에 대해 (독자적으로) 증명했다.

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

큰 O 표기로.설정

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

이것은 길이 N의 간격에서 2차 잔류물 모듈로 q의 수가

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

을 증명하는 것은 쉽다^[25].

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

사실...^[26]

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

Montgomery와 Vaughan은 1977년에 이것을 개선하였고, 만약 일반화된 Riemann 가설이 사실이라면, 다음과 같은 것을 보여주었다.

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

슈어가 1918년에 증명하였기 때문에 이 결과는 상당히 개선될 수 없다.

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

그리고 팰리는 1932년에 증명했다.

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

d > 0인 경우.

최소 2차 비잔류

최소 2차 잔차 mod p는 분명히 1이다.최소 2차 비잔류 n(p)의 크기에 대한 질문은 더 미묘하지만 항상 소수이며, 7은 71에서 처음으로 나타난다.

위의 폴랴-비노그라도프 부등식은 O(θp log p)를 나타낸다.

최상의 무조건 추정치는 문자 ^[27]합계에 대한 Burgess의 추정치에 의해 얻어진 임의의 δ>1/4 µe에 대해 n(p) µp이다^θ.

일반화 리만 가설을 가정하면 Ankeny는 n(p) ( (log p)^2[28]를 구했다.

Linnik은 X보다 작은 p의 수가 n(p^ε) > X가 ^[27]θ에 따라 상수로 제한됨을 보여 주었다.

홀수 소수 p에 대한 최소 2차 비잔류 모드 p는 다음과 같습니다.

2, 2, 3, 2, 3, 2, 5, 2, 3, 3, 2, 2, 2, ... (OEIS의 시퀀스 A053760)

이차초과

p를 홀수 소수점이라고 하자.2차 초과 E(p)는 (0,p/2) 범위의 2차 잔류물의 수에서 (p/2,p) 범위의 수(OEIS의 시퀀스 A178153)를 뺀 값이다.1 mod 4에 해당하는 p의 경우 -1은 2차 잔기이고 r ↔ p-r에서 잔기는 대칭이기 때문에 초과는 0이다.3 mod 4에 해당하는 p의 경우, 초과 E는 항상 양의 ^[29]값입니다.

제곱근을 찾는 복잡성

즉, 숫자 a와 계수 n이 주어졌을 때, 이것은 얼마나 어려운가?

1. x 해결² x ) a (mod n)가 존재하는지 여부를 알 수 있다.
2. 만약 존재한다고 가정한다면, 계산해 볼 수 있을까요?

소수와 합성 모듈리의 중요한 차이가 여기에 나타납니다.모듈로 소수 p, 2차 잔기 a는 1 + (a p)근(즉, N p의 경우 0, a ≤ 0(mod p)의 경우 1 또는 R p 및 gcd(a,p) = 1의 경우 2)을 가진다.

일반적으로 합성 계수 n이 서로 다른 소수의 거듭제곱의 곱으로 쓰여져 있고, 첫 번째 루트 모듈로₁₂ n, 두 번째 루트 모듈로 n, ...가 있다면₁₂, nn이 있을 것이다.루트 모듈

주역들의 해법 모듈로가 결합되어 해법 모듈로가 되는 이론적인 방법을 중국의 나머지 정리라고 부릅니다. 효율적인 ^[30]알고리즘으로 구현될 수 있습니다.

예를 들어 다음과 같습니다.

x 6 6(mod 15)을² 구합니다.

x² 6 6(mod 3)은 0, x² 6 6(mod 5)은 2개, 1개 및 4개의 해를 가집니다.

그리고 두 개의 솔루션 모듈로 15가 있습니다. 즉, 6과 9입니다.

x² 4 4(mod 15).

x² µ 4(mod 3)에는 1과 2의 2개의 솔루션이 있으며² x µ 4(mod 5)에는 2개의, 2와 3의 솔루션이 있습니다.

그리고 4개의 솔루션 모듈로 15, 즉 2, 7, 8, 13이 있습니다.

x ÷ 7(mod 15)을² 해결합니다.

x² 7 7(mod 3)에는 1과 2의 2개의 솔루션이 있으며² x 7 7(mod 5)에는 솔루션이 없습니다.

솔루션 모듈로 15는 없습니다.

소수 또는 소수 전력 계수

첫째, 계수 n이 소수일 경우, 유클리드의 알고리즘^[31] 또는 오일러의 기준을 변형하여 신속하게 Legendre $)\$를 계산할 수 있습니다.-1일 경우 해결 방법이 없습니다.둘째, (${\displaystyle \frac{a}{})}$ ${\displaystyle =}$ ${\displaystyle 1}$\ $displaystyle \ frac${ $a$} {$n}$ \ right $\}$ $= 1$that n n 3 ( mod 4 )인 경우, Lagrange는 다음과 같이 솔루션이 주어지는 것을 발견했다.

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

및^[32] Legendre는 n † 5(mod 8):

${\displaystyle x\equiv {case}\pm \;a^{(n+3)/8}{\pmod {n}}{\text}{\pm \a^{(n+3)/8}2^{(n-1)/4}{\pmod {n}}{text}}{text}} {\text}}}$

단, 소수 n≤ 1(mod 8)의 경우 알려진 공식은 없습니다.Tonelli^[33] (1891년)와^[34] Cipolla는 모든 소수에 적용되는 효율적인 알고리즘을 발견했다.두 알고리즘 모두 2차 비잔류 모듈 n을 찾아야 하며, 이를 위해 알려진 효율적인 결정론적 알고리즘은 없습니다.그러나 1과 n 사이의 숫자의 절반이 잔존하지 않기 때문에 숫자 x를 랜덤으로 선택하고 잔존하지 않는 숫자를 찾을 때까지 Legendre 기호$(\$를 계산하면 즉시 잔존하지 않는 숫자가 생성됩니다.이 알고리즘의 약간의 변형은 Tonelli-Shanks 알고리즘입니다.

계수 n이 소수 n = p일^e 경우, 헨젤의 렘마 또는 ^[8]가우스의 알고리즘을 이용하여 용액을 모듈로 p로 구하여 용액 모듈로 n에 대해 "비교"할 수 있다.

복합 계수

계수 n이 소수 거듭제곱에 인수분해된 경우 해법은 위에서 논의되었다.

n이 2 modulo 4와 일치하지 않고 Kronecker 기호$({\displaystyle \frac{n}{})}$ $=$ -$$${\displaystyle 1}$(\$displaystyle \tfrac {a}\right$)=-$1)$이면 해결 방법이 없습니다. ${\displaystyle \frac{n}{}}$이 2 modulo 4${\displaystyle }$및 (${\displaystyle \frac{n}{}}$/${\displaystyle \frac{}{}}$2) ${\displaystyle =}$ - 1$(\displaystyle \tfrac {a}/})$이면 해결 방법이 없습니다.n이 2 modulo 4와 일치하지 않고${\displaystyle }$(${\displaystyle \frac{a}{}}$ )$$ ${\displaystyle 1}$ {\$displaystyle \left\tfrac$ {$a}$ {$n}}\right$)=1$\}$ $또는$ n이 2 modulo 4와 일치하고${\displaystyle }$(${\displaystyle \frac{a}{}}$ ${\displaystyle \frac{/}{}\frac{2\mathrm{}}{}}$) ${\displaystyle =}$ {\$displaystyle \tfrac {a}{n/2}}\right=1$일 경우, 또는 1이 없을 수 있습니다.

n의 완전한 인수분해를 알 수 없고$,{\displaystyle }$(${\displaystyle \frac{a}{}}$ ) $=$ ${\displaystyle 1}$ {\$displaystyle$\left$\tfrac$ {$a}$ {$n}} = 1$$${\displaystyle \tfrac {n}} = n은 2 modulo 4와 일치하지 않거나${\displaystyle \frac{,}{}}$ ${\displaystyle \frac{n}{}}$ /${\displaystyle \frac{}{}\frac{2\mathrm{}}{}}{\displaystyle =}$ ${\displaystyle 1}$ {$displaystyle \tleft\tfrac {$n} } {n} }$=$ 2/}n(즉, 어느 한 문제에 대한 효율적인 솔루션을 사용하여 다른 문제를 효율적으로 해결할 수 있다).

위의 설명은 n의 인자를 알면 어떻게 효율적으로 근을 찾을 수 있는지를 보여줍니다.합성수의 제곱근 모수를 찾는 효율적인 알고리즘이 있다고 가정해 보십시오.제곱의 기사 일치성은 x와² y의 두 숫자를 찾는² 것이 어떻게 n을 효율적으로 인수분해하는 데 x ( y(mod n)와 x y ± y로 충분한지 논의한다.난수를 생성하고 이를 제곱하여 효율적인 제곱근 알고리즘이 루트를 찾도록 합니다.원래 제곱한 것과 같지 않은 수(또는 음의 모듈로 n)를 반환할 때까지 반복한 다음 제곱합으로 설명된 알고리즘을 따릅니다.인수분해 알고리즘의 효율은 루트파인더의 정확한 특성에 따라 달라집니다(예를 들어 모든 루트를 반환합니까?).가장 작은 것? 무작위?) 하지만 ^[35]효율적일 것입니다.

a가 2차 잔차인지 비잔차 모듈로 n(R n 또는 N n을 나타냄)인지를 Legendre 기호를 계산함으로써 prime n에 대해 효율적으로 판단할 수 있다.그러나 합성 n의 경우 이는 인수 분해만큼 어려운 것으로 알려져 있지 않지만 상당히 어려운 것으로 가정되는 2차 잔존성 문제를 형성합니다.

한편, 주어진 한계 c보다 작은 x에 대한 해답이 있는지 알고 싶다면, 이 문제는 NP-완전이지만,^[36] 이것은 고정 파라미터 추적 가능한 문제이며, 여기서 c는 파라미터입니다.

일반적으로 a가 2차 잔기 모듈로 복합 n인지 아닌지를 판단하기 위해서는 다음과 ^[37]같은 정리를 사용할 수 있다.

n > 1 및 gcd(a,n) = 1로 합니다.그러면² x µ a(mod n)는 다음과 같은 경우에만 해결 가능합니다.

• 모든 홀수 소수 p(n)에 대한 Legendre 기호$({\displaystyle \frac{a}{})}$ $=$ $(\displaystyle \tfrac {a}{p}\right$)=$1}.$
• n이 4로 나누어지지만 8로 나누어지지 않으면 a 1 1(mod 4), n이 8로 나누어지면 a 1 1(mod 8).

주의: 이 정리는 기본적으로 n의 인수분해를 알아야 한다.또한 gcd(a,n) = m이면 합치는 a/m µ² x/m(mod n/m)로 감소될 수 있지만 m이 정사각형인 경우를 제외하고 2차 잔기에서는 문제가 사라집니다.

2차 잔차 수

n = 1, 2, 3 ...에 대한 2차 잔기 모듈 n의 수 목록은 다음과 같습니다.

1, 2, 2, 3, 4, 3, 3, 4, 4, 4, 4, 6, 6, 4, 7, 8, 6, 6, 6, ... (OEIS의 시퀀스 A000224)

스탕글은 ^[38]제곱모듈로 n을 세는 공식이다.

2차 잔류물의 적용

음향학

소리 확산기는 원시근 및 2차 ^[39]잔류물과 같은 수 이론 개념을 기반으로 합니다.

그래프 이론

옅은 그래프는 각 p ≤ 1(mod 4)에 대해 1개씩 조밀한 무방향 그래프이며, 회의 그래프의 무한 패밀리를 형성하며, 대칭 회의 행렬의 무한 패밀리를 생성합니다.

Paley Digraph는 Paley 그래프의 방향 아날로그로, 각 p † 3(mod 4)에 대해 하나씩이며, 대칭 회의 행렬을 생성합니다.

이러한 그래프의 구성에는 2차 잔류가 사용됩니다.

암호화

큰 합성 n의 수 모듈의 제곱근을 구하는 것이 인수분해와 동등하다는 사실은 라빈 암호 시스템 및 망각 전송과 같은 암호 체계를 구축하는 데 사용되어 왔다.2차 잔존성 문제는 Goldwasser-Micali 암호 시스템의 기초입니다.

이산 로그는 암호학에서도 사용되는 유사한 문제입니다.

프라이머리 테스트

오일러의 기준은 p가 소수인 Legendre 기호 a에 대한 공식이다.p가 합성인 경우 공식은 (a p)를 올바르게 계산할 수도 있고 아닐 수도 있습니다.주어진 숫자 n이 소수인지 합성인지에 대한 솔로베이-스트라센 원시성 테스트는 임의의 a를 선택하고 유클리드의 ^[40]알고리즘 수정과 오일러의 ^[41]기준을 사용하여 (a)를 계산한다.결과가 일치하지 않으면 n은 합성이고, 일치하면 n은 합성 또는 소수일 수 있습니다.합성 n의 경우 적어도 1/2의 경우 2, 3, ..., n - 1 범위의 a 값은 "n is composite"를 반환하며, 소수 n의 경우 none이 반환되지 않습니다.a, n의 여러 다른 값을 사용한 후 합성된 것으로 증명되지 않은 경우 "예측 소수"라고 한다.

Miller-Rabin primality test는 같은 원리에 기초하고 있습니다.이 테스트의 출력은 "n은 확실히 합성" 또는 "n은 소수이거나 GRH는 거짓"입니다.합성 n에 대해 두 번째 출력이 발생할 경우 GRH는 거짓이 되며 이는 수학의 많은 분기에 영향을 미칩니다.

정수 인수분해

디스퀴지션의 § VI에서 가우스는^[42] 2차 잔기와 2차 상호성의 법칙을 사용하는 2개의 인수분해 알고리즘을 논한다.

몇 가지 최신 인수분해 알고리즘(딕슨의 알고리즘, 연속분수법, 2차 체 및 숫자장 체 포함)은 인수분해를 생성하는 제곱의 일치성을 찾기 위해 작은 2차 잔기(인수분해되는 수)를 생성한다.숫자 필드 체는 알려진 것 중 가장 빠른 범용 인수분해 알고리즘입니다.

2차 잔기 표

다음 표(OEIS의 시퀀스 A096008)는 2차 잔기 mod 1 ~ 75(빨간색 숫자는 n에 대한 코프라임이 아님을 의미함)이다(n에 대한 2차 잔기 coprime은 OEIS: A096103, 2차 잔기는 OEIS: A047160 참조).

n	이차 잔기 mod n	n	이차 잔기 mod n	n	이차 잔기 mod 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, 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, 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, 9, 13, 16, 20, 22, 23, 24, 25, 28, 29, 30, 33, 35, 36, 38, 42, 45, 49, 51, 52, 53, 54, 57
9	0, 1, 4, 7	34	0, 1, 2, 4, 8, 13, 15, 16, 17, 18, 19, 21, 25, 26, 30, 32, 33	59	0, 1, 3, 4, 5, 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, 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, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36	62	0, 1, 2, 4, 5, 7, 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, 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, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 29, 33, 36, 37, 39, 40, 47, 49, 54, 55, 56, 59, 60, 62, 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, 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, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 24, 25, 27, 30, 32, 36, 37, 38, 40, 43, 45, 48, 49, 50, 54, 57, 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, 6, 9, 12, 16, 18, 19, 23, 24, 25, 27, 35, 36, 37, 38, 41, 46, 48, 49, 50, 54, 57, 61, 64, 67, 70, 72
24	0, 1, 4, 9, 12, 16	49	0, 1, 2, 4, 8, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46	74	0, 1, 3, 4, 7, 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, 64, 65, 67, 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

2차 잔류물(A048152, A343720 참조)

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
모드 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
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
모드 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
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
모드 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
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
모드 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
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
모드 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
모드 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

「 」를 참조해 주세요.

• 오일러의 기준
• 가우스 보조군
• 졸로타레프족
• 문자 합계
• 2차 상호성의 법칙
• 이차잔류코드

메모들

레퍼런스

디스퀴지스 산술서는 가우스의 시케로니아 라틴어에서 영어와 독일어로 번역되었다.독일어판은 수론에 관한 그의 모든 논문들을 포함하고 있다: 모든 2차 상호성의 증명, 가우스 합의 부호 결정, 2차 상호성의 조사, 그리고 미발표 주.

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second corrected ed.), New York: Springer, ISBN 0-387-96254-9 {{citation}}: first2=범용명(도움말)이 있습니다.
• 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 {{citation}}: first2=범용명(도움말)이 있습니다.
• Bach, Eric; Shallit, Jeffrey (1996), Efficient Algorithms, Algorithmic Number Theory, vol. 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 A7.1: AN1, 페이지 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
• 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.
• PlanetMath에서의 Polya-Vinogradov 부등식의 증명.