정수론 1

1. integer divisibility(가분성)

• 0이 아닌 정수 a와 정수가 있다. a가 b를 나눴을 때 b=ak가 되는 k가 존재한다면 Divisibility라고 한다. a|b로 표기한다.
• Divisibility는 숫자를 작은 원소(primes)로 분해할 때 중요하다.
• a, b, c 정수가 있다. a가 0이 아닐 때 a|0과 a|a는 성립한다. 또한 1|b의 모든 값은 b이다.
• a|b이고 b|c이면 a|c이다.
• a|b이고 a|c이면, 모든 정수 s와 t에 대한 a(sb+tc)이 있다

2. Prime(소수)

• 만약 p>1이고 1과 자기 자신으로만 나눠진다면 p는 prime이다. 단순히 n>1이면 n은 prime이 아닌 composite이다.
• 모든 양의 정수는 소수의 결과이다. 소수에 대한 요인은 독특하다.

-      prime으로 구성되어 있지 않은 양의 정수가 존재한다고 가정하자

-      작은 정수 n이 있다.

-      n은 1이 아니고 p가 아니기 때문에, n=ab로 구성된 n이어야 한다.

-      a와 b는 소수이어야 한다.

-      n은 a와 b를 곱한 값이므로 composite이어야 한다.

 

 

 

3. Modular 연산

• Modular연산은 나머지를 구하는 연산이다. 표현은 mod n으로 표현한다.
• 정수 a와 b가 있다. a와 b를 n으로 나눴을 때 나머지가 같으면 이때 b ≡ a mod n이라 표현한다. (합동)

-      [(a mod n) + (b mod n)] mod n = (a + b) mod n

-      [(a mod n) – (b mod n)] mod n = (a – b) mod n

-      [(a mod n) * (b mod n)] mod n = (a * b) mod n

-      교환, 분배, 결합, 항등원, 역원이 성립한다.

 

 

 

4. Great Common Divisor(최대 공약수)

• a와 b의 최대 공약수는 a와 b를 나눌 수 있는 가장 큰 수이다. gcd(a, b)로 표기한다.
• 만약 gcd(a, b)이면 a와 b는 relatively prime(서로소)이다.
• a와 b를 소수로 나눌 수 있다면, gcd(a, b)를 얻는 것은 쉽지만 때로는 소수 분해를 얻는 것이 쉽지 않다.
• gcd(a, b)를 구하는 방법에는 잘 알려진 Euclidean algorithm이 있다.

 

 

5. Division in Zn (mod inverse)

• Zn은 n보다 작은 음이 아닌 정수 집합이다

-      Zn = {0, 1, 2, …, n-1}

 

• Division(Zn)은 gcd(a, n) = 1이고, as + nt =1인 s,t가 있다. 그때 as는 1 mod n과 합동이고, s ≡ a^(-1) mod n 이라고 한다.
• Modular Inverse (a^-1 mod n)

-      정수 a를 n으로 나눈 나머지 연산의 곱셈 역원은 a * a^-1 ≡ 1 mod n 을 만족하는 a^-1을 말한다.

1. 확장 유클리드 알고리즘을 이용해 d = as + nt인 d, s, t를 구한다.
2. 만약 d=1이면 a^-1 ≡ s mod n이다. (Extended Euclidean algorithm을 해서 s값이 역원이다)

 

6. Euclidean & Extended Euclidean

• Euclidean Algorithm

1.     a>b인 a와 b가 있다. 2.     r0 = a, r1 = b 3.     r0 = q1*r1 + r2 4.     r1 = q2*r2 + r3 5.              … 6.     rk-2 = qk-1*rk-1 + rk 7.     rk-1 = qk*rk + 0 where rk+1=0 8.     Output gcd(a,b) = rk * q1은 r1으로 r0을 나눴을 때 나오는 몫이다.

 

 

 

• Extended Euclidean Algorithm

1.     a>b인 a와 b가 있다. 2.     r0 = a*1, r1 = b*0 where (x0, y0) = (1, 0) 3.     r1 = a*0, r1 = b*1 where (x1, y1) = (0, 1) 4.                               … 5.     rj-2 = a*xj-2 + b*yj-2 6.     rj-1 = a*xj-1 + b*yj-1 7.     rj = a*(xj-2 + q j-1*xj-1) + b*(yj-2 + q j-2*xj-1) from rj-2 = qj-1*rj-1 + rj                 where (xj, yj) = (xj-2 + q j-1*xj-1, *(yj-2 + q j-2*xj-1)                                  … 8.     Output gcd(a, b) = rk with (xk, yk) where rk+1 = 0 * q1은 r1으로 r0을 나눴을 때 나오는 몫이다.

 

 

ex) a=1180, b=482