Studying Number theory 2

Organize notes#

정수론 2#

설명: 페르마의 정리(Fermat’s little theorem)와 오일러 정리(Euler’s theorem)의 정수론과 암호악에 있어 빼놓을 수 없는 중요한 정리임
- RSA 공개키 암호, DSA 전자 서명 등의 많은 정수론을 사용한 암호학적 시스템이 이 정리들에 기반함
1. 페르마의 소정리(Fermat’s little theorem)
  - 위치(position): 소수(Prime number)가 가지는 여러 중요한 성질 중 하나에 관한 정리
  - 설명: 소수 p, 그리고 p와 서로소인 정수 a에 대하여 a^p-1 ≡ 1 (mod p)를 만족함
    - p가 소수이기 때문에 a가 p인 소로소인 조건은 a가 p의 배수가 아니기만 하면 됨. 달리말해, p를 modulus로 하였을 때, 0이 아닌 나머지 p - 1가지 의 모든 수 a에 대하여 a^p-1 ≡ 1 (mod p)가 성립함
  - 증명
    1. 0 이상 p 미만의 수들 중 p와 서로소인 수들의 집합을 S라고 정의함. S의 원소의 수는 p - 1개이고, S = {1, 2, …, p - 1}로 표현됨
    2. p와 서로소인 정수 a에 대하여 집합 S의 모든 원소에 a를 곱한 값들의 집합을 S’로 정의한다. S’의 원소의 수 또한 p - 1개이고, S’ = {a, 2 * a, …, (p - 1) * a}와 같이 표현됨
    3. 기존 S의 모든 원소들이 p의 배수가 아니고, a도 p의 배수가 아니기 때문에, S’의 모든 원소도 p의 배수가 아님. 즉 S’의 모든 원소 또한 p와 서로소임
    4. S’의 모든 원소는 p와 서로소이기 때문에 p를 법으로 {1, 2, …, p - 1} 중 하나에 속해 있다. 만약 S’의 p - 1개의 원소가 p를 법으로 전부 다 다르다는 것이 증명된다면, S’의 모든 원소는 p를 법으로 {1, 2, …, p - 1}이 각각 정확히 하나씩 빠짐없이 들어가있다는 것이 증명됨
      - 증명
        
        임의의 1 <= i < j <= p - 1을 만족하는 i, j에 대하여 S’의 i번째 원소는 i * a이고, S’의 j번째 원소는 j * a이다. 두 원소를 빼면 (j - i) * a라는 값이 나오게 됨
        
        1 <= i < j <= p - 1에 속하는 i, j에 대하여 1 <= j - i <= p - 2이기 때문에 j - i는 p의 배수가 될 수 없고, a 또한 p의 배수가 될 수 없기 때문에 S’ 의 i번째 원소는 S’의 j번째 원소는 p를 modulus로 서로 다른 값을 가지게 되어 가정이 성립함
    5. S와 S’는 p를 법으로 순서만 바뀐 {1, 2, …, p - 1}이 한 번씩 들어가 있으므로, 각 집합의 모든 원소의 곱은 p를 modulus로 동일함
    6. S의 모든 원소의 곱은 (p - 1)!, S’의 모든 원소의 곱은 (1 * a)(2 * a)…((p - 1) * a) = (p - 1)! * a^p-1이다. 여기서 !연산은 팩토리얼 연산을 의미함
      - 따라서 다음 식이 성립함 -> (p - 1)! * a^p-1 ≡ (p - 1)! (mod p)
    7. (p - 1)!는 p의 배수가 아닌 수들만으로 곱해져 있기 때문에 p와 서로소임. 그러므로 양변에 역원인 ((p - 1)!)^-1을 곱하여 소거할 수 있음
      - 다음과 같은 식이 나옴 -> (p - 1)! * ((p - 1)!)^-1 * a^p-1 ≡ (p - 1)! * ((p - 1)!)^-1 (mod p)
      - 요약: 결국 이 페르마의 소정리는 a^p-1 ≡ 1 (mod p)를 증명하고 싶던 것이다
    - 소거 후에 최종적으로 a^p-1 ≡ 1 (mod p)를 얻어 페르마의 소정리를 증명할 수 있음
2. 오일러 정리(Euler’s theorem)
  - 설명: 양의 정수 n과 서로소인 양의 정수 a이 다음 식을 만족한다는 정리 -> a^ϕ(n) ≡ 1 (mod n)
  - 모듈러 파이 함수(Euler’s phi function, ϕ): n 이하의 양의 정수 중에서 n과 서로소인 수의 개수
    - 예시: 6이하의 양의 정수 중 6과 서로소인 수는 1, 5로 두 개이기 때문에 ϕ(6) = 2이고, 소수 p의 경우에는 1부터 p - 1까지 모두 p와 서로소이기 때문에 ϕ(p) = p - 1가 되어 페르마의 소정리와 동일한 결과를 나타냄
      - p가 소수여야지 성립됨
  - 오일러 파이 함수의 값 ϕ(n)을 일반적인 자연수 n에 대하여 구하는 방법
    1. 먼저 n을 다음과 같이 표현함 -> n = p^e₁₁p^e₂₂…p^e_k_k
    2. 이때 모든 p_i는 소수이고, e_i는 1 이상의 정수임. 모든 양의 정수 n에 대하여 k >= 0을 만족하는 위와 같은 표현이 유일하게 존재함
      - 다시 말해, 모든 양의 정수 n에 대하여 유일한 소인수분해 결과가 존재함
    3. 0 ~ n - 1의 n개의 정수에 대하여 p₁과 서로소인 정수는 몇 개인지 계산해본다. p₁번마다 p₁의 배수가 등장하고, 나머지는 전부 p₁과 서로소임이 보장됨
      - 따라서 전체 중에서 p₁과 서로소인 비율은 1 - 1/_p₁임
    4. 모든 서로 다른 p_i들은 서로소임을 사용하여 다른 p_i에 대해서도 비율을 계산하여 1 - 1 - 1/_p₁가 되고, n개와 모든 비율들을 다 곱하면 다음과 같음 -> ϕ(n) = n * (1 - 1/_p₁)( 1 - 1/_p₂)…( 1 - 1/_{p_k})
  - RSA 공개키 암호에서는 서로 다른 두 소수 p, q를 곱한 값으로 n을 생성하여 사용함
    - 즉 n = p * q와 같이 표현되는 경우의 ϕ(n)
      1. n = p * q인데 p와 q가 소수이므로 ϕ(n)은 n보다 작으면서 p와 q의 배수가 아닌 수들의 개수가 됨
      2. n이하의 수 중 p의 배수는 q개, q의 배수는 p개 존재하며 이 중 공통으로 존재하는 수는 두 수의 최소공배수인 n뿐임
      3. 따라서 ϕ(n)는 다음과 같은 식으로 표현 가능함 -> ϕ(n) = p * q - p - q + 1 = (p - 1)(q - 1)
        
        ϕ(n) = (p - 1)(q - 1)로 표현되는 것을 확인할 수 있음
        
        또한 위에서 일반화한 수식을 통해서도 확인 가능함 -> ϕ(n) = p * q * (1 - 1/_p)(1 - _q) = (p - 1)(q - 1)
  - 오일러 정리의 증명
    - n = p * q인 경우의 증명
      1. 오일러 정리는 다음과 같음 -> n과 서로소인 a에 대하여 a^ϕ(n) ≡ 1 (mod n)이 성립함
      2. 이는 페르마의 소정리를 사용하여 증명할 수 있음. 페르마의 소정리에 의해 다음의 두 식이 성립함
        
        a^p-1 ≡ 1 (mod p), a^q-1 ≡ 1 (mod q)
      3. 따라서 다음이 성립함 -> a^{(p - 1)(q - 1)} ≡ 1 (mod p), a^{(p - 1)(q - 1)} ≡ 1 (mod q)
      4. p, q가 서로소이기 때문에 중국인의 나머지 정리를 사용하면 다음과 같이 결론지을 수 있음
        
        a^{(p - 1)(q - 1)} ≡ 1 (mod p * q)
      - p * q 꼴의 n에 대하여 a^ϕ(n) ≡ 1 (mod n)이 성립하는 것을 확인 가능함
    - 일반적인 양의 정수 n에 대한 증명
      - 일반적인 양의 정수 n에 대한 증명 또한 페르마의 소정리의 증명 과정과 동일하게 진행됨
        
        0 이상 n 미만의 n과 서로소인 모든 정수위 집합을 S라고 정의. 이때 S의 원소의 수는 ϕ(n)개임.
        
        S의 모든 원소에 a을 곱하여 저장한 집합 S’은 n을 modulus로 S와 동일한 집합임.
        
        이에 대한 증명은 페르마의 소정리 과정과 동일함
        
        따라서, S의 모든 원소의 곱에 a^ϕ(n)을 곱하여도 S의 모든 원소의 곱과 n을 modulus로 동일하기 때문에 a^ϕ(n) ≡ 1 (mod n)이 성립함