algo_lec23

 

Number theory basics

• If G=(S,⊕) is a group, S'⊂S, and G' = (S,⊕) is also group, G' is subgroup of G
• Also, if S'≠S, G' is a proper subgroup of G
• Examples
  • Z: integers, E: even integers, (E,+) is subgroup of (Z,+)
• For G=(S,⊕), we have an inverse element a' for a∈S and define a^k and a^(-k) (for non-negative integer k)
  • a^0=e
  • a^k=a⊕a⊕...⊕a(k a's)
• Also, we have G=(S,⊕) and subgroup S'⊆S. Then, if a⊕b∈S' for all a,b∈S', S' is closed for ⊕.

---

• Theorem. For finite group G=(S,⊕), we have a closed subgroup (but not empty set) S'⊆S, (S,⊕) is a subgroup of G.
• Theorem. For finite froup G=(S,⊕) and its subgroup G' = (S',⊕), |S'| is a divisor of |S|. Also, if G' is a proper subgroup of G, |S'| ≤ |S|/2. 
• Example
• For (Z_12.+). S'=(0,3,6,9}. Then, (S',+) is a subgroup of (Z_12,+). Then, |S'|=4. |Z|=12 so 4 is a divisor of 12.

 

---

• <a>
  • For finite group G=(S,⊕) and a∈S, define <a> as follows
    • <a> = {a^k | k≥1 integers}
    • <a> is closed for ⊕, (<a>,⊕) is a subgroup of G. This is a subgroup generated by a. If subgroup G is generated by a, a is a generator of G.
  • Example
    • For group (Z_8,+), when a=2, <2> = {2,2+2,2+2+2,2+2+2+2,2+2+2+2+2...} = {2,4,6,0,2,4,6,...} = {2,4,6,0}

---

• ord(a)
  • In the previous slide, when generating subgroups, once the identity element is generated, duplicates appear thus, it is unnecessary to continue generating attributes after getting the identity element.
  • To mark this, we use an order of 𝑎 with the notation ord 𝑎 , the minimum positive integer 𝑡 s.t. 𝑎^𝑡 = 𝑒.
  • Thus, 𝑎 = {𝑎^1 , 𝑎^2 , 𝑎^3 , ⋯ , 𝑎^𝑡}

이전 슬라이드에서 부분군을 생성할 때, 한 번 항등원 e가 나오면 이후에는 이미 생성된 원소들이 반복되므로, 항등원을 얻은 뒤에는 더 이상 원소를 계속 생성할 필요가 없습니다.

이를 표시하기 위해, 원소 a의 차수(order) 를 ord(a)로 표기하는데, 이는 a^t = e를 만족하는 최소의 양의 정수 t를 뜻합니다.

따라서 ⟨a⟩={ a^1, a^2, a^3, …, a^t }.

• Theorem. For finite group G=(S,⊕) and a∈S, t=ord(a). Then, subgroup <a> generated by a consists of distinct t attributes as follows. 𝑎^1 , 𝑎^2 , 𝑎^3 , ⋯ , 𝑎^𝑡(= e)

유한군 G=(S,⊕)와 a∈S에 대하여, t=ord(a)라 하면, a에 의해 생성된 부분군 ⟨a⟩는 서로 다른 t개의 원소로 이루어지며, 𝑎^1 , 𝑎^2 , 𝑎^3 , ⋯ , 𝑎^𝑡(= e)로 구성된다.

• Example:
  • For group (Z_8,+), <2>={2,4,6,0}, <4>={4,0}, <1>={1,2,3,4,5,6,7,0}=Z_8. Thus, 1 is a generator of Z_8.
  • For group (Z_9*,x), Z_9* = {1,2,4,5,7,8}. <4>={4,7,1}, <2>=Z_9*.
    • <4>={4,7,1}
      • 4, 4x4=16(7), 7x4=28(1)
    • <2>={1,2,4,5,7,8}
      • 2,2x2=4,2x2x2=8,8x2=16(7),16x2=32(5), 52=10(1)
    • Thus 2 is a generator of Z_9*.
    • The number of attributes in <2> is ord(2) which is 6. ⟨2⟩의 원소 개수는 ord(2)=6

---

• Theorem. G=(S,⊕) is a finite group with identity element e. Then, for all a∈S, a^|S|=e.
  • (Note that |S| is the number of attributes in S)
  • proof
    • we know that the number of attributes in subgroup <a> (generated by) a is ord(a).
    • Thus, k s.t. |S|=ord(a) x k exists.
      • ord(a) 이후론 계속 반복되므로, 그 배수가 결국 S 집합의 사이즈
    • Hence, a^|S| = a^ord(a) x k= e^k = e.
• Euler's Theorem
  • When n>1, for all a∈Z_n*, a^𝜙(𝑛) ≡ 1 (mod n)
    • The number of attributes in Z_n*
    • a and n are coprime

---

• Fermat's little theorem
  • when p is a prime, for all a∈Z_p*, a^(p-1) ≡ 1 (mod p)
  • [proof] By Euler/s Thm. and if p is a prime, 𝜙(p) = p-1. p와 서로소의 개수
• Example

1부터 9까지 정수 9개 중에서 3의 배수는 3, 6, 9 이렇게 3개니까, 9개 중 3개가 3의 배수인 셈이죠.
따라서 배수의 비율은 3/9=1/3이고,

서로소인 수(3의 배수가 아닌 수)의 비율은 1−1/3이 되는 겁니다.

그래서 ϕ(9)=9×(1−1/3)=9×2/3=6 이렇게 계산하는 거예요.

---

뭘 구하고자 하는 거지?
이 정리들로 “큰 거듭제곱을 모듈로(n) 연산한 뒤 나머지가 무엇인지” 혹은
“모듈로 곱셈에서 역원을 어떻게 구할 것인지”를 손쉽게 알아낼 수 있습니다.

---

• Primitive root

• For some g ∈ Z*n, if ord(g) = |Z*n*|, all the attributes in Z*n can be generated by g. Then, g is called a primitive root of Z*n.
• For example, for Z*15, ord(2) = 4, ord(4) = 2. For Z*11, ord(2) = 10, ord(3) = 5.
      Z*15 = {1,2,4,6,7,8,9,10,11,12,13,14}  (15와 서로소)
      Z*11 = {1,2,3,4,5,6,7,8,9,10}         (11과 서로소)
      2, 2×2 = 4, 4×2 = 8, 8×2 = 5, 5×2 = 10, 10×2 = 20(9), 9×2 = 18(7), 7×2 = 14(3), 3×2 = 6, 6×2 = 12(1), thus ord(2) = 10
    For Z*15, no primitive root. For Z*11, 2,6,7,8 are primitive roots.

 

1. 원시근(primitive root)이란?
배경: Zn∗는 “모듈로 n 곱셈군”(단위원이 1인 아벨 군)으로, 원소 개수는 ϕ(n)입니다.
정의: 어떤 g∈Zn∗에 대해 ord(g)= |Zn∗|=ϕ(n)이면, g의 거듭제곱으로 군의 모든 원소를 생성할 수 있으므로, 
         ⟨g⟩={ g1, g2, …, gϕ(n)=1}=Zn∗. 이때 g를 Zn∗의 원시근(primitive root)이라 부릅니다.

군 G=(S,⊕)에서 원소 a∈S의 차수(order) ord(a)는 a^t = e(항등원) 을 만족하는 가장 작은 양의 정수 t 입니다.

2. 예제1: Z15∗에는 원시근이 없다
ϕ(15)=15 (1−1/3)(1−1/5)=15⋅2/3⋅4/5=8
그러므로 Z15∗의 크기는 8이고, 그 원소는{1,2,4,7,8,11,13,14}.

각 원소의 차수(ord)를 계산해 보면
ord(2): 2^1=2,  2^2=4,  2^3=8,  2^4=16 ≡ 1(mod15) → 차수=4
ord(4): 4^1=4,  4^2=16 ≡ 1 → 차수=2 (나머지 원소들도 최대 차수가 4 이하로, 8이 될 수 없음)

결론: 아무 원소도 차수 8을 갖지 않으므로 Z15∗는 순환군이 아니며, primitive root이 존재하지 않는다.

3. 예제2: Z11∗에는 원시근이 있다
11은 소수이므로 ϕ(11)=10.
Z11∗={1,2,3,4,5,6,7,8,9,10}.

2의 차수 계산: 2^1=2, 2^2=4, 2^3=8, 2^4=16≡5(mod11), 2^5=5⋅2=10, 2^6=10⋅2=20≡9, 2^7=9⋅2=18≡7, 2^8=7⋅2=14≡3, 2^9=3⋅2=6, 2^10=6⋅2=12≡1.
→ ord(2)=10=ϕ(11). 따라서 2는 Z11∗의 원시근이다.

3의 차수 계산(비교): 3^1=3,  3^2=9,  3^3=27≡5,  3^4=5⋅3=15≡4,  3^5=4⋅3=12≡1
→ ord(3)=5<10, 원시근이 아님.

---

• Discrete logarithm problem
  • When 𝑔 is a primitive root of Ζ𝑛 ∗ and 𝑎 ∈ Ζ𝑛 ∗ , there exists a positive integer 𝑥 s.t. 𝒈^𝒙 ≡ 𝒂 (𝐦𝐨𝐝 𝒏). Then, 𝑥 is called discrete logarithm of 𝑎 mod 𝑛 for 𝑔. It is difficult to find 𝑥.
  • Given difficulty to solve, discrete logarithm problem is used for public key cryptographic and symmetric key cryptographic algorithms.

이산 로그 문제

g가 Zn∗의 원시근(primitive root)이고, a∈Zn∗일 때 g^x≡a (mod n)를 만족하는 양의 정수 x가 존재한다.
이때 x를 “g에 대한 a의 모듈러 n 이산 로그(discrete logarithm)”라고 부르며, 이를 구하는 것은 매우 어렵다.
이러한 난이도 덕분에, 이산 로그 문제는 공개키 암호와 대칭키 암호 알고리즘의 보안 기반으로 널리 사용된다.

---

Euclid (or Euclidean) algorithm

• GCD (Greatest Common Divisor)
  • Notation: For r0,r1, (at least one of them should not be 0), GCD(r0,r1)
  • GCD(r0,0)=r0
• Coprime
  • For r0,r1 (at least one of them should not be 0), if GCD(r0,r1)=1, r0,r1 are coprime.
• Euclidean Algo.
  • Efficiently Compute GCD without coprime factorization
  • For two integers r0 and r1 (0≤r1<r0), if r0=qxr1+r2, GCD(r0,r1)=GCD(r1,r2)
  • Then, q and r2 are integers and r1>r2.
    • GCD(r0,r1)=GCD(r1,r2)=GCD(r1,r0 mod r1)

소인수 분해 없이 최대공약수를 효율적으로 계산하는 방법

두 정수 r0,r1 (0≤r1<r0​)에 대해 r0=q×r1+r2 라고 하면 GCD(r0,r1)=GCD(r1,r2)
여기서 q와 r2는 정수이고, r1>r2

따라서 GCD(r0,r1)=GCD(r1,r2)=GCD(r1, r0  r1).

• Euclid algo. example
  • If r0=75, r1=20, find GCD using Euclid algo.
    • 75=3x20+15
    • 20=1x15+5
    • 15=3x5+0
    • GCD(75,20)=GCD(20,15)=GCD(15,5)=5

---

Euclid algorithm

Show that GCD(A,B)=GCD(B, A mod B)=GCD(B,R)=G.

1. 가정 및 기호 정리
G=gcd⁡(A,B)라 하자. 그러면 A와 B를 G로 나누면 서로소인 몫 a,b를 얻는다: A=Ga,B=Gb, gcd⁡(a,b)=1. 

2. 나눗셈 알고리즘 적용
A를 B로 나눈 나머지를 R이라 하면, A=Bq+R ⟹ R=A−Bq. 여기에 A=Ga, B=Gb를 대입하면, R=Ga−Gbq=G(a−bq). 

3. gcd⁡(B,R)구하기
gcd⁡(B,R)=gcd⁡(Gb, G(a−bq))=G  gcd⁡(b,  a−bq). 
따라서 gcd⁡(B,R)=G이 되려면 gcd⁡(b,  a−bq)=1이어야 합니다.

4. gcd⁡(b,  a−bq)=1임을 보이는 반증법 proof by contradiction
반대 가정: gcd⁡(b,  a−bq)=m>1이라 하자. 그러면 b=mk, a−bq=m k′인 정수 k,k′가 존재한다.
두 번째 식에서 a=bq+m k′이므로, 첫 번째 식을 써서 a=mkq+m k′=m (kq+k′).
따라서 a도 m의 배수가 되어 a와 b가 공약수 m>1을 가지게 됩니다.
이는 gcd⁡(a,b)=1이라는 처음 가정에 모순이므로, 반대 가정이 잘못되었다는 결론이 나옵니다.

5. 결론
따라서 gcd⁡(b,  a−bq)=1이 성립하고 gcd⁡(B,R)=G⋅1=G이 되어 gcd⁡(A,B)=G=gcd⁡(B,R).
이로써 “나머지를 이용한 유클리드 알고리즘”의 핵심 정리 gcd⁡(A,B)=gcd⁡(B, A  B)가 증명됩니다.

---

Extended Euclidean Algo.

• Extend the Euclidean algo. to find the inverse element in public key cryptographic system
• GCD can represent as linear combination of two integers
  • if d=gcd(r0,r1), there exists integer s,t s.t. d=gcd(r0,r1)=sxr0+txr1, s,t∈Z.

• Find the inverse element using an extended Euclidean algo.
  • if a and n are coprime, gcd(a,n) = 1 and there exists integer x,y s.t. ax+by=1
  • If we take (mod n) on both sides of ax+ny=1, ax ≡ 1 (mod n).
  • Therefore, x is the inverse element of a by an extended Euclidean algo.

확장 유클리드 알고리즘을 이용한 역원(inverse element) 구하기

a와 n이 서로소이면 gcd⁡(a,n)=1이고, 정수 x,y가 존재하여 ax+by=1을 만족합니다.
이 등식의 양변을 모듈로 n 연산하면 ax ≡ 1 (modn)이 되어, 따라서 x가 a의 모듈로 n곱셈에 대한 역원입니다.

• Example: Find the inverse element of 5 for (Z*7,x)
  • X*7={1,2,3,4,5,6}
  • gcd(5,7)=1 so ax+ny=1, 5x+7y=1 (by extended euclidean algo.) by taking (mod 7), 5x ≡ 1 (mod 7)
  • x=3

아래는 확장 유클리드 알고리즘을 이용해 (Z7∗,×)에서 [5]_7의 역원을 구하는 예제입니다.

1. 유클리드 호제법으로 GCD 계산
7=5×1+2
5=2×2+1
2=1×2+0
최종 나머지가 1이므로 gcd⁡(5,7)=1임이 확인됩니다.

2. Bézout 계수 찾기 (역추적)
두 번째 식에서 1=5−2×2. 첫 번째 식 2=7−5×1을 대입하면 1=5−2 (7−5⋅1)=5−2⋅7+2⋅5=3⋅5−2⋅7.

따라서 Bézout 계수는 x=3,  y=−2이며, 5⋅3+7⋅(−2)=1

3. 모듈로 연산으로 역원 얻기
5 x+7 y=1⟹5 x ≡ 1(mod7).

여기서 x=3이므로, [5]7−1=[3]7.
결론적으로 Z7∗에서 5의 곱셈 역원은 3입니다.