제곱 잉여

3. 제곱잉여의 성질

소수 ''p''를 법으로 할 때, ''n'' R ''p''이고 ''n'' + 1 R ''p''인 쌍 또는 ''n'' N ''p''이고 ''n'' + 1 R ''p''인 쌍 등의 개수는 거의 같다.^[20][21] ''p''를 홀수 소수라고 하자. ''i'', ''j'' = 0, 1에 대해 다음 집합을 정의한다.

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

그리고

:$\backslash alpha\_\{ij\}\; =\; |A\_\{ij\}|.$

즉,

:α₀₀은 제곱 잉여 다음에 제곱 잉여가 오는 경우의 수이고,

:α₀₁은 제곱 잉여 다음에 제곱 비잉여가 오는 경우의 수이고,

:α₁₀은 제곱 비잉여 다음에 제곱 잉여가 오는 경우의 수이고,

:α₁₁은 제곱 비잉여 다음에 제곱 비잉여가 오는 경우의 수이다.

그러면 ''p'' ≡ 1 (mod 4)이면

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

이고 ''p'' ≡ 3 (mod 4)이면

:$\backslash alpha\_\{01\}\; =\; \backslash frac\{p+1\}\{4\},\backslash ;\backslash alpha\_\{00\}\; =\backslash alpha\_\{10\}\; =\backslash alpha\_\{11\}\; =\; \backslash 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)^[22]는 ''p'' ≡ 1 (mod 4)일 때 ''x''⁴ ≡ 2 (mod ''p'')가 풀릴 필요충분조건이 ''p'' = ''a''² + 64 ''b''²임을 증명하면서 이러한 종류의 계산을 도입했다.

모듈로 ''n''에 대한 이차 잉여의 개수 목록은 ''n'' = 1, 2, 3 ...에 대해 다음과 같다.

:1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, ...

모듈로 ''n''에 대한 제곱수의 개수를 세는 공식은 Stangl에 의해 제공된다.^[38]

''n'' = 1, 2, 3, … 에 대한 ''n''을 법으로 하는 제곱 잉여의 수 목록은 다음과 같다.

: 1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, …

''n''을 법으로 하는 제곱수의 수를 세는 공식은 스탕글(Stangl)에 의해 주어진다.^[83]

==== 소수 법 ====

모듈로 2에서는 모든 정수가 제곱 잉여이다. 홀수 소수 ''p''를 법으로 할 때, 오일러 기준에 따라 (''p'' + 1)/2개의 잉여(0 포함)와 (''p'' - 1)/2개의 비잉여가 있다.^[4] 0은 특수한 경우로 간주하고 체 $(\backslash mathbb\{Z\}/p\backslash mathbb\{Z\})$의 0이 아닌 원소의 곱셈군 내에서 작업한다.^[4]

이 관례에 따라, 잉여의 곱셈 역수는 잉여이고, 비잉여의 역수는 비잉여이다.^[5] 홀수 소수를 법으로 할 때, 잉여와 비잉여의 수는 같다. 소수를 법으로 할 때, 두 비잉여의 곱은 잉여이고, 비잉여와 (0이 아닌) 잉여의 곱은 비잉여이다.

2차 상호 법칙의 첫 번째 보충 정리에 따르면,^[6] ''p'' ≡ 1 (mod 4)이면 -1은 모듈로 ''p''에서 제곱 잉여이고, ''p'' ≡ 3 (mod 4)이면 -1은 모듈로 ''p''에서 비잉여이다.

만약 ''p'' ≡ 1 (mod 4)이면 모듈로 ''p''에서 잉여의 음수는 잉여이고, 비잉여의 음수는 비잉여이다. 만약 ''p'' ≡ 3 (mod 4)이면 모듈로 ''p''에서 잉여의 음수는 비잉여이고, 비잉여의 음수는 잉여이다.

홀수 소수 ''p''와 서로소인 수 ''a''는 ''p''의 거듭제곱을 법으로 하는 잉여일 때 ''p''를 법으로 하는 잉여이다.^[8]

제곱 잉여의 상호 법칙에 따르면, ''p''와 ''q''가 홀수인 소수일 때, (''p''가 ''q''를 법으로 하는 제곱 잉여)와 (''q''가 ''p''를 법으로 하는 제곱 잉여)는 (''p''와 ''q'' 중 적어도 하나가 4를 법으로 1과 합동)과 동치이다. 즉,

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

이며, 여기서 $\backslash left(\backslash frac\{p\}\{q\}\backslash right)$는 르장드르 기호이다.

따라서, 숫자 ''a''와 ''a''를 나누지 않는 홀수인 소수 ''p''에 대해, 다음 표와 같다.

==== 합성수 법 ====

합성수 ''n''을 법으로 할 때, 두 제곱잉여의 곱은 항상 제곱잉여이다.^[10] 하지만 잉여와 비잉여의 곱, 또는 두 비잉여의 곱은 잉여, 비잉여, 또는 0이 될 수 있다.^[10]

예를 들어 법 6에서 잉여 3과 비잉여 5의 곱은 잉여 3이지만, 잉여 4와 비잉여 2의 곱은 비잉여 2이다.^[10] 법 15에서 비잉여 2와 8의 곱은 잉여 1이지만, 비잉여 2와 7의 곱은 비잉여 14이다.^[10]

어떤 수 ''a''가 ''n''에 대한 잉여라면, ''a''는 ''n''을 나누는 모든 소수 거듭제곱에 대한 잉여이다.^[10] 반대로 ''a''가 ''n''에 대한 비잉여라면, ''a''는 ''n''을 나누는 최소한 하나의 소수 거듭제곱에 대한 비잉여이다.^[10]

이 현상은 추상대수학의 용어로 설명할 수 있다. 법 ''n''과 서로소인 합동류는 곱셈에 대해 군을 이루며, 이를 환 $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$의 단위군이라고 부른다.^[10] 제곱은 그 부분군이 되며, 서로 다른 비잉여는 서로 다른 잉여류에 속할 수 있고, 그들의 곱이 어떤 잉여류에 속할지 예측하는 간단한 규칙은 없다.^[10]

일부 저자들은 제곱 잉여 ''a''는 제곱수일 뿐만 아니라 법 ''n''과 서로소여야 한다는 정의를 추가하기도 한다.^[54]

3. 1. 소수 법

3. 2. 합성수 법

4. 제곱잉여의 분포

제곱 잉여는 법 ''n''에서 무작위적인 패턴을 보이는 듯하지만, 몇 가지 규칙성도 나타낸다.^[17] 이러한 규칙성은 디리클레가 이진 이차 형식의 해석 공식을 연구하면서 처음 발견되었다.^[17]

디리클레 정리, 2차 상호 법칙, 중국인의 나머지 정리를 이용하면, 임의의 ''M'' > 0에 대해 숫자 1, 2, ..., ''M''이 모두 모듈로 ''p''에서 잉여가 되는 소수 ''p''가 존재함을 보일 수 있다. 예를 들어 ''p'' ≡ 1 (mod 8), (mod 12), (mod 5), (mod 28)이면, 2차 상호 법칙에 의해 2, 3, 5, 7은 모두 모듈로 ''p''에서 잉여가 되므로 1-10까지의 모든 숫자가 잉여가 된다. CRT에 따르면 이는 ''p'' ≡ 1 (mod 840)과 같으며, 디리클레 정리에 따르면 이러한 형태의 소수는 무한히 많다. 2521이 가장 작은 소수이며, 실제로 1² ≡ 1, 1046² ≡ 2, 123² ≡ 3, 2² ≡ 4, 643² ≡ 5, 87² ≡ 6, 668² ≡ 7, 429² ≡ 8, 3² ≡ 9, 529² ≡ 10 (mod 2521)이다.

디리클레는 디리클레 L-함수를 정의하고, ''q'' ≡ 3 (mod 4)인 소수 ''q''에 대해 L(1)의 값을 계산하여 1, 2, ..., ''q'' − 1 범위에서 이차 잉여의 합과 비잉여의 합의 차이가 음수임을 보였다. 예를 들어 11을 법으로 할 때, 잉여는 1, 3, 4, 5, 9이고, 비잉여는 2, 6, 7, 8, 10이다. 잉여의 합은 22, 비잉여의 합은 33으로, 그 차이는 -11이다. ''q'' > 3인 경우 이 차이는 항상 ''q''의 홀수 배수이다.^[18] 또한, ''q'' ≡ 1 (mod 4)인 경우, 이차 잉여의 합과 비잉여의 합은 서로 같고, 그 값은 $\backslash frac\{q(q-1)\}\{4\}$이다. 디리클레는 ''q'' ≡ 3 (mod 4)인 경우 1, 2, ..., (''q'' − 1)/2 범위에서 비잉여보다 이차 잉여가 더 많다는 사실도 증명했다. 예를 들어 11을 법으로 할 때, 6보다 작은 잉여는 1, 3, 4, 5로 4개이고, 비잉여는 2로 1개이다. 그러나 이 두 정리에 대한 알려진 모든 증명은 해석학에 의존하며, 간단하거나 직접적인 증명은 아직 발견되지 않았다.^[19]

포여와 비노그라도프는 포여-비노그라도프 부등식을 통해 주어진 구간에서 제곱잉여의 개수를 추정했다.^[24] 그들은 임의의 비주요 디리클레 지표 χ(''n'') 모듈로 ''q''와 임의의 정수 ''M'' 및 ''N''에 대해 $\backslash left|\backslash sum\_\{n=M+1\}^\{M+N\}\backslash chi(n)\backslash right|\; =O\backslash left(\; \backslash sqrt\; q\; \backslash log\; q\backslash right)$임을 보였다. χ(''n'')을 $\backslash left(\backslash frac\{n\}\{q\}\backslash right)$로 설정하면, 길이 ''N''의 임의의 구간에서 법 ''q''에 대한 제곱 잉여의 개수가 $\backslash frac\{1\}\{2\}N\; +\; O(\backslash sqrt\; q\backslash log\; q)$임을 알 수 있다.^[25] 또한, 이며,^[25] 더 정확하게는 이다.^[26]

몽고메리와 본은 일반화된 리만 가설이 참이라면 $\backslash left|\backslash sum\_\{n=M+1\}^\{M+N\}\backslash chi(n)\backslash right|=O\backslash left(\backslash sqrt\; q\; \backslash log\; \backslash log\; q\backslash right)$임을 보였다. 그러나 슈어와 페일리의 결과에 따르면 이 결과는 크게 개선될 수 없다.

홀수 소수 ''p''에 대한 최소 이차 비잉여는 항상 소수이며, 문자 합에 대한 Burgess의 추정치를 통해 얻은 ''n''(''p'') ≪ ''p''^θ (θ>1/4)이다.^[28] 일반화된 리만 가설 하에서, Ankeny는 ''n''(''p'') ≪ (log ''p'')²를 얻었다.^[27] 린닉은 ''n''(''p'') > X^ε인 ''X'' 미만의 ''p''의 개수가 ε에 따라 달라지는 상수로 제한된다는 것을 보였다.^[28] 홀수 소수 ''p''에 대한 최소 이차 비잉여는 2, 2, 3, 2, 2, 3, ... () 순으로 나타난다.

소수 ''p''가 4로 나눈 나머지가 3일 때, (0, ''p''/2) 범위 내의 제곱 잉여의 개수에서 (''p''/2, ''p'') 범위 내의 개수를 뺀 값인 '''제곱 잉여 초과''' ''E''(''p'')는 항상 양수이다.^[29]

5. 제곱근 계산의 복잡도

주어진 수 ''a''와 법 ''n''에 대해, ''x''² ≡ ''a'' (mod ''n'')를 만족하는 ''x''를 찾는 문제는 법이 소수인지 합성수인지에 따라 다른 복잡도를 가진다.

법 ''n''이 소수인 경우, 르장드르 기호를 야코비 기호 계산이나 오일러 기준을 사용하여 빠르게 계산할 수 있다.^[31] 만약 르장드르 기호가 -1이면 해는 존재하지 않는다. $\backslash left(\backslash frac\{a\}\{n\}\backslash right)=1$이고 ''n'' ≡ 3 (mod 4)이면, 조제프루이 라그랑주가 발견한 해의 공식은 다음과 같다.^[32]

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

''n'' ≡ 5 (mod 8)일 때, 아드리앵마리 르장드르는 비슷한 해를 발견했다.^[32]

: $x\; \backslash equiv\; \backslash begin\{cases\}$

\pm\; a^{(n+3)/8} \pmod{n}& \text{ 만약 } a \text{가 } n \text{을 법으로 하는 사차 잉여일 때 } \\

\pm\; a^{(n+3)/8}2^{(n-1)/4} \pmod{n}& \text{ 만약 } a \text{가 } n \text{을 법으로 하는 사차 비잉여일 때 } \end{cases}

소수 ''n'' ≡ 1 (mod 8)의 경우에는 알려진 공식이 없지만, 토넬리-섕크스 알고리즘^[33]과 치폴라 알고리즘^[34]은 모든 소수 법에 대해 작동하는 효율적인 알고리즘이다. 이 알고리즘들은 ''n''을 법으로 하는 이차 비잉여를 찾아야 하는데, 이를 위한 효율적인 결정적 알고리즘은 알려져 있지 않다. 그러나 1과 ''n'' 사이의 수의 절반이 비잉여이므로, 임의의 수를 선택하고 르장드르 기호를 계산하여 비잉여를 빠르게 찾을 수 있다.

법 ''n''이 소수 거듭제곱 ''n'' = ''p''^''e''이면, 헨젤의 보조정리나 가우스의 알고리즘을 사용하여 법 ''p''에서의 해를 법 ''n''으로 "올릴" 수 있다.

합성수 법 ''n''의 경우, ''n''의 소인수 분해가 알려져 있으면 중국인의 나머지 정리를 통해 해를 구할 수 있다.^[30] 예를 들어, x² ≡ 6 (mod 15)를 풀 때, x² ≡ 6 (mod 3)은 0이라는 하나의 해를 갖고, x² ≡ 6 (mod 5)는 1과 4라는 두 개의 해를 갖는다. 따라서 15에 대한 법에서는 6과 9라는 두 개의 해가 있다. 하지만 ''n''의 소인수 분해가 알려져 있지 않으면, 제곱근을 찾는 문제는 소인수 분해 문제와 동등하게 어렵다고 알려져 있다.^[35]

''a''가 소수 ''n''을 법으로 제곱 잉여인지 비잉여인지 결정하는 것은 르장드르 기호를 계산하여 효율적으로 수행할 수 있다. 그러나 복합수 ''n''의 경우, 제곱 잉여성 문제가 되며, 이는 소인수 분해만큼 어렵다고 알려져 있지는 않지만, 매우 어렵다고 가정된다.

6. 제곱잉여의 응용

제곱 잉여는 음향 확산기 설계에 사용되며, 이는 원시 근과 제곱 잉여 같은 수론적 개념을 기반으로 한다.^[39][84] 페일리 그래프는 제곱 잉여를 사용하여 구성되며, 각 소수 ''p'' ≡ 1 (mod 4)에 대해 하나씩 존재하며, 이는 무한한 종류의 컨퍼런스 그래프를 형성하고, 무한한 종류의 대칭 컨퍼런스 행렬을 생성한다.^[42] 또한, 페일리 방향 그래프는 페일리 그래프의 방향성 유사체로, 제곱잉여를 사용하여 구성되며 각 ''p'' ≡ 3 (mod 4)에 대해 하나씩 존재하며, 비대칭 컨퍼런스 행렬을 생성한다.

어떤 큰 합성수 ''n''을 모듈로 하는 숫자의 제곱근을 찾는 것이 소인수 분해와 동등하다는 사실은 라빈 암호 시스템, 무지향 전송 등 암호화 방식 구축에 사용되어 왔으며, 제곱 잉여 문제는 골드와서-미칼리 암호 시스템의 기반이 된다.^[42] 이산 로그는 암호학에서 사용되는 유사한 문제이다.

오일러의 기준은 소수 ''p''에 대한 르장드르 기호 (''a''|''p'')를 구하는 공식이며, 솔로베이-스트라센 소수 판별법은 주어진 수 ''n''이 소수인지 합성수인지 판별하는 데 사용된다.^[40][41] 밀러-라빈 소수 판별법도 같은 원리에 기반하며, 일반화된 리만 가설에 의존한다.

가우스는 《산술 탐구》^[42]의 6절에서 이차 잉여와 이차 상호 법칙을 사용하는 두 가지 소인수분해 알고리즘에 대해 논의한다.

몇몇 현대적인 소인수분해 알고리즘 (딕슨의 알고리즘, 연분수 방법, 이차 체 방법, 수체 체)은 소인수분해를 위한 제곱 합동을 찾으려고 시도한다.^[42]

6. 1. 한국 정보통신기술(ICT)과의 연관성

7. 제곱잉여표

법 ''n''에 대한 제곱 잉여의 개수 목록은 ''n'' = 1, 2, 3 ...에 대해 다음과 같다.

:1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, ...

모듈로 ''n''에 대한 제곱수의 개수를 세는 공식은 Stangl에 의해 제공된다.

참조

_[1] 문서 Lemmemeyer, Ch. 1
_[2] 문서 Lemmermeyer, pp 6–8, p. 16 ff
_[3] 문서 Gauss, DA, art. 94
_[4] 문서 Gauss, DA, art. 96
_[5] 문서 Gauss, DA, art. 98
_[6] 문서 Gauss, DA, art 111
_[7] 문서 Gauss, DA, art. 103
_[8] 문서 Gauss, DA, art. 101
_[9] 문서 Gauss, DA, art. 102
_[10] 간행물
_[11] 문서 Gauss, DA, art. 131
_[12] 문서 e.g. Hardy and Wright use it
_[13] 문서 Gauss, DA, art 230 ff.
_[14] 문서 This extension of the domain is necessary for defining ''L'' functions.
_[15] 문서 See [[Legendre symbol#Properties of the Legendre symbol]] for examples
_[16] 문서 Lemmermeyer, pp 111–end
_[17] 간행물
_[18] 간행물
_[19] 간행물
_[20] 문서 Lemmermeyer, p. 29 ex. 1.22; cf pp. 26–27, Ch. 10
_[21] 문서 Crandall & Pomerance, ex 2.38, pp 106–108
_[22] 문서 Gauss, ''Theorie der biquadratischen Reste, Erste Abhandlung'' (pp 511–533 of the ''Untersuchungen über hohere Arithmetik)''
_[23] 문서 Crandall & Pomerance, ex 2.38, pp 106–108 discuss the similarities and differences. For example, tossing ''n'' coins, it is possible (though unlikely) to get ''n''/2 heads followed by that many tails. V-P inequality rules that out for residues.
_[24] 간행물
_[25] 웹사이트 Planet Math: Proof of Pólya–Vinogradov Inequality '#External links'
_[26] 문서 Pomerance & Crandall, ex 2.38 pp.106–108. result from T. Cochrane, "On a trigonometric inequality of Vinogradov", ''J. Number Theory'', 27:9–16, 1987
_[27] 서적 Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis American Mathematical Society
_[28] 서적 Opera De Cribro American Mathematical Society
_[29] 서적 Analytic Number Theory World Scientific
_[30] 간행물
_[31] 간행물
_[32] 문서 Lemmermeyer, p. 29
_[33] 간행물
_[34] 간행물
_[35] 문서 Crandall & Pomerance, ex. 6.5 & 6.6, p.273
_[36] 논문 1978
_[37] 서적 Elementary Number Theory McGraw HIll
_[38] 간행물 Counting Squares in ℤ_''n'' http://www.maa.org/s[...] 1996-10
_[39] 웹사이트 The design and application of modular acoustic diffusing elements http://downloads.bbc[...] BBC Research Department 2016-10-25
_[40] 논문 1996
_[41] 논문 1996
_[42] 문서 DA
_[43] 문서 Ch.1
_[44] 문서
_[45] 문서 DA
_[46] 문서 DA
_[47] 문서 DA
_[48] 문서 DA
_[49] 문서 DA
_[50] 문서 DA
_[51] 문서 DA
_[52] 문서 DA
_[53] 문서 DA
_[54] 논문 1990
_[55] 문서 DA
_[56] 문서
_[57] 문서 DA
_[58] 문서
_[59] 문서
_[60] 문서
_[61] 논문 2000
_[62] 논문 2000
_[63] 논문 2000
_[64] 문서
_[65] 문서
_[66] 문서 Theorie der biquadratischen Reste, Erste Abhandlung
_[67] 문서
_[68] 논문 2000
_[69] 문서 Planet Math: Proof of Pólya-Vinogradov Inequality
_[70] 문서
_[71] 서적 Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis American Mathematical Society
_[72] 서적 Opera De Cribro American Mathematical Society
_[73] 서적 Analytic Number Theory World Scientific
_[74] 논문
_[75] 논문
_[76] 문서
_[77] 논문
_[78] 논문
_[79] 문서 DA
_[80] 문서
_[81] 논문
_[82] 서적 Elementary Number Theory McGraw HIll
_[83] 간행물 Counting Squares in ℤ{{sub|''n''}} http://www.maa.org/s[...] 1996-10
_[84] 웹사이트 The design and application of modular acoustic diffusing elements http://downloads.bbc[...] BBC Research Department 2016-10-25
_[85] 논문
_[86] 논문
_[87] 문서 DA