[정수론 기초] algo_lec25

1. ⟨a⟩ 정의

• ⟨a⟩={ak∣k≥1인 정수}
• ak는 a⊕a⊕⋅⋅⋅⊕a를 k번 반복한 것

2. subgroup 성질

• 닫힘성(closed under ⊕):
  임의의 두 원소 ai,aj∈⟨a⟩에 대하여 ai⊕aj=a i+j 역시〈a〉에 속하므로 closed.
• 항등원(identity):
  군 G의 항등원 e는 e=a^k 형태로 나타나진 않더라도, 〈a〉에는 “k=0”를 허용해서 a^0=e를 포함시키기도 하고, 아니면 “k≥1” 사이클을 돌면서 결국 항등원에 도달합니다.
• 역원(inverse):
  a의 역원 a^(-1) 역시 어떤 거듭제곱 a^m로 나타낼 수 있으므로 〈a〉에 들어 있습니다.

3. 생성원 (generator)

만약 이 부분군 〈a〉가 원래 군 G 전체와 같다면—즉 ⟨a⟩=G,

—그때 우리는 “a가 G를 생성한다”라고 하고, a를 G의 생성원(generator) 혹은 원시원(primitive element) 이라고 부릅니다.

 

4. 예시

지수 k	계산과정	결과 3^k mod 7
1	3^1 = 3	3
2	3^2 = 9, 9 mod 7 = 2	2
3	3^3 = 3^2*3 = 2*3 = 6, 6 mod 7 = 6	6
4	3^4 = 3^3*3 = 6*3 = 18, 18 mod 7 = 4	4
5	3^5 = 3^4*3 = 4*3 = 12, 12 mod 7 = 5	5
6	3^6 = 3^5*3 = 5*3 = 15, 15 mod 7 = 1	1

 

• Z7∗​={1,2,3,4,5,6}에서
• 예를 들어 a=3이면, ⟨3⟩={3,2,6,4,5,1}=Z7∗={3,2,6,4,5,1}
  이 경우 3는 Z7∗​의 생성원입니다.

---

 

 

1. 〈2〉의 정의

⟨2⟩  =  { k⋅2∣k=1,2,3,… }

여기서 “k⋅2”는 덧셈 연산으로 “2를 k번 더한다”는 뜻이고, mod 8을 취한 값으로 생각합니다.

 

2. 실제 계산

1. k=1일 때:1⋅2=2(mod8)  ⟶  2. 
2. k=2일 때:2⋅2=2+2=4(mod8)  ⟶  4. 
3. k=3일 때:3⋅2=2+2+2=6(mod8)  ⟶  6.
4. k=4일 때:4⋅2=2+2+2+2=8≡0(mod8)  ⟶  0. 
5. k=5 이상부터는 이미 나온 값을 반복합니다:5⋅2=10≡2(mod8),6⋅2=12≡4,7⋅2=14≡6,8⋅2=16≡0,  … 

따라서 〈2〉을 무한히 늘려 써 보면, { 2,4,6,0,2,4,6,0,… }  =  {0,2,4,6}.

 

3. 결론

⟨2⟩={0,2,4,6}

이는 Z8에서 “짝수 원소들”로 이루어진 부분군이며, 2를 덧셈으로 반복해서 얻을 수 있는 모든 원소의 집합입니다.

---

 

군 G=(S,⊕)에서 어떤 원소 a를 반복 연산으로 집어넣다 보면, 결국 “항등원” e가 다시 나오게 되는 시점이 있습니다. 이때 “언제 e가 처음 나오는가”를 재는 것이 바로 원소 a의 위수(order), 즉 ord(a)입니다.

 

1. 위수( order )의 정의

• ord(a)는 가장 작은 양의 정수 t로서 a^t = e가 성립하는 t입니다.
  (여기서 a^t 는 군 연산 ⊕를 t번 반복한 것을 뜻해요.)
• “가장 작은” 조건 덕분에, a^1,  a^2,  a^3,  …,  a^(t−1)  ,  a^t=e까지 전부 서로 다른 원소들이고,
  그 이후 a^(t+1)=a, a^(t+2)=a^2 … 처럼 순환됩니다.

 

2. 위수와 생성부분군의 크기

• 원소 a가 생성하는 부분군
  ⟨a⟩={a1,a2,a3,… }은 결국{ a1,a2,…,at−1,at=e}로 크기 t인 유한집합이 됩니다.
• 정리하면∣⟨a⟩∣=ord(a) . 즉, a를 계속 곱해서(또는 더해서) 더 이상 새로운 원소가 안 나올 때까지의 단계 수가 곧 ord(a)이며, 그만큼이 〈a〉의 원소 개수입니다.

 

3. 예시: Z8에서 a=2

• 군 (Z8,+)에서 2^1=2,  2^2=4,  2^3=6,  2^4=0(=e),  2^5=2,… 이므로
  ord(2)=4이고, ⟨2⟩={2,4,6,0}입니다.

 

4. 정리

1. ord(a)(a) = “a^t=e”가 처음 성립하는 가장 작은 t>0.
2. 이 t를 넘으면 앞에 나왔던 원소들이 반복되므로, ⟨a⟩={a1,a2,…,at}로 끝.
3. 따라서 부분군 ⟨a⟩의 크기가 바로 ord(a)입니다.

---

아래 슬라이드는 두 가지 중요한 정리를 요약하고 있습니다. 차례대로 풀어서 설명드릴게요.

---

1. 유한군에서 a^|G|=e가 성립하는 이유

1. 부분군〈a〉와 위수(order)
   • 원소 a가 생성하는 부분군 ⟨a⟩={a1,a2,a3,… }은 결국 “a^t=e”가 처음 되는 최소 양의 정수 t까지의 거듭제곱들로 이루어집니다.
   • 이 t를 ord(a)라고 부르고, |⟨a⟩|=ord(a)입니다.
2. 군 전체의 크와 부분군 크기의 관계
   • 군 G가 유한군이므로, Lagrange의 정리에 따라 |⟨a⟩|  =  ord(a)는∣S∣=∣G∣ 의 약수입니다. 즉, 어떤 정수 k가 있어서∣S∣  =  ord(a)×k.
3. 거듭제곱을 이용한 결론
   • 따라서, a^|S|  =  a^ord(a)×k  =  (a^ord(a))^k  =  e^k  =  e.
   • 이로써 “a를 |S|번 곱하면 항상 항등원 e가 된다”는 결론에 이릅니다.

---

2. 오일러의 정리 (Euler’s theorem)

• RSA 같은 공개키 암호에서는 φ(n)=(p−1)(q−1)일 때, a^φ(n)≡1(modn) 성질이 복호화의 핵심이 됩니다.

- 직관적 연결

• 첫 번째 정리(유한군에서 a^|G|=e)는 “군의 크기”를 지수로 거듭제곱했을 때 항등원이 된다는 일반적인 군 이론 결과입니다.
• 오일러의 정리는 “곱셈 군 Zn∗의 크기 ∣Zn∗∣=φ(n)”라는 사실을 적용한 경우라고 볼 수 있습니다.
  즉, Zn∗자체가 유한군이므로, 위 첫 번째 정리를 그대로 쓰면 a^∣Zn∗∣=a ^φ(n)=e=1(modn). 

---

 

• 소수일 때 φ(p)=p−1이므로 페르마의 소정리가 성립한다.

 

---

 

숫자 k	1	2	3	4	5	6	7	8	9	10	11	12	13	14
gcd⁡(k,15)	1	1	3	1	5	3	1	1	3	5	1	3	1	1
서로소?	○	○	×	○	×	×	○	○	×	×	○	×	○	○

 

따라서, Z15∗​={k∈{1,…,14}∣gcd(k,15)=1}={1,2,4,7,8,11,13,14}.

---

 

• 원시근 g∈Zn∗와 군의 임의 원소 a∈Zn∗가 주어질 때, g^x  ≡  a(modn)를 만족하는 양의 정수 x를 찾는 문제

---

최대공약수

• 적어도 하나는 0이 아닌 두 정수 r0, r1에 대하여 공약수 중 가장 큰 수를 최대공약수라 하며, GCD(r0,r1)로 표시

서로소

• 적어도 하나는 0이 아닌 두 정수 r0,r1에 대하여, GCD(r0,r1)=1을 만족하는 경우

유클리드 알고리즘

• 두 정수 r0와 r1이 r0=q*r1+r2를 만족하면, GCD(r0,r1)=GCD(r1,r2)
• GCD(r0,r1)=GCD(r1,r2)=GCD(r1,r0 mod r1)

확장 유클리드 알고리즘

• 유클리드 알고리즘을 확장하여 공개키 시스템에서 중요한 역원 구하는데 사용
• d=gcd(r0,r1)=s*r0+t*r1
• 만약 두 정수 a와 n이 서로소라면, gcd(a,n)=1이고, ax+ny=1인 정수 x,y가 존재
• ax+ny=1의 양변에 mod n을 취하면 ax≡1 (mod n)이 되므로, 두 정수 a,n에 대해 확장 유클리드 알고리즘에 의해 구한 정수 x값은 a의 역원이 된다.