[이산수학] Chapter 5. Introduction to Number Theory

1. Divisors

  1)

  - d가 n을 나누어 떨어지게 할 때, 즉 n=dq를 만족하는 integer q가 존재할 때, d divides n이라고 말한다. 

  - 이 때 q를 quotient, d를 divisor 또는 n의 factor라고 부른다.

  - d divides n일 때 d|n으로 쓴다.

 

  Theorem 5.1.3 

  m, n, d를 정수라고 하자. 만약 d|m이고 d|n이면 d|(m±n)이다. 또한 d|m이면 d|mn이다. 

 

  proof : d|m이고 d|n이면 m=dq, n=dq' 라고 쓸 수 있다. m+n = dq + dq' = d(q+q')이다. 

 따라서 d|(m+n) 이다. 

 

 

2) Prime and Composite

 - Prime : 소수

 - Composite : 합성수

   composition은 2와 루트n 사이의 divisor d를 갖는다.

 

* 소수와 합성수를 구분하는 알고리즘

//input : n
// output : d

is_prime(n) {
  for d=2 to sqrt(n) {
    if(n % d ==0)
    	return d
  }
  return 0
}

만약 소수이면 0을 return하고 합성수이면 나누어 떨어지는 divisior 값을 리턴한다.

 

Theorem 5.1.11 

 1보다 큰 정수는 소수들의 곱으로 나타낼 수 있다. 또한 이 소수들이 오름차순으로 쓰여진다면, 이 factorization은 unique하다. 

 

Theorem 5.1.12

 소수의 개수는 무한하다. 

 

 proof : p보다 작거나 같은 모든 소수들을 p1, p2....pn 이라고 하자. 

m = p1p2...pn + 1 이라고 하고, m을 q로 나누어 1이 남는 수, m = piq + 1이라고 하면 모든 i=1 to n까지 pi는 m을 나누어 떨어지게 만들지 못한다. 따라서 p'는 m의 prime factor이고, p'는 어떤 pi와도 같지 않다. 따라서 p1, p2 ,..., pn은 p보다 작거나 같은 소수들의 리스트이므로 p'>p인 pi를 무조건 갖는다.

 

 

3) 공약수와 공배수 

  - Greatest Common Divisor : 최대공약수( gcd(m,n) )

   

  - Least Common Multiple : 최소공배수 ( lcm(m,n) )

Theorem 5.1.25 

  gcd(m,n) * lcm (m,n) = mn

 

 

2. Representation of Integers and Integer Algorithms

  1) Number system 

    -Binary digits: 0, 1 (bits)

    -hexadecimal, octal ...

 

    -컴퓨터는 이진수로 돌아감. positive integer n을 표현하기 위해서는 몇 bits가 필요함.

   integer n을 표현하는데에는 k+1 bits가 필요하다. 이 때 k는 log n 보다 작거나 같고, log n 은 k+1보다 작다. 따라서 

 " k+1 <= 1+log n < k+2 " 이므로 k+1 = 1+log n 이다. 즉, integer n에서 필요한 비트수는 1+log n이다. 

 

위에 나온 소수 합성수 구분하는 알고리즘의 the worst case time은 Θ(√n) 

C(√n) ≥ Cc^s 이므로 Exponential time in the input size s 라는데 뭔소리임

 

 

 2) Binary to Decimal

 

*이진수 c 값을 b진수로 바꾸는 알고리즘

//input : c, n, b
// output : dec_val

base_b_to_dec(c, n, b){
  dec_val = 0;
  power = 1;
  for (i=0; i<n; i++){
  	dec_val = dec_val + ci * power
    power = power*b
  }
  return dec_val
}

 

  3) Decimal to Binary

//input : m,b
// output : c,n

dec_to_base_b(m,b,c,n){
  n= -1;
  while(m>0){
    n = n+1;
    c_n = m mode b;
    m= m/b;
  }
}

 

  4) Hexadecimal number System

 

 

  5) addition

   - Binary addition

 * Binary addition table

 

  * 알고리즘

//input : a, b, n
//output : s
 
 binary_addition(a, b, n, s){
   carry = 0;
   for (i=0;i<n;i++){
     s_i = (a_i + b_i + carry) % 2;
     carry = (a_i + b_i + carry) / 2
   }
   s_n+1 = carry
 }

  - Hexadecimal addition

 

 

 6) Exponentiation

 

 a^n을 계산하자!

 ① 단순 반복 ( repeated multiplication ) 

  a^n = a*a*...*

 

 ② 제곱을 이용

 

 a^29 = a^1 * a^4 * a^8 * a^16

 

  - a^2 = a*a

  - a^4 = a^2*a^2

  - a^8 = a^4 * a^4

  - a^16 = a^8 * a^8

 

 -> 7번의 계산

 

 

 

 * squring을 활용한 a^n을 구하는 알고리즘

//input : a, n
//output : a^n

exp_via_repeated_squaring(a,n){
  result = 1;
  x = a;
  while (n>0){
  	if(n % 2 ==1)
    	result = result *  x;
    x = x*x;
    n=n/2;
  }
  return result;
}

 

 Theorem 5.2.17

 만약 a, b, z가 양의 정수라면, ab mod z = [(a mod z) (b mod z)] mod z

 

//input : a, n, z
//output : a^n mod z

exp_mod_via_repeated_squaring(a,n,z){
  result = 1;
  x = a mod z;
  while (n>0){
  	if(n % 2 ==1)
    	result = (result *  x) mod z;
    x = (x*x) mod z;
    n=n/2;
  }
  return result;
}

 

 

3. The Euclidean algorithm

 - Euclid algorithm

 : gcd(a, b) = gcd(b, a mod b)

 

Theorem 5.3.2 

  a가 음수가 아닌 정수이고, b가 양의 정수이고, r=a mod b이라면, gcd(a, b) = gcd(b, r) 이다. 

 

//input : a, b
//output : greatest common divisor of a and b

gcd(a, b){
  //make a largest
  if(a<b)
    swap(a,b);
  while ( b != 0 ){
    r=a mod b;
    a = b;
    b = r;
  }
  return a;
}

 * a special result 

 Theorem 5.3.7.

    a와 b가 음이 아닌 정수일 때(단, 둘 다 0이면 안됨), gcd(a, b) = sa + tb를 만족하는 정수 s와 t가 존재한다.

 

ex) gcd(273, 110) = s*273 + t*110

 1) gcd(273, 110) 찾기 (=1)

 2) 다시 돌아가서 마지막 방정식 풀기 

 

 a= 273, b=110, 273 mod 110 = 53  -> 53 = 273 - 110*2

                      110 mod 53   = 4   -> 4 = 110 - 53*2

                       53 mod 4     = 1   -> 1 = 53 - 4*13

 

 즉, 1= 53 - (110 - 53*2)*13

       = 27*53 - 13*110

       = 27*(273 - 110*2) - 13*110

       = 27*273 - 67*110 

 

따라서 s=27, t=-67 임

 

 

 

 - Modulo convention 

      "0 (mod 5) vs "0 (mod 4)"

       N(mod 5)에서 N에는 0부터 4까지의 숫자가 들어갈 수 있음

 

 - Inverse Modulo of b (mod m)  

     bb^(-1) = 1 (mod m)

     m으로 나눌 때 기존 수에 어떤 수를 곱해서 나머지가 1이 나온다면, 그 수가 mod m number이다. 

 

    ex) inverses for (mod 5) number

         0 -> 0*0^(-1) mod 5 = 1? 존재하지 않음

         1 -> 1*1^(-1) mod 5 = 1?  1(mod 5)

         2 -> 2*2^(-1) mod 5 = 1?  3(mod 5)

         3 -> 3*3^(-1) mod 5 = 1?  2(mod 5)

         4 -> 4*4^(-1) mod 5 = 1?  4(mod 5)

   

즉 어떤 수에 곱해서 나머지가 1이 나오게 만드는 수가 바로 inverse modulo of b (mod m)

2에는 3을 곱해야 5로 나누었을 때 나머지가 1 (이 때 modulo에는 0~4가 가능함)

 

만약 gcd(e, Φ) = 1 이라고 해보자

1 = ed + Φy

ed = -Φy + 1

d는 e의 inverse modulo (즉 mod Φ)

또한 e와 Φ는 서로소임 (mutually prime)

 

 

 

모르겠으니 예시로 풀어보자

 

e=110, Φ= 273

 

gcd(e, Φ) = 1, -67e + 27Φ=1이다.

ed mod Φ = 110(-67) mod 273 = 1

d = -67 (근데 이거는 0과 273 사이가 아님)

 

s=d mod Φ = -67 mod 273 = 206

110 modulo 273의 inverse는 206임!

(-67 = 273*(-1) + 206)

 

 

 

4. The RSA public-key cryptosystem

 1) Cryptosystems : 보안 통신을 위한 시스템 ? 정부, 산업, 회사 등등에서 씀

    sender가 암호화(encryps)해서 보내면 receiver가 복호화(decrypts)해서 메시지를 읽음

 

    RSA ( Rivest, Shamir, Adleman) System 

    : 메세지는 숫자로 표현됨

    아주 큰 십진수 정수를 인수분해하는데 다항식의 시간 안에 해결할 수 있는 효율적인 알고리즘이 없다는 사실에 기반함.

 

   예전엔 그냥 단순하게 어떤 문자를 다른 문자로 replace했는데, 이건 쉽게 뚫림

 

 2) RSA

   - 메시지는 숫자로 표현된다. 

       A, B, C ,... => 1, 2, 3...

   - SEND MONEY => 20, 5, 15, 1, 14, 16, 15, 5, 26 => 200515011416150526

   

    ① 두 개의 소수 p, q 를 골라서 n=pq를 계산한다.

    ② Φ = (p-1)(q-1) 을 계산한다.

    ③ gcd(e, Φ)=1 인 아무 e를 고른다.

    ④ ed mod Φ = 1인 d를 계산한다. (0<d<Φ)

    ⑤ n, e는 암호화 키(encryption key, prime) : public

        p, q, d는 복호화 키(decryption key) : secret

    ⑥ 메시지를 보낼 때, m을 c=m^e mod n 으로 암호화한다.

    ⑦ c는 m=c^d mod n으로 복호화한다.