정리 현대적인 정리 방식으로 이 정리는 다음과 같이 서술됩니다:
p = p_1 \cdot p_2 \cdot \ldots \cdot p_k라고 합시다. 여기서 p_i는 쌍마다 서로소인 수입니다.
임의의 수 a (0 \le a < p)에 a_i \equiv a \pmod {p_i}를 만족하는 튜플 (a_1, \ldots, a_k)를 대응시킵시다:
a \Longleftrightarrow (a_1, \ldots, a_k).
그러면 이 대응(수와 튜플 사이의 대응)은 일대일 대응이 됩니다. 더 나아가, 수 a에 대해 수행하는 연산은 각 성분에 대해 독립적으로 연산을 수행함으로써 대응하는 튜플의 원소들에 대해 동등하게 수행할 수 있습니다.
즉, 다음과 같다면
a \Longleftrightarrow \Big( a_1, \ldots, a_k \Big[…] b \Longleftrightarrow \Big( b_1, \ldots, b_k \Big[…]
다음이 성립합니다:
{(a+b) \pmod p} \Longleftrightarrow \Big( {(a_1+b[…] {(a-b) \pmod p} \Longleftrightarrow \Big( {(a_1-b[…] {(a \cdot b) \pmod p} \Longleftrightarrow \Big( {[…]
처음 정식화된 형태의 이 정리는 서기 100년경 중국의 수학자 손자(孫子)가 증명했습니다. 구체적으로 말하면, 그는 특수한 경우에 대해 모듈러 방정식 연립계를 푸는 것과 하나의 모듈러 방정식을 푸는 것이 동치임을 보였습니다(아래 따름정리 2 참고).
따름정리 1 모듈러 방정식계:
\cases{ {x \equiv a_1 \pmod {p_1}}, \cr \ldots,[…]
법 p에 대해 유일한 해를 가집니다.
(위와 마찬가지로 p = p_1 \cdot \ldots \cdot p_k이고, 수 p_i는 쌍마다 서로소이며, a_1, \ldots, a_k는 임의의 정수 집합입니다)
따름정리 2 따름정리로서, 모듈러 방정식의 연립과 이에 대응하는 하나의 모듈러 방정식 사이에 다음과 같은 관계가 성립합니다:
방정식:
x \equiv a \pmod p
다음 연립방정식과 동치입니다:
\cases{ {x \equiv a \pmod {p_1}}, \cr \ldots, […]
(앞에서와 마찬가지로 p = p_1 \cdot \ldots \cdot p_k이고, 수 p_i는 쌍마다 서로소이며, a는 임의의 정수라고 가정합니다)
가너 알고리즘 중국인의 나머지 정리로부터 수에 대한 연산을 튜플에 대한 연산으로 대체할 수 있다는 사실이 도출됩니다. 다시 말하자면, 각 수 a에는 튜플 (a_1, \ldots, a_k)가 대응되며, 여기서 다음이 성립합니다:
{ a_i \equiv a \pmod {p_i} } .
이는 (서로 다른 모듈러에 대한 나머지로부터 수를 복원하는 직접적인 용도 외에도) 실제로 폭넓게 활용될 수 있습니다. 이렇게 하면 긴 수 연산(long arithmetic)을 “짧은” 수들의 배열에 대한 연산으로 대체할 수 있기 때문입니다. 예를 들어, 원소 1000개짜리 배열이면 약 3000자리의 수까지 “충분합니다”(p_i로 처음 1000개의 소수를 고른 경우). 그리고 p_i로 10억 근처의 소수들을 고른다면, 약 9000자리의 수까지 충분합니다. 하지만 물론 그렇게 하려면 이 튜플로부터 수 a를 복원하는 방법을 알아야 합니다. 따름정리 1로부터 이러한 복원이 가능하며, 게다가 유일하다는 것을 알 수 있습니다(0 \le a < p_1 \cdot p_2 \cdot \ldots \cdot p_k라는 조건 하에서). Garner 알고리즘이 바로 이 복원을, 그것도 상당히 효율적으로 수행할 수 있게 해 주는 알고리즘입니다.
다음과 같은 형태로 해를 구해 봅시다:
a = x_1 + x_2 \cdot p_1 + x_3 \cdot p_1 \cdot p_2[…]
즉, 자릿값이 p_1, p_2, \ldots, p_k인 혼합 기수법으로 나타낸 것입니다.
p_j를 법으로 하는 p_i의 역원인 수를 r_{ij} (i=1 \ldots k-1, j=i+1 \ldots k)로 나타냅시다(모듈러 환에서 모듈러 역원을 구하는 방법은 여기에 설명되어 있습니다:
r_{ij} = (p_i) ^ {-1} \pmod {p_j} .
혼합 기수법으로 나타낸 a의 식을 연립 방정식의 첫 번째 방정식에 대입하면 다음을 얻습니다:
a_1 \equiv x_1.
이제 이 식을 두 번째 방정식에 대입합시다:
a_2 \equiv x_1 + x_2 \cdot p_1 \pmod {p_2}.
양변에서 x_1을 빼고 p_1로 나누어 이 식을 변형합시다:
a_2 - x_1 \equiv x_2 \cdot p_1 \pmod {p_2}; (a_2 - x_1) \cdot r_{12} \equiv x_2 \pmod {p_2}; x_2 \equiv (a_2 - x_1) \cdot r_{12} \pmod {p_2}.
세 번째 방정식에 대입하면, 같은 방식으로 다음을 얻습니다:
a_3 \equiv { x_1 + x_2 \cdot p_1 + x_3 \cdot p_1 […] (a_3 - x_1) \cdot r_{13} \equiv x_2 + x_3 \cdot p[…] ((a_3 - x_1) \cdot r_{13} - x_2) \cdot r_{23} \eq[…] x_3 \equiv ((a_3 - x_1) \cdot r_{13} - x_2) \cdot[…]
이제 패턴이 꽤 분명하게 보이며, 이는 코드로 표현하는 것이 가장 간단합니다:
for (int i=0; i<k; ++i) { x[i] = a[i]; for (int j=0; j<i; ++j) { x[i] = r[j][i] * (x[i] - x[j]);
x[i] = x[i] % p[i];
if (x[i] < 0) x[i] += p[i];
}
} 이제 계수 x_i를 O (k^2) 시간에 계산하는 방법을 익혔으며, 답 자체인 수 a는 다음 공식으로 복원할 수 있습니다:
a = x_1 + x_2 \cdot p_1 + x_3 \cdot p_1 \cdot p_2[…]
실제로는 거의 항상 답을 긴 수 연산(Long arithmetic)을 사용하여 계산해야 하지만, 계수 x_i 자체는 여전히 내장 자료형으로 계산되므로 Garner 알고리즘 전체는 상당히 효율적이라는 점에 주목할 필요가 있습니다.
가너 알고리즘의 구현 이 알고리즘은 Java 언어로 구현하는 것이 가장 편리합니다. Java에는 표준 긴 정수 연산이 포함되어 있으므로, 수를 모듈러 체계에서 일반적인 수로 변환하는 데 아무런 문제가 생기지 않기 때문입니다(표준 클래스 BigInteger를 사용합니다).
아래에 제시하는 가너 알고리즘의 구현은 덧셈, 뺄셈, 곱셈을 지원하며, 음수도 다룰 수 있습니다(이에 대해서는 코드 뒤의 설명을 참고하십시오). 일반적인 십진 표현의 수를 모듈러 체계로 변환하는 기능과 그 역변환 기능이 구현되어 있습니다.
이 예제에서는 10^9 이후의 소수 100개를 사용하며, 이를 통해 대략 10^{900}까지의 수를 다룰 수 있습니다.
final int SZ = 100; int pr[] = new int[SZ]; int r[][] = new int[SZ][SZ];
void init() { for (int x=100010001000, i=0; i<SZ; ++x) if (BigInteger.valueOf(x).isProbablePrime(100)) pr[i++] = x;
for (int i=0; i<SZ; ++i)
for (int j=i+1; j<SZ; ++j)
r[i][j] = BigInteger.valueOf( pr[i] ).modInverse(
BigInteger.valueOf( pr[j] ) ).intValue();
}
class Number {
int a[] = new int[SZ];
public Number() {
}
public Number (int n) {
for (int i=0; i<SZ; ++i)
a[i] = n % pr[i];
}
public Number (BigInteger n) {
for (int i=0; i<SZ; ++i)
a[i] = n.mod( BigInteger.valueOf( pr[i] ) ).intValue();
}
public Number add (Number n) {
Number result = new Number();
for (int i=0; i<SZ; ++i)
result.a[i] = (a[i] + n.a[i]) % pr[i];
return result;
}
public Number subtract (Number n) {
Number result = new Number();
for (int i=0; i<SZ; ++i)
result.a[i] = (a[i] - n.a[i] + pr[i]) % pr[i];
return result;
}
public Number multiply (Number n) {
Number result = new Number();
for (int i=0; i<SZ; ++i)
result.a[i] = (int)( (a[i] * 1l * n.a[i]) % pr[i] );
return result;
}
public BigInteger bigIntegerValue (boolean can_be_negative) {
BigInteger result = BigInteger.ZERO,
mult = BigInteger.ONE;
int x[] = new int[SZ];
for (int i=0; i<SZ; ++i) {
x[i] = a[i];
for (int j=0; j<i; ++j) {
long cur = (x[i] - x[j]) * 1l * r[j][i];
x[i] = (int)( (cur % pr[i] + pr[i]) % pr[i] );
}
result = result.add( mult.multiply( BigInteger.valueOf( x[i] ) ) );
mult = mult.multiply( BigInteger.valueOf( pr[i] ) );
}
if (can_be_negative)
if (result.compareTo( mult.shiftRight(1) ) >= 0)
result = result.subtract( mult );
return result;
}
} 음수 지원에 대해서는 따로 언급할 필요가 있습니다(함수 {\rm bigIntegerValue}()의 플래그 \rm can_be_negative). 모듈러 체계 자체는 양수와 음수를 구별하지 않습니다. 그러나 특정 문제에서 답의 절댓값이 모든 소수의 곱의 절반을 넘지 않는다면, 양수는 이 중간값보다 작게 나오고 음수는 더 크게 나온다는 점에서 양수와 음수가 구별된다는 것을 알 수 있습니다. 따라서 고전적인 가너 알고리즘을 수행한 후 결과를 중간값과 비교하고, 결과가 더 크면 마이너스 부호를 출력하고 결과를 반전시킵니다(즉, 모든 소수의 곱에서 결과를 빼고 그 값을 출력합니다).