정수론2

1. Group

[덧셈에서의 역원은 더해서 0이되는것, 곱셈에서의 역원은 곱해서 1이되는것. 물론 최종 결과는 모듈러(나머지)정리한것!]
 
1. Group

• Group의 기본 조건: Closure(닫힘성), Associativity(결합법칙), Identity(항등원), Inverse(역원)

2. Abelian Group

• Commutative(교환법칙) 만족하는 group을 Abelian Group이라고 한다.
• <Zn, +>는 abelian group이다.

3. Zn∗ 

• < Zn∗ , *> 은 Abelian Group이다.

4. Order of Group (군의 차수)
: 군 안에 포함된 원소의 개수, ∣G∣ 

• Infinite Order(무한 차수)
• Zn의 차수 : {0,1,2....,n-1} , 집합 크기=n
• Zp∗: 소수 p에 대해, Zp∗는 p와 서로소인 정수 집합을 뜻하며, 이 집합의 차수는 p−1. Z5*={1,2,3,4}, 차수는 5-1=4
• Zn∗의 차수는 오일러 피 함수 ϕ(n). n=10일 때, Z10∗={1,3,7,9}이고, ϕ(10)=4.

5. Properties of Groups (군의 성질)

• 항등원과 역원은 유일하다.(unique)
• 좌측 및 우측 소거법칙이 성립한다. Left/Right- cancellation property. ab=ac→b=c.

2. Subgroup

 
1. Subgroup: group G의 부분집합 H가 G의 연산에 대해 group을 이룬다면, 이를 subgroup이라고 한다.

• 모든 group G는 항등원 {e}와 G 그 자체인 자기자신을 subgroup으로 가진다. → trivial subgroups
• ex) Z6에 대한 subgroup은 {0,2,4} 이다.
• 정수의 덧셈 group Z는 유리수의 덧셈 group Q의 subgroup이며, Q는 실수의 덧셈 group R의 부분군이다.

<Z,+> subgroup of <Q,+> subgroup of <R,+>

 
2. Subgroup 조건(condition)

• H가 G의 Subgroup: Closed, Inverse
• H가 유한집합일 때: H가 G의 이항연산에 대해 closed
• 즉 Subgroup은 closed, inverse, identity e

3. Direct Product of Groups (직접곱)
 

• <G,*>와 <H,∗>가 각각 군일 때, G×H 두 군의 곱을 정의할 수 있다.
• 두 원소 (g1,h1)와 (g2,h2)의 곱셈을 다음과 같이 정의한다:
  • (g1,h1)⋅(g2,h2)=(g1*g2,h1*h2)
• 즉, G와 H에서 각각의 연산을 동시에 수행하는 것

G = &lt;Z2, +&gt; x &lt;Z9*, *&gt;

4. Powers of Elements (원소의 거듭제곱)

• Z4 = {0,1,2,3}, 덧셈연산
  • 3^2=3+3=6 ≡ 2 
  • 3^(-2)=(3^(-1))^2 = 1^2 = 1+1(덧셈연산) = 2
  • 3^2 * 3^(-2) =[2][2] = [4]=[0]=[3]^0(덧셈에선 항등원e가 0이기 때문)=e
• (ab)^n = a^n b^n ?
  • 항상 성립하는 것은 아니고 Abelian(교환법칙)을 만족한다면 해당성질 성립.

3. Homomorphism, Isomorphism

1.Homomorphism (동형사상)

• 그룹 G와 H에 대해 f : G → H일 때, (G의 원소 a,b의 연산에 대해 H에서도 동일하게 반영하는 함수)
  • f(a∘b)=f(a) ∘ f(b)를 만족하는 함수 f를 group의 Homomorphism이라고 한다.
• Endomorphism(자기 동형사상) : 정의역과 공역이 동일한 경우. 즉 그룹 G에서 자기자신으로 가는 동형사상
• Automorphism(자기 동형) : 역원을 가지는 자기동형사상. 즉 자기동형사상 중에서 역함수 존재. G →G에서 단사, 전사 성질 만족
• 동형사상의 성질

2. Isomorphism (동형)

• 동형사상 f:G→H가 **동형(Isomorphism)**이 되려면, f가 **일대일(단사, injective)**이면서 **전사(onto, surjective)**여야 한다.
• 즉, f가 하나의 원소를 다른 하나의 원소에 매핑하며, 이런식으로 모든 원소가 매핑될 수 있어야 한다.
• 이러한 경우 그룹 G와 그룹 H를 "동형"이다 라고 표현한다. G와 H는 구조적으로 동일하다. 

4. Cyclic Group

 
1. Cyclic Group (순환군)

• 순환군은 그룹 G에 대해, 그룹의 모든 원소를 하나의 원소 x의 거듭제곱으로 표현할 수 있는 그룹.
• 어떤 원소 x∈G가 존재해서 G의 모든 원소 a∈G에 대해 a = x^n(또는 덧셈 군에서는 a=nx)이 되는 군을 순환군이라고 한다. 
• 이 때 x를 generator 또는 primitive element라고 부른다. 
• 무한 순환군은 Z와 동형이며, 유한 순환군은 Zn과 동형이다. 
• 순환군의 subgroup도 순환군이다.

2. Order of Elements (원소의 차수)

• 차수는 group의 원소가 몇 번의 연산을 통해 항등원e에 도달하는지를 나타낸다
  • 그룹 G의 원소 a의 차수는 |<a>| 이렇게 <a>의 크기로 정의되며, ord(a)로 표기한다.
  • 만약 a^n = e가 되는 최소의 양의 정수 n이 존재하면, ord(a)=n이다.
  • 만약 a^n = e가 되는 n이 존재하지 않으면, a는 무한 차수를 가진다.
• a^k = e이면 n이 k를 나눈다. 즉 k는 차수 n의 배수이다.

5. Lagrage Theorem

1. 라그랑주 정리

• 그룹 G가 크기 n을 가지는 유한 그룹이고, 그 subgroup의 크기가 m일 때 m은 n을 나눈다 : m/n
  • 즉, subgroup의 크기 |H|는 항상 group의 크기 |G|의 약수이다.

• 원소의 차수와 group의 크기: 유한 그룹G의 원소 a의 차수 ord(a)는 group의 크기 |G|를 나눈다.
• 소수 차수의 group은 cycle group이다. 
  • G의 크기가 소수 p라면, G는 순환군이다. |G|=p

• 원소의 차수는 그룹의 크기를 나누며, 이를 통해 원소가 몇 번의 연산 후 항등원에 도달하는지 알 수 있다.

6. Euler Theorem

1. 오일러 정리 : group 서로소의 크기에 해당하는 거듭제곱 꼴은 모든 원소에 대해 1로 성립한다. (원소^크기 = 1) 

7. Fermat (Little) Theorem

1. 페르마 소정리

• p가 소수이고, a가 Z의 원소라면 a^p ≡ a (mod p) 성립
• p가 소수이고, a가 Zp*의 원소라면 a^(p-1) ≡ 1 (mod p) 성립 → p와 서로소인 a에 대해 성립.

8. # of Generators

• p가 소수라면 , Zp∗​ (모듈러 p에서의 곱셈군)는 **순환군(cyclic group)**이다.
  • 이 (소수) 순환군의 크기는 p-1이다. 
  • 이 그룹의 generator(생성자)는 오일러 피함수  ϕ(p−1)로 주어진다. (p-1과 서로소인 수의 개수)

서로소랑 생성자는 다른 말이다.

 

9. Discrete Logarithm

1. 이산 로그

• a≡g^r (mod p) : 이를 만족하는 정수 r을 찾는 문제.
• r은 p와 g에 대한 a의 지수로 불리며, ind_{p,g}(a)로 표기.

• 결론적으로, 이산로그의 문제점은 같은값이 나왔는데 여러개가 나올 수도 있다는 것이 문제다. 

10. RSA

1. RSA 암호화 알고리즘 기본 원리

• RSA는 2개의 소수 p와 q를 선택한 후, 이 두 소수로부터 공개키와 개인키를 생성하여 암호화를 수행한다.
  1. 소수 p와 q 선택: 두 소수 p와 q를 선택한다.
  2. 모듈러 n 계산: n = p*q
  3. 오일러 피 함수 ϕ(n) 계산: ϕ(n)=(p−1)×(q−1)
  4. 암호화 지수 e 선택: e는 1<e< ϕ(n) 범위에서 gcd⁡(e,ϕ(n))=1이 성립하는 값으로 선택.
  5. 복호화 지수 d 계산: d는 e*d ≡ 1 (mod ϕ(n))를 만족하는 값이다. 즉 d는 e의  모듈러 ϕ(n)에 대한 역원이다.

•