이 부분은 이산수학 정수론 공부하는 중에


중국인 나머지 정리 직후에 나온 부분입니다.


밑에 두부분으로 나누어 서술할 부분의 설명과 예제는 왜 그런 값들이 나오는지 이해가 되는데


왜 그런식으로 표현해야하고


설명과 예제가 궁극적으로 말하고자 하는 말의 뜻을 모르겠습니다.



소제목은 큰 정수의 컴퓨터 산술 

이라고 되어있는데



1.

m1, m2, m3 ... mn은 2보다 크거나 같은 쌍으로 서로소인 정수이며 M은 그들의 곱


중국인 나머지 정리에 의해  0 <= a


즉


(a mod m1,   a mod m2,   ....a mod mn)이런 식으로


예를 들면


첫 요소가 3으로 나눈 나머지이며 둘째 요소가 정수를 4로 나눈 나머지인 순서 쌍일때

12보다 작은 음이 아닌 정수로 표현하는데 사용되는 쌍은


0 = (0,0)

1 = (1,1)

2 = (2,2)

3 = (0.3)

,,,,,,

10 = (1,2)

11 = (2,3)




2.


큰 정수의 산술을 수행하기 위해 계수 m1, m2 ,,, mn을 선택한다.


i != j 일때 gcd (mi, mj) = 1이고 m = m1*m2*n3....mn으로 우리가 수행하기 원하는 산술 연산의 결과보다 크다.


계수가 선택되면 mi (i = 0 , 1, 2, ,,,, n)으로 나눈 나머지를 사용해


이들 정수를 표현하는 n쌍 요소에 연산을 행함으로 정수의 산술연산을 수행한다


이후 모듈로 mi합동의 시스템을 풀어서 값을 회복함



예를들어


100보다 작은 정수의 산술 계산이 큰 정수의 산술계산보다 훨씬 빠르다고 가정한다.


정수를 100보다 작은 쌍의 서로소의 모듈로 나머지를 표현하면 100보다 작은 정수에 거의 모든 계산을 제한할수있음.


예로 99, 98, 97, 95의 계수를 사용한다.



중국 나머지 정리에 의해 이들의 곱인 89,403,930 보다 작고 음이 아닌 모든 정수는 이 4개 계수에 의해 나누어질 때


나머지에 의해 유일하게 표현이 가능하다.


예로 123,684 = X라 하였을때


X mod 99 = 33

X mod 98 = 8

X mod 97 = 9

X mod 95 = 89

이므로 X를 (33, 8, 9, 89)로 표현가능


유사하게 

413,456 = Y라 하였을때

Y를 (32, 92, 42, 16) 라 표현 가능


X와 Y의 합을 구하기 위해 두 정수가 아닌 4쌍을 가지고 작업한다.


(33, 8, 9, 89) +  (32, 92, 42, 16) = 

(65 mod 99,    100 mod 98,    51 mod 97,    105 mod 95) = 

(65, 2, 51, 10)


즉

x ≡ 65 (mod 99)

x ≡ 2  (mod 98)

x ≡ 51 (mod 97)

x ≡ 10 (mod 95)


이를 계산하면


 x ≡ 5,242,610(mod M ) (M = 99 * 98 * 97 * 95)


따라서 537,140 (X + Y)는 M보다 작고 유일한 음이 아닌 이 시스템의 해 이다.





요기 까지인데


나무는 보이는데 숲이 안보이는 느낌이라고 말씀드리는게 좋을거같아요


한줄 한줄은 이해가 되는데 (아니면 그렇다고 느끼는지 모르겠지만)


저 단락들이 도데체 궁극적으로 무었을 의미하는지 모르겠습니다.




1번은

계수 m과 n이 있을떄

m*n보다 작은 음이아닌 정수를


(a mod m,   a mod n)의 꼴들로 표현이 가능하다는거 같은데


이런 표현이 왜 언제 쓰이는지 모르겠습니당.




2번은

서로소인 계수를 사용하여


임의의 정수를 계수의 mod연산의 쌍으로 표현이 가능한거 같은데


소로소의 모듈로 나머지는 표현하면 100보다 작은 정수에서 거의 모든 계산을 제한할수 있다 << 이 말의 의미를 모르겠습니다.


그리고 임의의 X와 Y를 가지고


선택한 4개의 계수를 이용해 모듈 연산을 시행했을때


(33, 8, 9, 89)  (32, 92, 42, 16)


이 두 쌍이 나왔는데


다시 이 X + Y를 구하기 위해 이 쌍들을 이용하는데


그렇게 나온 결과



x ≡ 65 (mod 99)

x ≡ 2  (mod 98)

x ≡ 51 (mod 97)

x ≡ 10 (mod 95)

의 연산 537,140 (X + Y)는 M보다 작고 유일한 음이 아닌 이 시스템의 해 이다.  <<<< 요 부분의 의미를 모르겠습니다.



글이 두서없고 쓸대없이 장문충이여서 댓글이 달릴지 안달릴지 모르겠지만


저 1번과 2번의 예제가 무었을 의미하는지 도통 모르겠습니당 ㅠㅠ


혹시 저부분이 무었을 의미하는지, 뭘 말하고 싶은지 이해되시면 알려주실수 있나영? ㅠㅠ