[이산수학] Cyclic Group(순환군), Lagrange Theorem (라그랑주의 정리), Euler Theorem (오일러 정의), Fermat (Little) Theorem (페르마의 소정리), Discrete Logarithm(이산 로그)

Cyclic Group

 

정의

그룹 G가 cyclic이 되기 위해서는 G 안에 생성자(generator)라고 불리는 특정 원소 x가 존재해야한다.
G의 모든 원소 a는 x의 거듭제곱으로 만들 수 있다. $a \in G, \ a = x^n, \ n \in Z$

 

• Cyclic Group $Z_4$가 있다. 1과 3은 생성자이고 0과 2는 생성자가 아니다.
• 그룹 G의 원소 a의 거듭제곱으로 만든 집합 S는 G의 Subgroup이다. 닫힘성과 역원을 만족하기 때문이다.
• 이 Subgroup을 subgroup generated by a 라고 하고 $<a>$ 라고 쓴다.

예시

$<Z_4, +>$ 그룹 H에 대해

• $[0]^1 = [0]^2 = [0]^3 = [0]^4 \rightarrow <0> = \{0\}$
• $[1]^1 = [1], [1]^2 = [2], [1]^3 = [3], [1]^4 = [0] \rightarrow <1> = \{0, 1, 2, 3\} = Z_4$

 

Order of Elements

그룹 G에 속한 원소 a에 대해, order of a는 ord(a)라고 쓰고 |<a>| 와 같다. (만약 |<a>|의 수가 유한하다면, a는 infinite order가 된다)

 

• ord(a)= n이라고 했을 때 
• k 가 정수이고 $a^k = e$라면 n | k이다 (n은 k를 나눈다.)
• 만약 a를 거듭제곱해도 절대로 항등원 e가 나오지 않으면 infinite order
• ex) $Group <Z_4, +>$
  • ord[1] = 4(n), $[1]^{4(k)} = e$ 이고 4(n)는 4(k)를 나눈다.
  • ord[2] = 2(n) $[2]^{4(k)} = [8] = [0] = e$ 이고 2(n)는 4(k)를 나눈다.

 

Cyclic Group의 성질

그룹 G가 Cyclic Group이라고 하자,

• |G|가 무한하다면 G는 $<Z, +>$ 와 isomorphic(동형) 이다.
• |G|가 유한하고 1보다 크다면 ㅎ는 $<Z_n, +>$ 와 isomorphic(동형) 이다.

모든 cyclic group의 subgroup은 cyclic이다.

 

 

Lagrange Theorem (라그랑주의 정리)

만약 크기가 n인 유한한 그룹 G가 있고, H가 크기가 m인 G의 subgroup이라면 m은 n을 나눈다.

-> 모든 subgroup의 크기가 group 전체의 크기를 나눈다.

 

예시

• $Z_8$ 이 있을 때 그룹의 크기는 {0, 1, 2, 3, 4, 5, 6, 7} = 8이다.
• cyclic group <2> 는 2에 의해 생성된 subgroup이며 크기는 {0, 2, 4, 6}  = 4이다.
• => 4는 8을 나눈다.

유한군 G의 원소 a의 크기 (ord(a))는 |G|의 약수이다.

 

모든 소수 크기의 그룹은 cyclic group이다.

 

• 소수 p를 선택하고 원소의 수가 |G| = p인 그룹 G를 가정한다.
• G에 속한 항등원 e가 아닌 원소 g를 선택한다. <g>의 크기는 1보다 크다.
• |<g>|  <= |G| 이고 라그랑주의 정리에 의해 |<g>|는 p를 나눈다.
• |<g>|는 1또는 p이다. -> g가 군 G의 모든 원소를 생성할 수 있다.
• 따라서 소수 크기의 그룹은 항상 하나의 원소로 모든 원소를 생성할 수 있는 cyclic group이다.

$<Z_{15}^* \ , \ \cdot>$

• 15와 서로소인 원소만 가지고 있으며 크기는 8이다.
• ord(2) = 4
• ord(4) = 2
• 4, 2모두 8의 약수이므로 라그랑주의 정리를 만족한다.
• generator가 없으므로 cyclic group이 아니다.

$<Z_5 \ , \ +> $ ❘Z❘ = 5

• 그룹의 크기가 소수일경우 항등원을 제외한 모든 원소들이 generator가 된다.
• 1, 2, 3, 4 모두 생성자가 될 수 있다.

 

Euler Theorem (오일러 정의)

1보다 큰 양의 정수 n과 정수 a가 서로소라면 (gcd(a, n) = 1)
$a^{\phi(n)} \equiv 1 \ (mod \ n )$

 

• 15와 서로소인 테이블에서, $\phi(15)$ = 8번 거듭제곱을 하면 1이 나온다.

 

Fermat (Little) Theorem (페르마의 소정리)

p가 소수이고 a가 정수일 때 $a^p \equiv a \ (mod \ p )$가 성립한다.
a를 p번 거듭제곱하고 p로 나눈 나머지는 a와 같다.

 

a와 p가 서로소일 때 $Z_p^*$에 속하는 모든 a에 대해

$$ a^{p-1} \equiv 1 \ (mod \ p ) $$

• a를 p-1번 거듭제곱한 후 p로 나눈 나머지가 항상 1이다.
• ex) $<Z_{11}^*, \ \cdot> 에 대해

• a를 10번 거듭제곱하고 11로 나눈 나머지가 항상 1이라는 것을 볼 수 있다.
• a를 11번 거듭제곱하고 11로 나눈 나머지는 자기 자신이 된다.

 

 

---

# of Genarators (생성자의 수)

만약 p가 소수라면

• $Z_p^*$는 p -1 크기를 가진 cyclic group이다.
• $Z_p^*$의 생성자의 개수는 $\phi(p -1)$ 개 이다.
• ex) $Z_{11}^*$ 에는 10개의 원소를 가지고 있고 생성자의 개수는 $\phi(10)$ = 4이다.

2, 6, 7, 8만 모든 원소를 생성한다.

 

Discrete Logarithm (이산로그의 정의)

g를 $Z_p^*$의 고정된 생성자(fixed generator)라고 하자
$Z_p^*$에 속한 원소 a에 대해 고유한 정수 r이 존재하여
$$ a \equiv g^r \ (mod \ p) $$
를 만족한다.
-> a가 생성자 g의 거듭제곱으로 표현될 수 있다. (g를 r번 거듭제곱 한 후 나머지가 a)

 

• 이 r은 이산로그라고 불리며 a가 $g^r$로 표현될 때의 지수이다. $ind_{p, q}(a)$
  • ex) p = 11, g = 2일 때 a가 8이라면
  • $8 \equiv 2^r \ (mod 11) $
  • r = 3이므로 $ind_{2, 11}(8) = 3$ 

$<Z_{11}^*, \cdot>$ 테이블

• 각 원소는 유일한 지수를 가지고 있다. -> 생성자를 사용했기 때문에
• $2^5 \ (mod \ 11 ) = 10$, $ind_{11, 2}(10) = 5$
• mod 11에서 10을 만드는 생성자 2의 지수 r을 구하는게 목표

Discrete Log Problem (DLP)

p, g, a가 주어지고 $ind_{p, g}(a)$ 값을 구하는 문제
같은 값에 대한 r이 여러개 나올 수 있어 r값 유추가 어렵다.
결정론적 다항(P) 시간에 해결할 수 있는지에 대한 명확한 답이 없어 NP문제로 분류된다. 

• RSA 알고리즘에 사용된다.