[TIL]230406 - 컴퓨터시스템보안 6주차: 대수구조(3)

순환 부분군

• 만약 군의 부분군이 어떤 원소의 멱승(power)을 사용하여 생성된다면, 해당 부분군은 순환 부분군임
• 여기서 멱승은 해당 군에 포함된 원소에 군의 연산을 반복적으로 적용한 것을 의미함

임의의 연산(o)를 a에 대해 n번 반복해서 수행함

• 이 과정으로 만들어진 집합을 <a>로 표기
  • 단 집합 내에서 중복된 원소들은 하나의 원소로 취급하며 a^0 = e임

ex1)

군 G = <Z6, +>로부터 네 개의 순환 부분군들이 생성될 수 있다. 그것은 H0 = <{0}, +>, H1 = G, H2 = <{0,2,4}, +>, H3 = <{0,3}, +>이다. 모든 군에 대해서 정의된 연산은 모듈러 6의 덧셈이다.

• a^n 연산의 의미
• a를 n번 더한 것 -> a^n = a + a + ... + a (n times)

1. 군 G = <Z6, +>로부터 네 개의 순환 부분군을 어떻게 생성하는가?
2. 상기의 H0, ..., H3는 G의 순환 부분군임을 어떻게 확인할 수 있는가?

• H0: 원소 0 ∈ Z6을 이용해 생성되는 순환 부분군

  • 모듈러 덧셈 연산의 항등원인 {0}만 원소로 갖는 집합이며, Z6의 부분집합
  • 따라서 H0는 원소로 {0}만 갖는 순환 부분군

• H1: 원소 1 ∈ Z6을 이용해 생성되는 순환 부분군

  • 원소의 집합은 {0, 1, 2, 3, 4, 5}며 이는 G의 Z6과 동일함
  • 원소 1을 이용해 생성되는 순환 부분군 H1은 G와 동일 -> H1 = G
    

• H2: 원소 2 ∈ Z6을 이용해 생성되는 순환 부분군

  • 원소의 집합은 {0, 2, 4}며 이는 G의 원소 집합 Z6의 부분 집합임
  • 원소 2을 이용해 생성되는 순환 부분군 H2은 G의 순환 부분군
    

• H3: 원소 3 ∈ Z6을 이용해 생성되는 순환 부분군

  • 원소의 집합은 {0, 3}며 이는 G의 원소 집합 Z6의 부분 집합임
  • 원소 3을 이용해 생성되는 순환 부분군 H2은 G의 순환 부분군
    

• H4: 원소 4
  Z6을 이용해 생성되는 순환 부분군

  • 원소의 집합은 {0, 4, 2}며 이는 G의 원소 집합 Z6의 부분 집합임
  • 그러나 H2의 집합과 동일함
  • 따라서 원소 4를 이용해 생성되는 순환 부분군 H4는 새로운 부분군이 아님
    

• H5: 원소 5 ∈ Z6을 이용해 생성되는 순환 부분군

• 원소의 집합은 {0, 1, 2, 3, 4, 5}며 이는 G의 원소 집합 Z6와 동일

• 따라서 원소 5를 이용해 생성되는 순환 부분군 H5는 H1과 동일한 군으로 새로운 부분군이 아님
  

ex2)

• 군 G = <Z'10, x>로부터 세 개의 순환 부분군들이 생성될 수 있다. 그것은 H1 = <{1}, x>, H9 = <{1,9}, x>, H3 = G이다. 이때, 모든 군에 대해서 정의된 연산은 모듈러 10의 곱셈이다.

• a^n 연산의 의미

  • a를 n번 곱한 것 -> a^n = a x a x ... x a (n times)

• Z'10은 어떤 집합인가?

  • Z10에서 곱셈에 대한 역원이 존재하는 원소로만 구성된 집합
  • Z'10 = {1, 3, 7, 9}

• H1: 원소 1 ∈ Z10을 이용해 생성되는 순환 부분군 H1

  • 모듈러 곱셈 연산의 항등원인 {1}만을 원소로 갖는 집합이며, 이는 z'10의 부분집합임
  • H1은 원소로 {1}만을 갖는 순환 부분군임
    

• H3: 원소 3 ∈ Z10을 이용해 생성되는 순환 부분군 H3

  • 원소의 집합은 {1, 3, 7, 9}이며, 이는 군 G의 Z'10와 동일함
  • 원소 3을 이용해 생성되는 순환 부분군은 G와 동일함 -> H3 = G
    

• H7: 원소 7 ∈ Z10을 이용해 생성되는 순환 부분군 H7

  • 원소의 집합은 {1, 3, 7, 9}이며, 이는 군 G의 Z'10와 동일함
  • 원소 7을 이용해 생성되는 순환 부분군은 G와 동일함 -> H7 = G
    

• H9: 원소 9 ∈ Z10을 이용해 생성되는 순환 부분군 H9

  • 원소의 집합은 {1, 9}이며, 이는 군 G의 Z'10의 부분집합임
  • 원소 9을 이용해 생성되는 순환 부분군 H9는 G의 순환 부분군임
    

---

순환 군과 생성원

순환 군

• 그 자신이 하나의 순환 부분군인 군
• ex1) 군 G = <Z6, +>
  • H1, H5: 그 자신이 하나의 순환 부분군과 동일함
    -> 순환 군
• ex2) 군 G = <Z'10, x>
  • H3, H7: 그 자신이 하나의 순환 부분군과 동일함
    -> 순환 군

생성원

• 순환 군 의 생성원: G의 집합의 원소 중에서 G와 동일한 순환 부분군을 생성하는 원소
• ex1) 군 G = <Z6, +>
  • H1, H5: 그 자신이 하나의 순환 부분군과 동일함
    -> 생성원: 1, 5
• ex2) 군 G = <Z'10, x>
  • H3, H7: 그 자신이 하나의 순환 부분군과 동일함
    -> 생성원: 3, 7

원소의 위수(order)

• 군 G에 대한 원소 a의 위수
  • 군 G의 집합을 구성하는 원소 a에 대해, a^n = e를 만족하는 가장 작은 정수 n
    • e: 군 G에서 정의된 연산에 대한 항등원 (+: 0, x: 1)
• a^n은 a의 n제곱이 아님에 유의
  • 임의의 연산을 a에 대해 n번 수행
• 원소의 위수 = 그 원소가 생성하는 순환 군의 위수

  cf) 군의 위수: 집합의 크기 (집합 안의 원소의 개수)

ex1)

• 군 G = <Z6, +>에서 원소 a에 대한 위수
• Z6 = {0, 1, 2, 3, 4, 5}이므로 0~5 각각에 대한 위수는

• 의미: 원소 a를 n번 더한 후 6으로 나누었을 때 나머지 값이 항등원 e(=0)으로 다시 되돌아오는 데 필요한 n 값 중 최솟값
  • 원소 a가 생성하는 순환 군의 위수와 같음

ex2)

• 군 G = <Z'10, x>에 대한 위수
• Z10 = {1, 3, 7, 9}이므로 각각에 대한 위수는
  

• 의미: 원소 a를 n번 곱한 후 10으로 나누었을 때 나머지 값이 항등원 e(=1)로 다시 되돌아오는 데 필요한 n 값 중 최솟값
  • 원소 a가 생성하는 순환 군의 위수와 같음

---

환 (Ring)

R = <Set, Operation1, Operation2>

• 첫 번째 연산(Operation1, o): 가환 군(아벨 군)에 대해 요구되는 다섯 가지 성질 (닫힘, 결합 법칙, 항등원 존재, 역원 존재, 교환 법칙)을 모두 만족해야 함

• 두 번째 연산(Operation2, ㅁ): 군(Group)에 요구되는 닫힘 성질과 결합 법칙을 만족하고, 첫 번째 연산과 함께 수행될 때 분배 법칙을 만족해야 함

  a ㅁ (b o c) = (a ㅁ b) o (a ㅁ c)

• 가환 환: 두 번째 연산에 대해 교환 법칙을 추가로 만족하는 환

첫 번째 연산: +(-)
두 번째 연산: x
-> 나눗셈은 닫힘 성질을 만족하지 않기 때문에 불가능함

환을 이루는 공간에서 덧셈(뺄셈)/곱셈 모두 수행 가능
cf) 군 (Group)은 하나의 군에서 하나의 연산만 수행 가능