CSE&MATH

Public Key Cryptography

• 소인수 분해 문제 (Prime Factorization)→RSA
  • n=p×q일 때, p,q를 알아내는 것은 쉽지 않음 (NP-난해).
• 이산로그 문제 (Discrete Logarithm)→ElGamal
  • 주어진 g,y,p에 대해 g^x ≡ y (mod p)를 만족하는 x를 구하는 것 역시 매우 어려움.

이 두 문제의 난이도를 이용해 RSA, ElGamal 같은 공개키 암호가 동작한다.

Key Exchange or Establishment

• 시나리오
  • Alice와 Bob은 카페의 공용 인터넷을 통해 민감한 데이터를 주고받고 싶어하지만, 잠재적인 도청자로부터 통신을 보호해야 합니다. (암호화가 필요합니다!)
  • 그러므로, 그들은 민감한 데이터를 암호화할 key가 필요.
  • 안전하지 않은 채널을 통해 이 키를 어떻게 안전하게 공유할 수 있을까?
  • Diffie-Hellman key exchange protocol
    • By Whitfield Diffie and Martin Hellman
    • Discrete Logarithm problem (y=g^x mod p)
      • even if we know y,g, and p, it is hard to compute x.

Vulnerability of Diffie-Hellman key exchange

• Man-in-the-middle attack

Diffie–Hellman 키 교환이 인증 없이 실행될 때 발생할 수 있는 전형적인 중간자 공격(Man-in-the-Middle Attack) 을 보여줌.

1. Alice → Eve: R1=g^x mod  p

• Alice는 원래 Bob에게 g^x를 보내야 하지만, 네트워크 상에 끼어든 Eve가 가로채서 R1을 자신이 받아 버립니다.

2. Eve → Bob: R2=g^z mod p

• Eve는 자신만의 비밀값 z를 골라 R2  =  g^z mod p를 Bob에게 보냅니다.
• Bob은 이것이 “Alice가 보낸 R1”인 줄 알고 받아들임.

3. Bob → Eve: R3 = g^y mod p

• Bob은 올바로 받은 R2에 자신의 개인키 y를 써서 k2 = g^yz mod  p를 공유키로 삼으려 하지만,
• 이 역시 Eve에게만 전달됩니다.

4. Eve → Alice: R4 = g^z mod p

• Eve는 Bob이 보낸 R3 대신 자신의 R4=g^z (같은 값) 을 Alice에게 다시 보냅니다.

결과: Eve가 양쪽과 개별적인 키를 형성

• Alice–Eve 사이의 공유키:
  Eve는 Alice에게 보낸 R4=g^z와, Alice가 원래 보낸 R1=g^x를 이용해 kAE=(R4)^x=g^zx mod  p를 계산합니다.
• Eve–Bob 사이의 공유키:
  Bob이 받은 R2=g^z와 Bob이 보낸 R3=g^y를 이용해 kEB=(R2)^y=g^zy mod  p를 계산합니다.

이제 Eve는

1. Alice가 보낼 메시지를 kAE로 복호화(eavesdrop)
2. 내용을 읽거나 위조한 뒤
3. 다시 kEB로 암호화(encrypt)하여 Bob에게 전달

Alice와 Bob은 서로가 직접 공유한 키라고 믿지만,

실제로는 Eve와 각각 다른 키를 공유하고 있기 때문에, Eve는 양쪽 통신을 완전히 통제하게 됩니다.

• 방어 대책: 인증(Authentication)
  • Diffie–Hellman 자체는 키 교환만 담당하므로,
  • “상대가 진짜 Alice(또는 Bob)가 맞는지”를 검증해 주는 인증 계층이 필수적입니다.
  • 예를 들어 디지털 서명, 공개키 기반 구조(PKI), 미리 공유된 인증서 등을 이용해
    R1,R2가 진짜 상대방이 보낸 것임을 확인해야 중간자 공격을 막을 수 있습니다.

Diffie–Hellman 키 교환

- 공개 매개변수: 큰 소수 p, 원시근 g.
- 개인키:Alice: a, Bob: b

- 공개키 교환:
Alice → Bob: A=g^a mod p
Bob → Alice: B=g^b mod p
공통 비밀키 계산: K = A^b mod p = B^a mod p = g^ab mod p.

- 취약점:
중간자 공격(Man-in-the-Middle)인증(Authentication)이 없으면 공격자가 둘 사이에 끼어 키를 탈취·변조할 수 있음.

Prime and Primality test

“큰 소수를 어떻게 효율적으로 찾는가”

1. 왜 큰 소수가 필요한가?

• RSA 같은 공개키 암호의 보안 강도는 n=pq에서 p,q가 충분히 큰 소수일 때 유지됩니다.
• 따라서 우리는 임의의 큰 수를 뽑아서 소수 여부(primality)를 확인하는 과정을 반복해야 합니다.

2. 소수 분포와 확률

• π(x)는 “x 이하의 소수 개수”를 뜻하는 함수입니다.
  예를 들어 π(15)=6인데, 그 이유는 {2,3,5,7,11,13} 여섯 개가 15 이하의 소수이기 때문입니다.
• 소수 분포 정리(Prime Number Theorem) 덕분에 lim⁡(x→∞) π(x)/[x/ln⁡x]=1⟹π(x)≈x/ln⁡x로 근사할 수 있습니다.

3. 임의의 수가 소수일 확률

• 1에서 x 사이의 임의 정수가 소수일 확률은 π(x)/x  ≈  1/ln⁡x.
• 예를 들어, x=10^16이라면, ln⁡10^16 = 16 ln⁡10 ≈ 16×2.30 ≈ 36.8이므로, 1/ln⁡(1016) ≈ 1/36.8 ≈ 0.027(≈2.7%).

4. 반복 시도 횟수와 실패 확률

• 한번에 임의의 큰 수를 뽑아도 “소수가 나올 확률”이 1/ln⁡x 정도이므로,
• 예컨대 200번 반복해서 소수가 하나도 안 나올 확률은(1−0.027)^200  ≈  0.004 (≈0.4%)로 매우 낮습니다.
• 따라서 통상 수백 번 정도 무작위 시도 후 “확률적 소수 판정(Miller–Rabin 등)”을 거치면, 충분히 큰 소수를 현실적인 시간 안에 찾을 수 있습니다.

5. 결론

1. 소수 분포 정리를 통해 “큰 수 x에서 소수 밀도는 1/ln⁡x 정도”임을 알 수 있다.
2. 따라서 “임의의 x-비트 수를 뽑아서 소수 판정을 몇 번 반복하면 소수를 쉽게 얻는다”는 전략이 실용적이다.
3. 이 과정을 통해 안전한 RSA 모듈러 n=pq를 구성할 수 있다.

1. 큰 소수 생성 절차

1. 임의의 n-비트 수 N 선택: 2ⁿ의 범위 안에서 무작위로 하나 고른다.
2. 소수 판정 실행: N이 소수인지 확인한다.
3. 반복 또는 완료
   - 소수라면 N을 출력해 끝내고,
   - 합성수면(소수가 아니면) 1번으로 돌아가 다른 N을 골라 다시 판정.

2. 소수 판정(Primality Test) 알고리즘

2-1. Naïve trial division

• 2부터 ⌊N⌋까지 모든 수로 나눠보는 방법
• 시간 복잡도는 대략 O(sqrt(N)) → 입력 크기(비트수) n으로 보면 O(2^n/2)로 지수 시간이므로 실무 불가

2-2. AKS 알고리즘 (2002, R. Agrawal 외)

• 수학적으로 완전 결정론적이고, 다항식 시간에 소수 여부를 판정
• 최초의 순수 다항식 시간 알고리즘으로, 복잡도는 대략 Θ(n^6) (여기서 n은 입력 비트 길이)
• 이론적으로 의미가 크지만, 실제 구현 성능은 Miller–Rabin보다 느림

2-3. Miller–Rabin 알고리즘

• 현재 가장 널리 쓰이는 표준 소수 판정 기법
• 확률적(primality probabilistic) 테스트:
  • 몇 번의 랜덤 기저(base) 테스트를 수행해,
  • “합성수일 확률을 아주 낮게” 만들고,
  • 테스트를 다 통과하면 “거의 확실히 소수”로 간주

Miller-Rabin algo.

1. Fermat's test

Primalith test using Fermat's little theorem

• 만약 p가 소수라면, 임의의 a∈Zp∗에 대해 a^(p−1)  ≡  1 (mod p). 
• 따라서 “a^(p−1) ≡ 1 (mod p)”인 a가 하나라도 나오면 무조건 합성수입니다.

2. 필요충분조건이 아닌 이유: 위음수(Pseudoprime)

• 역(⇐)은 항상 참이 아닙니다.
  즉 “a^(p−1) ≡ 1 (mod p)인 a가 전부였다 → p는 소수다”는 거짓이 될 수 있습니다.
• 예: p=221일 때, 221=13×17인데, 임의의 a (예: a=38)를 골라 보면, 38^220  =1 (mod 221)이 성립합니다.
• 모든 a에 대해 a^(p−1) ≡ 1 (mod p)을 만족해도 합성수인 경우입니다.

3. 그래도 유용한 이유: 확률적 판정

• 합성수이더라도 “a^(p−1) ≡ 1 (mod p)”인 기저(base) a의 개수는 제한적이므로,
• 여러 번 무작위 a를 골라 테스트하면 대다수 합성수는 금세 걸러집니다.
• 즉, “테스트를 여러 차례 통과한 수”는 거의 확실히 소수라 할 수 있는 확률적(primality probabilistic) 방법입니다.

4. 의사코드

boolean primality1(int n)
{
    int a;
    Pick a positive integer a < n at random;
    if (a^(n-1) ≡ 1 (mod n))
        return true;    // Pass
    else
        return false;   // Fail
}

1. 무작위 기저 a 선택
2. 페르마 조건 a^(n−1) mod  n=1검사
3. 하나라도 실패하면 즉시 합성수로 판정
4. k번 모두 통과하면 “소수일 확률 높음”으로 판정

Prime and Primality test

Carmichael 수(Carmichael number)

모든 a에 대해서 primality 검사를 통과하는 아주 예외적인 합성수

• 페르마 소정리에 따르면, 소수 p에 대해 임의의 gcd⁡(a,p)=1인 a는 a^(p−1) ≡ 1 (mod p)을 만족합니다.
• Carmichael 수는 “합성수이면서도” 이 조건을 모든gcd⁡(a,n)=1인 a에 대해 충족시키는 예외적인 수입니다.
  즉, a^(n−1)≡1 (mod n) for all a with gcd⁡(a,n)=1이지만 n은 소수가 아닌 수입니다.

이 때문에 단순한 Fermat 테스트만으로는 Carmichael 수를 걸러낼 수 없어, 페르마 테스트의 “충분조건”이 되지 못합니다.

얼마나 드물게 나타날까?

다음 표는 “10^n 이하의 Carmichael 수 개수” C(10^n)를 보여줍니다:

• 보시다시피 10^21 이하에 약 2천만 개 정도 있지만, 이는 10^21 자체에 비하면 극히 작은 밀도입니다.
• 그래서 “무작위로 큰 수를 뽑아 Fermat 테스트를 돌려도 Carmichael 수에 걸릴 확률은 매우 낮습니다.”

1. 소수인 경우와 합성수인 경우의 통과율 차이

If we just ignore Carmichael numbers,

1. n이 소수라면
   • 페르마 소정리에 의해, 모든 1≤a<n에 대하여 a^(n−1) ≡ 1 (mod n) 
   • 따라서 “테스트를 하면 항상 true(통과)” → 오류 없음(정확도 100%).
2. n이 합성수(Carmichael 수 제외)라면
   • 최대 절반 이하의 a만이 a^(n−1)≡1을 만족
   • 나머지 절반 이상에서는 “Fail(합성으로 올바르게 판정)”
   • 즉, “false positive(합성수를 소수로 잘못 판단)” 확률 ≤ 50%.

2. 확률적 테스트로서의 의미

That is, again it is Probabilistic primality test

• True Positive (실제로 소수인 n에 대해 true 반환)
  • Pr⁡[if n is prime → return true] = 1
• False Positive (합성수인 n에 대해 true 반환)
  • Pr⁡[if n is composite → return true] ≤ 1/2. 

즉, 단 한 번의 테스트로는 “합성수를 소수라 오판할” 위험이 최대 50%라는 확률적 한계가 있지만, 소수는 절대 빠지지 않습니다.

3. 에러 확률을 기하급수적으로 낮추기

To reduce such error rate, we can pick multiple a's and do primality test multiple times

• 여러 개의 서로 다른 기저 a1,a2,…,ak를 골라서 독립적으로 Fermat 테스트를 반복하면, Pr⁡[all k tests pass∣n composite]  ≤  (1/2)^k.
• 예를 들어, k=50이면(1/2)^50=2^(−50)<10^(−17), 사실상 0에 가까운 확률이 되어, 합성수를 소수로 오판할 가능성을 거의 완전히 제거할 수 있습니다.

이 결과는 10,000 이하 숫자에 대해 페르마 테스트를 여러 번 반복했을 때 “합성수임에도 소수로 잘못 통과하는(거짓 양성)” 숫자가 얼마나 줄어드는지를 보여줍니다:

• k=1 (기저 하나만 시험): 8개의 합성수가 소수로 잘못 통과
• k=3 (기저 세 개 시험): 약 5개만 통과
• k=5 (기저 다섯 개 시험): 약 2개만 통과
• k=10 (기저 열 개 시험): 통과하는 합성수 0개 → 완벽하게 걸러냄

즉, 반복 횟수 k를 늘릴수록 “합성수 오판”이 기하급수적으로 줄어들어,

충분한 k만큼 테스트하면 사실상 오류 없이 소수 판정이 가능합니다.

ElGamal Cryptographic system

• Discrete Logarithm Problem
• Also used in digital signature
• 같은 평문을 암호화하더라도 매번 서로 다른 암호문이 생성되어 확률적 특성을 갖습니다. 이는 발신자가 암호문을 생성할 때마다 매번 임의의 난수를 선택하기 때문입니다.

1. 키 쌍 생성 (Key Pair Generation)

1. 큰 소수 p와 그 원시근(primitive root) g를 선택
2. 개인키 x를 {1,2,…,p−2에서 무작위로 골라 비밀로 보관
3. 공개키 y  =  g^x mod p를 계산하고, (p,  g,  y)를 모두에게 공개

2. 암호화 (Encryption)

• 평문: m (단, 0<m<p)
• 매 암호화마다 임의의 난수 k∈{1,2,…,p−2}를 새로 골라 사용

1. C1=g^k mod p 
2. C2=m×y^k mod  p  =  m×(g^x)^k  mod  p  =  m  ×  g^xk  mod  p
3. 최종 암호문은 (C1,  C2) 쌍

확률적 암호화: 매번 다른 k를 골라 C1,C2를 생성하므로, 같은 m이라도 매번 다른 암호문이 나옵니다.

3. 복호화 (Decryption)

1. C1x  =  (g^k)^x=g^kx  mod  p 
2. 이 값의 역원을 곱하면, (C1x)^(−1)  =  g^(-kx) mod p
3. 복호화 식 m=C2  ×  (C1^x)^(−1) mod  p = (m g^kx) × g^(−kx) mod   p=m (mod p)

Example

1. 키 생성 (Key Generation)

1. 공개 매개변수 p=13,g=2
2. 개인키 x=3
3. 공개키 y=g^x mod  p=2^3 mod  13 = 8. 따라서 공개키는 (p,g,y)=(13,2,8).

2. 암호화 (Encryption)

• 평문 m = 11
• 임의 난수 k = 5

1. C1 = g^k mod  p = 2^5 mod  13 = 32  mod 13=6.
2. C2 = m×y^k mod  p = 11×8^5 mod  13 = 10

• 따라서 암호문은(C1, C2)=(6, 10).

3. 복호화 (Decryption)

수신자는 개인키 x=3을 사용하여: m = 10 x (6^3)^(-1) mod 13 = 11 

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. 예시

• 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이므로 페르마의 소정리가 성립한다.

따라서, 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의 역원이 된다.

Number theory and cryptographic algorithms (Part 3)
Spring 2025 Computer Algorithms

Number theory basics

• Zn∗의 원소 개수를 오일러 파이 함수 ϕ(n) "Euler phi function"이라고 부름.

• 여기서 p는 n을 나누는 모든 소수.
• 만약 p가 소수라면, ϕ(p) = p−1.

먼저 n=9일 때, 9를 소인수분해하면, 9 = 3^2.
따라서 “n을 나누는 소수들”은 단 하나, p=3밖에 없다.

Cryptographic Algorithms and Protocols

• 수론은 현대 암호 알고리즘·프로토콜의 핵심 도구.
• 많은 보안 기법이 수론 기반으로 설계됨.
• 이번 강의에서는 다음 두 개의 공개키 암호화 예시를 다룸:
  1. Merkle–Hellman Knapsack
  2. RSA Scheme
• 그 전에 고전적(비대칭 전 키) 방식 먼저 복습.

Symmetric (Private) Key Cryptography

• 앨리스(Alice)와 밥(Bob)이 동일한 비밀 키 K를 공유한다고 가정.
  1. 앨리스가 평문 mm을 EK(m)으로 암호화하여 밥에게 전송.
  2. 밥은 비밀 키 K로 DK(EK(m))=m을 계산하여 복호화.
• 즉, 암호화·복호화에 모두 같은 키를 사용함.
• 예시
  1. Classical algorithms: Caesar, Playfair, Vigenère, Hill cipher, Enigma 등
  2. Modern algorithms: DES, 3DES, AES, SEED 등
• General Goals 디자인 목표
  1. hard - EK(m)만 보고 m이나 K를 알아내기가 어려워야 함.
  2. easy - 주어진 K를 바탕으로 암호화/복호화 연산은 매우 빨라야 함.
• Problems with private key systems 단점
  1. 통신하려면 두 당사자가 안전한 방법으로 동일한 K를 공유해야 함.
  2. 만약 n명이 통신하려면 각 사용자마다 n-1개의 서로 다른 키를 유지해야 함 (총 n(n−1)2개의 키 관리 필요).

Public Key Cryptography

• 1976년 처음 고안된 공개키 암호 방식은 위의 문제를 해결함.
• 각 사용자는 공개키(Public Key)와 비밀키(Secret Key)를 쌍으로 가짐.
• 예) Bob이 Alice에게 메시지 m을 보낼 때:
  1. 밥은 앨리스의 공개키 PA로 EPA(m)을 계산하여 암호문 전송. encrypt
  2. 앨리스는 자기 비밀키 SA로 DSA(EPA(m))을 계산해 복호화. descrypt

• 모든 사용자의 공개키는 공개 디렉터리에 저장될 수 있음.
  • 누구나 해당 디렉터리에서 상대방 공개키를 가져다 메시지 암호화에 사용 가능.
• secret keys는 오직 해당 사용자만 알고 있으므로, 암호화된 메시지는 오직 의도한 수신자만 복호화할 수 있음.

Merkle–Hellman Knapsack Algorithm

• Sum-of-subset problem (or Knapsack problem) : revisited
  • 주어진 양의 정수 집합 S=[a1,a2,…,an]과 목표합 T가 주어졌을 때,
    이진 벡터 V=(v1,…,vn) (vi∈{0,1})을 찾아 ∑ai*vi=T이 되게 한다.
  • 이 문제는 일반적으로 NP-난해(NP-hard).

NP에 속한 임의의 문제 Y를 다항식 시간 환원(polynomial-time reduction)을 통해 X로 변환할 수 있다는 의미

• super-increasing (or simple) knapsack
  • additional restriction to the Knapsack problem
    • S가 “super-increasing sequence” (초가열 수열)이 되어야 함.
  • 즉, ak>∑aj for all 1≤k≤n.

• 예시:
  • S=[1, 4, 11, 17, 38, 73] (super-increasing)
  • 목표합 T1=96,  T2=95
• 해법: 큰 원소부터 차례로 빼나가는 방식
  1. 96: 73? Yes, 96−73=23
  2. 23: 38? 38>23이므로 No
  3. 23: 17? Yes, 23−17=6
  4. 6: 4? Yes, 6-4=2
  5. 2: 남은 원소 [1]만 검사 → 2-1=1 “No solution”
• T2=95도 비슷하게 계산 → 해를 구할 수 있음.
• 아이디어는 이진 메시지를 배낭 문제( knapsack problem )의 해로 부호화함으로써,  
  평문에서 “1”에 대응하는 항목들만 골라 더한 합을 암호문(타깃 합)으로 사용하는 것이다.

• Example (block size=6 bit)
  • (public) Plain text: 1 0 1 0 0 1 / 0 1 1 0 1 0 …
  • (secret) Knapsack: 1 2 5 9 20 43 / 1 2 5 9 20 43 …
  • Target sum: 49 / 27, …
    • 예: 49를 얻기 위해 43 + 5 + 1 = 49
  • 암호문 하나가 49라면, 대응 평문 블록 1 0 1 0 0 1이 됨.
• 공개키 (Public Key): (hard) knapsack 문제에 해당하는 수열 H
• 비밀키 (Secret Key): 대응하는 super-increasing(knapsack) 수열 S

• Transforming a super-increasing knapsack to a hard one

1. a simple Knapsack S=[s1,s2,…,sm] 선택
2. multiplier w와 modulus n을 고르되, n>sm이며 gcd⁡(w,n)=1 (보통 n은 소수)
3. “hard knapsack” H=[h1,h2,…,hm] when hi  =  w*si mod n .
   • 이때 H가 공개키가 되고, S + (w,n)가 비밀키가 됨.

• S=[1, 2, 4, 9], w = 15, n=17
  1. 1×15  mod 17=15
  2. 2×15  mod 17=13
  3. 4×15  mod 17=9
  4. 9×15  mod 17=16
• 따라서 하드 knapsack H=[15, 13, 9, 16]
• 이 H가 공개키(public key).

• Encypting a message (block size=4 bit)
  • S=[1,2,4,9],  H=[15,13,9,16]
  • public key is H while S is kept secret.

• Decryption algo. 복호화 알고리즘
  • S가 simple knapsack 일 때, H = w*s mod n
  • The ciphertext C(암호문) produced by the encryption algo. is C=H*P=w*S*P  mod n where P is plaintext.
  • To decipher(암호해독), multiply C by w^(-1) 
    • w^(-1) * C = w^(-1) * H * P = w^(-1) * w * S * P = S * P mod n
    • where w^(-1) * w = 1 mod n
  • 이렇게 얻은 S와 목표합 w^(-1)*C를 해결하면 원래 평문 P를 recover(복원)

• secrety key S={1,2,4,9}, public key  H={15,13,9,16},  w=15,  n=17
• P = 0100 1011 1010 0101
• Encrypted message: 13 40 24 29
  1. (0,1,0,0)·H = 13
  2. (1,0,1,1)·H = 40
  3. (1,0,1,0)·H = 24
  4. (0,1,0,1)·H = 29

x=8 (그리고 y=-7)을 구하는 법

• Decrypted message, where 15^(-1) mod 17 = 8 (extended Euclidean algo. 결과)
• w^(-1)*C 구하고 mod n 연산 
  1. 13×8  =104 mod  17=2  ⟶  (0,1,0,0)
  2. 40×8 =320  mod 17=14  ⟶  (1,0,1,1)
  3. 24×8 =192  mod  17=5  ⟶  (1,0,1,0)
  4. 29×8 =232   mod 17=11  ⟶  (0,1,0,1)

RSA public key cryptographic algorithm

• 공개키는 공개 저장소에 보관되고, 비밀키는 오직 해당 사용자만 소유.
• 암호화/복호화 흐름: c=EPA(m), m=DSA(c) 

• RSA: Ronald Rivest, Adi Shamir, Leonard Adleman이 1978년 발표.
  • Rivest(1947~), MIT 교수
  • Shamir(1952~), Weizmann Institute 교수
  • Adleman(1945~), USC 교수
• 현재 가장 널리 쓰이는 공개키 암호 알고리즘. most widely-used public key cryptographic algo.
• 소인수분해의 어려움 기반. based on prime factrorization
• applications
  • Public key cryptography(공개키 암호화), digital signature(디지털 서명), Key exchange protocol(키 교환 프로토콜) 등.

• Key Setup
  • Public key: (n,e)
  • Secret key: d

1. 두 개의 큰 소수 p, q 선택
   (일반적으로 ≥1024 bit 크기의 소수를 사용하고, 길이가 비슷해야 보안에 유리)
2. n=p×q
3. ϕ(n)=(p−1)(q−1)
4. public key e: gcd⁡(e,ϕ(n))=1,  1<e<ϕ(n)
5. secret key d: d=e^(−1) mod  ϕ(n) (확장 유클리드 알고리즘 사용)
6. 암호화 Encryption: c=m^e  mod n (m < n)
7. 복호화 Decryption: m=c^d  mod n

• p, q가 노출되면 ϕ(n) 계산이 가능해지고, 그 결과 e, d도 구해지기 때문에 p, q 보호가 매우 중요.

Example

• p=7, q=11  ⟶  n = p x q = 7×11 = 77
• ϕ(n) = (p-1)(q-1) = (7−1)(11−1) = 6×10 = 60
• e=7 (1 < e <  ϕ(n)이고 gcd⁡(7,60)=1)

유클리드 호제법을 “gcd⁡(7, 60)”으로 시작하여 단계별로 계산하면 다음과 같습니다:

첫 단계: gcd⁡(7, 60)
60÷7=8   … 나머지  4  ⟹  60=7×8+4.
따라서 gcd⁡(7, 60)  =  gcd⁡(7, 4).

두 번째 단계: gcd⁡(7, 4)
7÷4=1   … 나머지  3  ⟹  7=4×1+3.
따라서 gcd⁡(7, 4)  =  gcd⁡(4, 3).

세 번째 단계: gcd⁡(4, 3)
4÷3=1   … 나머지  1  ⟹  4=3×1+1.
따라서 gcd⁡(4, 3)  =  gcd⁡(3, 1).

네 번째 단계: gcd⁡(3, 1)
3÷1=3   … 나머지  0  ⟹  3=1×3+0.
이때 나머지가 0이므로 연산을 멈추고, 마지막 비(0이 아닌)나머지인 11이 최대공약수입니다.

결론: 
gcd⁡(7, 60) = gcd(1,0) = 1.

• d = e^(−1) mod  60 = 7^(−1) mod  60=43
  (Extended Euclidean algo.)

1. 유클리드 호제법으로 gcd⁡(7, 60)=1 확인

60=7×8+4 ⟹  4=60−7×8
7=4×1+3 ⟹  3=7−4×1
4=3×1+1 ⟹  1=4−3×1
3=1×3+0 → 나머지가 0이므로 종료, gcd⁡(7,60)=1.

2. 뒤로 올라가며 확장유클리드로 1을 7과 60의 선형 결합으로 표현

Step 3로부터
1  =  4−3×1.

여기서 3을 Step 2 식으로 대체:
Step 2로부터
3=7−4×1  ⟹  1=4−( 7−4×1 )=4−7+4=2⋅4−7.
즉, 1=2⋅4−7.

이제 4를 Step 1 식으로 대체:
Step 1로부터
4=60−7×8  ⟹  1=2( 60−7×8 )−7=2⋅60−16⋅7−7=2⋅60−17⋅7.

정리하면,
1=(−17)×7  +  2×60.

따라서 확장 유클리드 결과로 얻은 식은 7×(−17)+60×2  =  1이고,
모듈로 60에서 보면, 7×(−17) ≡ 1(mod60).
즉, 7×x≡1(mod60) ⟹ x≡−17(mod60).

−17  mod 60 = 60−17 = 43이므로, x = 43이 “7의 역원 modulo 60”

• 암호화
  • Plaintext m=8
  • Ciphertext c=8^7  mod 77 = 57

8^1 mod 77 = 8
8^2 mod 77 = 64
8^3 mod 77 = 50
8^4 mod 77 = 15
8^5 mod 77 = 438
8^6 mod 77 = 36
8^7 mod 77 = 57

따라서 실제 암호화 단계에서 c=8^7 mod 77 = 57

• 복호화: m=57^43  mod 77=8.
• 즉, 올바르게 복원됨.

Square-and-multiply Method

• 공개키 암호화 대부분에서 y = a^x mod n 연산이 필요.
• 일반 지수승 연산 a^x은 x가 매우 큰 경우 비효율적이기 때문에, “Square-and-multiply” 기법을 사용하여 빠르게 계산
  • represent the exponent in binary and use square and multiplication operations for exponentiation
  • 지수를 이진수로 표현한 뒤, 제곱 연산과 곱셈 연산을 반복.

Square‐and‐Multiply(x, c, n):
    # x: 밑 (base)
    # c: 지수 (exponent), 이진수로 c = (c_{l-1} c_{l-2} ... c_0)_2
    # n: 모듈러스 (modulus)

    z ← 1
    # 지수의 최상위 비트(c_{l-1})부터 c_0까지 순차 처리
    for i from (l - 1) down to 0 do
        # 1) 먼저 z를 제곱(제곱 후 모듈러 n)
        z ← (z × z) mod n

        # 2) 만약 현재 비트 c_i가 1이면, 
        if c_i = 1 then
            #   z에 다시 한 번 x를 곱하고 모듈러 n
            z ← (z × x) mod n
        end if
    end for

    return z

Square-and-multiply Method - Example

• n=11413,  c=3533,  x=9726,  z=9726^3533 mod 11413. 
• 지수 3533를 이진수로: 3533_{10} = 110111001101_{2}.

• 최종 결과: z=5761

RSA public key cryptographic algorithm

• 타당성(정당성)

• 실제 암호화·복호화 효율을 높이기 위해
  • 보통 e=3(이진수로 11), 17(이진수로 10001), 65537(이진수로 10000000000000001) 같은 작은 값 사용.

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입니다.

Number theory and cryptographic algorithms

Introduction to number theory and cryptographic algo.

• 수론은 이러한 작업을 수행하는 데 있어 가장 유용한 주요 도구입니다. 많은 현대 암호 기법이 수론에 기반해 설계되어 있습니다.
• 위와 같은 서비스의 보안은 종종 (NP 클래스에 속하는) 풀기 어려운 문제들의 난이도에 의존합니다. 예를 들어, 큰 합성수의 인수분해 문제나 이산 로그 문제 등이 있습니다.
• “수론과 암호 알고리즘”은 알고리즘 설계 및 분석의 틀 안에서 수론과 암호학의 계산적 측면을 연구하는 학문 분야입니다.

Number theory basics

• 임의의 집합 S와 이항 연산 ⊕에 대해, (S,⊕)가 군이 되려면 다음 네 조건을 만족해야 한다:

1. closed 폐쇄성: ∀a,b∈S, a⊕b∈S
2. identity element 항등원 존재: ∃e∈S s.t. e⊕a = a⊕e = a
3. inverse element 역원 존재: ∀a∈S, ∃b∈S s.t. a⊕b = b⊕a = e
4. associative law 결합법칙: ∀a,b,c∈S, (a⊕b)⊕c = a⊕(b⊕c)

• 예시
  • (ℤ,+): + (addition) operator for integers
  • (ℝ∖{0},×): x (multiplication) operator for real numbers except 0
• Finite group: S is fininte for (S,⊕)

• Commutative group or Abelian group: For ∀a,b∈S, a⊕b = b⊕a
• Modulo congruence "합동" 또는 "동치"
  • Let a, b be integers and n be positive integer. If (a-b) is divisible by n, (i.e., n|(a-b)), a≡b (mod n) (congruency)
  • 합동: a≡b (mod n) ⇔ n|(a−b).
  • Example
    • Since 3|(25 - 13), 25 ≡ 13 (mod 3)
    • 25 ≡13 (mod 3) ↔ 25 mod 3 = 13 mod 3
• Equivalence relation for (mod n)
  • Equivalence relation holds reflexity, symmetry, and transitivity
    • Reflexity: For all integers a, a ≡ a (mod n)
    • Symmetry: If a ≡ b (mod n), b ≡ a (mod n)
    • Transitivity: If a ≡ b (mod n) and b ≡ c (mod n), a ≡ c (mod n)
• Equivalence class
  • The set of integers which is congruent with a mod n
  • [a]ₙ은 n 합동 관계에서 a 와 “동치”인 모든 정수의 모임을 의미
  • As congruence is in equivalence relation, find the equivalence class as follows 
    • [a]ₙ = {a+kn | k∈Z}
    • [3]7={ ..., -11, -4, 3, 10, 17, ... }
  • ℤₙ : The set of equivalence classes for (mod n)
    • ℤₙ = { [0]ₙ, [1]ₙ, …, [n−1]ₙ } = {0,1, ... , n-1}
    • [a] ₙ + [b] ₙ = [a+b] ₙ
      • eg) [3]_5+[4]_5=[7]_5=[2]_5
    • [a] ₙ × [b] ₙ = [ab] ₙ 
      • eg) [2]_5 x [4]_5 = [8]_5 = [3]_5

1. 집합 [Z]_5 연산 ‘+’
Z_5={0,1,2,3,4} 연산은 “모듈로 5 덧셈” 즉, a+b를 계산한 뒤 5로 나눈 나머지를 결과로 삼습니다.

2. 항등원(identity element)
항등원이란, 아무 원소 a에 더해도 a 그대로 나오는 요소를 말합니다.
Z_5에서 어떤 a∈{0,1,2,3,4}에 대해 a+0  ≡  0+a  ≡  a(mod5) 가 항상 성립하므로, 항등원은 0입니다.

3. 역원(inverse element)
역원이란, 원소 a에 더했을 때 항등원(여기선 0)이 되는 요소 −a를 말합니다. 즉, a+(−a)  ≡  0(mod5).
모듈로 5 덧셈에서 −a는 일반적으로 5−a와 동치이므로, a + (5 - a)  ≡  0 (mod5).

1. It should be closed
Any two arbitrary attributes in Ζ_3 and the result of + should be in Ζ_3

2. It follows associative law
+ operator clearly follows associative law
(a + b) + c ≡ a + b + c ≡ a + (b + c) (mod 3)

3. There exists identity element
For arbitrary a in Z_3, a + 0 ≡ a ≡ 0 + a (mod 3)
There exists identity element 0.

4. There exists inverse element
For arbitrary a in Z_3, a + (-a) ≡ 0 (mod 3)
There exists inverse element of a, which is -a.

• Theorem. For all positive integers, (Ζ𝑛, +) is finite and commutative group
  • [proof] (Ζ𝑛, +) follows associative and communtative laws. Identity element is [0]𝑛 and inverse element of [𝑎]𝑛 is [−𝑎]𝑛 𝑎𝑠 [𝑎]𝑛 + [−𝑎]𝑛 = [𝑎 + (−𝑎)]𝑛 = [0]𝑛 
• (Ζ𝑛,×) is not a group
  • Some attributes in Ζ𝑛 do not have inverse elements

• ℤₙ*
  • The set of attributes in ℤₙ* which is coprime of n
  • If n is prime, ℤₙ* = ℤₙ - {0}
  • gcd(a,n)=1인 1≤a<n인 원소들의 집합 → 곱셈에 대한 군
  • Example
    
    • ℤ₉*={1,2,4,5,7,8}, ℤ₇*={1,2,3,4,5,6}
    • 항등원: [1], 각 원소는 역원을 가짐

• Find identity element and inverse element of all attributes for (ℤ₇*,x)
  • ℤ₇* = {1,2,3,4,5,6} ax1=1xa=a (mod 7)
  • Thus, 1 is identity element
  • Inverse elements

• x operator table for ℤ₉*={1,2,4,5,7,8}. Based on the table, we can get the result of x and inverse element of each attribute
•  이 표에 의해 곱셈의 결과와 각 원소에 대한 역원을 쉽게 알 수 있다.
  • Identity element: 1 ( ∵ a x 1 ≡ 1 x a ≡ a (mod 9) )
  • Inverse element: a x ? ≡ 1 (mod 9)
  • Inverse element for (ℤ₉*,x) are {1,5,7,2,4,8}

• 표에서 “어떤 행 a에서 1이 나타나는 열”을 보면 그 열의 헤더가 a의 역원임을 알 수 있다.

• Theorem. Leg gcd(a,b) be the greatest common divisor of a and b. If d|a,b and d=ax+by for some integers x,y, hen d=gcd(a,b).

정수 a,b에 대해 d가 a와 b의 공약수(d|a,b)이고, 정수 x,y가 존재하여 d=ax+by를 만족한다면, 그 d는 gcd⁡(a,b)이다.

[proof]
Since d|a and d|b, d ≤ gcd(a,b).
Also, Since gcd(a,b)|a and gcd(a,b)|b, gcd(a,b)|ax+by (=d). gcd(a,b) ≤ d
Therefore, d = gcd(a,b)

Example. For a=13,b=4, 1=13x1+4x(-3) so gcd(13,4) = 1 (13,4 are coprime)

2. It follows associative law
(axb)xc ≡ axbxc ≡ ax(bxc) (mod 10)

3. There exists identity element
ax1 ≡ a ≡ 1xa (mod 10). So, identity element is 1.

4. There exists inverse element
As Z10* is the set of coprimes of 10 (i.e., gcd(a,10)=1),
therefore, the inverse element of each attribute in Z10* should exist.

Z10*는 10과 서로소인 원소들의 집합(즉, gcd⁡(a,10)=1)이므로, Z10∗의 각 원소는 곱셈 역원이 존재해야 합니다.

• The number of attributes in ℤₙ* is called Euler phi function φ(n)

• The product will be applied to all primes which can divide n
  • 단, 여기서 곱은 n을 나누는 소수에 대해서 한다. (만약 n이 소수인 경우 n을 포함)
  • If p is prime, φ(p) = p(1-1/p) = p-1
  • Exmaple
    • φ(9)=9·(1−1/3)=6
    • φ(7)=7·(1–1/7)=6

Topics

• Radix sort
• Searching
  • findMinMax
  • find2ndMax
  • general selection (kth smallest)
    • median-of-medians rule

Lower bound proof (in the worst-case) for sorting by comparisons

비교 기반 정렬의 최악 하한 증명

• can be represented as a decision tree 결정 트리(Decision Tree) 모델
• 예를 들어, 세 개의 키 a,b,c를 정렬하는 다음과 같은 알고리즘을 생각해 보자.
  • 리프 노드(leaf nodes) 는 가능한 해답(정렬된 순서)을 나타내며, 총 n! 개가 있음.
  • n개의 키로 만들 수 있는 모든 순열 수와 일치.

※ 모든 키 x1,x2,…,xn는 서로 다르다고 가정.

1. 결정 트리 모델(Decision Tree Model)
   • 키 비교 기반 정렬 알고리즘은 항상 “비교 → 분기” 구조의 이진 결정 트리로 표현할 수 있다.
   • 예를 들어, 세 키 a,b,c를 정렬하는 경우, 내부 노드에서는 a<b, b<c 등의 비교를 수행하고,
     그 결과(“Yes”/“No”)에 따라 왼쪽·오른쪽 가지로 내려간다.
   • 리프 노드(leaf nodes)는 모든 비교가 끝난 뒤 얻어지는 정렬된 순서이며, 가능한 순열 수 n!개와 같다.
2. 높이(lower bound) 계산
   • 높이가 k인 이진 트리는 최대 2^k개의 리프를 가질 수 있다.
   • 따라서 n!  ≤  2k  ⟹  k  ≥  log⁡2(n!)이고, k는 정수이므로, 결정 트리의 높이는 최소 ⌈log⁡2(n!)⌉다.
3. 비교 횟수와 시간 복잡도
   • 정렬 알고리즘이 수행하는 비교 횟수는 결정 트리의 높이에 해당한다.
   • 따라서 어떠한 키 비교 기반 정렬도 최악의 경우 Ω(log⁡2(n!))번의 비교가 필요하며,
     Stirling 근사 등을 이용해 log⁡2(n!)=Ω(nlog⁡n)임을 보일 수 있다.
   • 결론: 비교 기반 정렬의 최저 한계(lower bound) 는 Ω(nlog⁡n)이다.

Bucket Sort vs. Radix Sort

Review: Radix Sort (기수정렬)

• Assumption 가정
  1. The keys are all non-negative integers in a fixed base (radix), e.g., 10. 비음수 정수(동일 자릿수)
  2. All keys have the same number of digits. 고정 진법
• Sort by distribution: general algo.
  • Distributes keys into distinct piles (buckets) based on the leftmost digit
  • Each pile can then be distributed into distinct piles based on the 2nd digit 
  • and so on ... 
  • 키를 가장 왼쪽(최상위) 자리수를 기준으로 서로 다른 더미(버킷)들로 분배한다.
  • 각 더미 안의 키들을 두 번째 자리수를 기준으로 다시 서로 다른 더미들로 분배한다.
  • 이 과정을 마지막(최하위) 자리수까지 반복한다.
  • 마지막으로, 모든 더미를 원래 순서대로 차례로 꺼내 붙여 합치면 정렬이 완성된다.
• MSD vs LSD
  • MSD: Most-Sifnificant-Digit from left to right
    • 최상위 digit부터 → 재귀적으로 각 버킷 탐색

• LSD: Least-Significant-Digit from right to left
  • 최하위 digit부터 → 반복적으로 한 번에 r개 버킷

• 각 키 ki가 가질 수 있는 값들의 개수를 기수(radix)라고 부름.
  • 즉, radix란 “한 자리(또는 한 단계)에서 키가 취할 수 있는 서로 다른 값의 수”를 의미.
  • 예를 들어, 10진수 키를 다룬다면 radix = 10이고, 이진수 키를 다룬다면 radix = 2가 됨.

• 시간 복잡도
  • If we have n keys with d digits and use r buckets for radix sort, d번 패스 × Θ(r + n) = Θ(d(r+n))
    • Time complexity for each pass: Θ(r + n)
      • 각 패스의 시간 복잡도는 r개의 각 버킷의 초기화에 필요한 시간 Θ(r)과 n개의 키를 분배하는데 필요한 시간 Θ(n)을 합한 Θ(r  + n)  
    • # of passes: d

Radix Sort Example (LSD)

• 입력: (34,18,55,08,35,07,86,27,91,40)
• 1차(1의 자리): bucket0→40, …, bucket8→18,08, …
• 2차(10의 자리): bucket0→07,08, … → 최종 [07,08,18,27,34,35,40,55,86,91]

Searching: findMinMax problem

• 문제: n개 키에서 최댓값·최솟값을 동시에 구하기
• 단순 방법: Max 찾고 Min 찾기 → (n-1) + (n-1) = 2n−2 비교
• divide-and-conquer 분할정복:
  • 반씩 나누어 각 부분에서 (min, max) 구함 → 두 부분 간 비교 2회 추가

• Psudo-code
  • Input: array, left, right
  • Output: (MIN, MAX)

procedure MaxMin(A, i, j)
 if i = j then return (A[i], A[i]) # No comparisons needed
 else if j − i = 1 then if A[i] < A[j] then return (A[i], A[j]) 
     else return (A[j], A[i]) # One comparison needed
 else
     mid ← ⌊(i + j) / 2⌋ # Divide into n/2-size subproblems
    (minL, maxL) ← MaxMin(A, i, mid)
    (minR, maxR) ← MaxMin(A, mid + 1, j)
    return (min(minL, minR), max(maxL, maxR)) # Two comparisons needed

• Time complexity ( # of comparisons)
  • If n=1, T(1)=0, (no comparisons needed)
    • n=1일 때, 즉 i=j일 때, 바로 a[i]값 반환하므로, 비교 X
  • If n-2, T(2)=1, (one comparison for two keys)
    • n=2일 때, 두 원소를 한 번 비교하여 큰 원소를 max로 반환하고 작은 원소를 min으로 반환
  • If n>2, T(n) = 2T(n/2) + 2
    • 인덱스 mid에 의해 배열을 대략 n/2씩 두 부분으로 나누게 되고, 각 부분 배열에서 수행하는 비교 횟수는 T(n/2)
    • 각 부분 배열에서 최대값을 구한 후, 원래 문제의 최대 최소 값을 구하기 위해서는 두 번의 비교를 추가로 함.
  • Thus, T(n) = 3n/2 - 2 comparisons

Searching: find2ndMax problem

• Naïve solution: Max 두 번 호출 → n−1+n−2비교
  • For x1,x2,x3,x4,x5, 4 comparisons to find MAX and further make 3 comparisons to find 2ndMAX
  • Total 7 comparisons
  • Better approach

• After 1st comprison, winners are x2,x4,x6,x7
• After 2nd comparison, winners are x4, x6
• After 3rd comparison, winners are x6 (MAX)
• 2ndMAX = max(x4,x7,x5) # losers against x6

• Time complexity:
  • findMAX: n-1 comparisons
  • The number of losers to x6: height of the tree (log2n)
  • max(x4,x7,x5): log2n -1 comparisons
  • Thus, n-1 + log2n -1 = n+ log2n -2

이 방식은 “토너먼트”를 통해 최대값을 찾고,
그 과정에서 최대값과 겨뤘던(비겼던 게 아니라 패배한) 후보들 중에서 다시 최대를 뽑아서 두 번째로 큰 값을 찾는 기법.

1. 첫 번째 토너먼트 (find MAX)
n개의 원소를 한 쌍씩 비교해 올라가면서 최댓값을 찾을 때,
매 비교마다 승자는 다음 라운드로 진출하고 패자는 탈락하므로, 총 n−1번의 비교가 필요.

2. 최댓값과 겨룬 패자(losers) 모으기
토너먼트 트리에서 루트(최댓값)까지 올라오는 과정에서
최댓값과 직접 비교된 후보(패자)는 트리의 높이만큼, 즉 ⌊log⁡2n⌋명. 이들은 “두 번째로 클 수 있는” 유일한 후보들.

3. 패자들 중에서 두 번째 최대값 찾기
이 log⁡2n명의 후보를 다시 최대를 뽑는 또 다른 “작은 토너먼트”라고 보면,
log⁡2n−1번의 비교로 그 안에서 최댓값(=원래 전체에서 두 번째로 큰 값)을 찾을 수 있음.

4. 총 비교 횟수 합산
n−1  +  (log⁡2n−1)  =  n+log⁡2n−2. 
첫 토너먼트(전체 최대) + 패자들 토너먼트(두 번째 최대)

즉, 전체 과정에서 n−1 + log⁡2n−1 비교를 수행하므로, 최종적으로 n+log⁡2n−2n 번의 비교를 하는 셈.

• How to keep track of losers to MAX
  • One way to do this is to maintain the linked lists of keys that lose to each undefeated keys. This requires O(n) extra space.

최댓값을 찾는 “토너먼트 방식”에서, “최댓값”이 되기까지 직접 비교를 통해 패배(lose)한 키들을 모두 모아두려면 다음과 같이 하면 됨.

1. 각 키에 연결 리스트(linked list) 준비
배열의 각 원소(키)마다 자신에게 패배한(lose) 상대 키들을 저장할 수 있는 빈 연결 리스트를 하나씩 만든다.
이때 연결 리스트 전체를 합치면 최대 n−1개의 요소가 저장되므로, 추가 공간 O(n) 만 필요.

2. 토너먼트 진행하면서 패자 기록
두 키 x 와 y 를 비교해 승자를 w=max⁡(x,y), 패자를 l=min⁡(x,y)라고 할 때, 승자인 w의 연결 리스트에 l 을 “push” 하듯 추가.
이렇게 하면, 나중에 w가 최종 승자가 되었을 때, “w에게 패배한 키들” 이라는 연결 리스트가 고스란히 남게 됨.

3. 두 번째 최댓값 찾기
최종 승자 w∗의 연결 리스트에는, “w∗가 이긴(compare) 모든 상대”가 들어 있음.
두 번째로 큰 값은 이 리스트 중 최댓값이므로, 이 리스트를 한 번 탐색하며 최대를 찾으면 됨.
리스트 길이는 토너먼트 트리 높이(⌊log⁡2n⌋)이므로, 이 단계 비교 횟수는 O(log⁡n).

4. 요약
- 공간 복잡도: 승자별 패자 기록용 연결 리스트 총합으로 O(n)

- 시간 복잡도:
1) 전체 토너먼트 = n−1 비교
2) 최종 승자 패자 리스트 탐색 = O(log⁡n) 비교 → 총 n+log⁡n−2 비교

이렇게 연결 리스트를 유지하면 “누가 누구에게 졌는지”를 일일이 다시 기억할 필요 없이,
최댓값에 패배한 후보들만 빠르게 추려낼 수 있음.

Searching: general selection problem

• Given keys, x1,x2,...,xn, find the kth smallest (or the kth largest) key.
  • findMax: finding the largest key (k=n)
  • findMin: finding the smallest key (k=1)
  • find2ndMax: finding the 2nd largest key (k=n-1)
  • findMedian: k= n/2
• Use divide-and-conquer (i.e., quicksort) to find k-th MIN
  • Let's say pivot is at i-th index
    • if k=i, pivot is k-th MIN
    • if k<i, recursively find MIN on sublist with i-1 length
    • if k>i, recursively find MIN on sublist with n-i length

• Pseudo-code
  • Input: a(list), k
  • Output: k-th MIN

selection(left, right, k, a)
{
	if(left equals right)
		return a[left]
	else
	{
		pivot = partition(left, right, a)
		if(k equals pivot)
			return a[pivot]
		else if(k is less than pivot)
			return selection(left, pivot – 1, k);
		else
            return selection(pivot + 1, right, k);
	}
}

• Unfortunately, it has the same worst-case time complexity as Quicksort, given by O(n^2).

• The careful choice of the pivot element improves on worst-case quadratic time, so called the "median-of-medians rule". Next we show briefly how this can be done.

• The "Median-of-Medians" rule:
  • Assume n=5(2r+1) for some r>0. We choose r=5.
    
    1. divide n keys into n/5 sets of 5 keys each. 5개씩 그룹 나누어 각 그룹 중앙값 구함.
    2. find the median mi of each set, where 1<=i<=n/5.
    3. 중앙값들로 다시 중앙값 m∗ 찾기(재귀 호출), that is, S={m_1,m_2,...,m_n/5} and k=n/10.
       • n/5개의 원소 m_1,m_2,...,m_n/5에 대해서 k=n/10으로 하여 이 함수를 다시 재귀적 호출, 중앙값들의 중앙값인 m*를 구한다.
    4. compare each key in A and D to m*.
    5. Let S1=C∪{keys < m* in A, D} and S2=B ∪{keys > m* in A, D}.
       • A,D에 있는 원소들 중 m*보다 작은 원소 
       • A,D에 있는 원소들 중 m*보다 큰 원소
    6. if |S1+1|=k, then m* is the k-th smallest key
    7. else if k<=|S1| then select (S1,k) S1에서 k번째로 작은 값 찾기
    8. else select (S2, k-|S1|-1) S2에서 k-|S1|-1번째로 작은 값 찾기

1. 5개씩 그룹으로 나누고 중앙값 뽑기
전체 n개의 키를 임의 순서로 5개씩 묶는다.
각 그룹(크기 최대 5)의 중앙값을 삽입 정렬 등으로 O(1)에 뽑아낸다.
총 그룹 수는 ⌈n/5⌉이므로, 이 단계 비용은 O(n).

2. 중앙값들의 중앙값 m∗ 구하기
뽑아낸 ⌈n/5⌉개의 중앙값을 다시 QuickSelect(재귀)로 처리하여 전체 중앙값을 구한다. 이 단계 비용은 T(n/5).

3. m∗로 배열 분할(Partition)
원래 배열을 <m∗, =m∗, >m∗ 세 부분으로 나눈다.
보장: 적어도 3n/10개 이상이 <m∗에, 적어도 3n/10개 이상이 >m∗에 속한다.
따라서 남는(가장 큰) 부분도 최대 7n/10개 이하다. 이 단계 역시 전체 순회 한 번이므로 O(n)

4. 재귀 호출
찾고자 하는 순위 k가
< 왼쪽 크기면 왼쪽(≤3n/10)만,
> 왼쪽+중앙값 개수면 오른쪽(≤7n/10)만
재귀 최악의 재귀 호출 비용은 T(7n/10)

전체 비용 합산
T(n) = O(n)  +  T(n/5)  +  T(7n/10) = O(n)
(그룹 나누고 중앙값 뽑고 분할까지) + (중앙값들의중앙값 찾기) + (가장 큰 재귀부분 호출)

Backup slide: general selection problem

“왜 Median‐of‐Medians 로 분할하면 최악에도 T(n)=O(n)이 보장되는지”를
• 그룹 크기(n/5중간값)
• 피벗 기준 좌우 크기(≤7n/10)
• 점화식 전개 등을 통해 수학적으로 증명하는 보충 자료

• Time complexity: 
  • Therefore, with this method, the algorithm is called “quickSelect”
    • Comparisons
      • For each set of 𝑛/5 sets, find median among 5 keys: 6𝑛/5
      • For the partition, compare n keys: n
    • Recursive calls
      • Find median-of-medians on 𝑛/5 on medians: W(𝑛/5)
      • Recursive call on left or right sub array:W(7𝑛/10)

Find the median among 5 keys

문제
5개의 원소 A,B,C,D,E 중에서 중앙값(3번째로 작은 값)을 찾고자 합니다.

비교 횟수
대회 이론이나 정보 이론 상, 5개에서 정확한 중앙값을 구하려면 최소 6번의 비교가 필요합니다.

한 가지 가능한 비교 순서
1) A vs. C → 더 큰 쪽을 W1, 작은 쪽을 L1으로 표시
2) B vs. D → 승자 W2, 패자 L2
3) W1 vs. W2 → 이 두 중 가장 큰 값을 W3, 작은 값을 L3
4) L3 vs. E → 승자 W4, 패자 L4
5) L4 vs. min⁡(W1,W2) → 승자 W5
6) W5 vs. min⁡(L1,L2) 또는 추가 비교를 통해 최종 중앙값 도출
이 과정을 통해 “5개 중 세 번째로 큰(=세 번째로 작은) 원소”를 정확히 분리해낼 수 있습니다.

왜 6번이 필요한가?
임의로 5개를 비교해 보면,
5개 중 3번째 위치를 결정짓기 위해서는 “누가 1,2위고, 누가 4,5위인지를 명확히 구분”해야 하기 때문.
4번 비교만으로는 상위 2개의 후보가, 하위 2개의 후보가 뒤바뀔 수 있는 경우가 남아 있고,
5번 비교로는 상·하위 그룹 중 하나만 확정될 뿐 전체 중앙값까지 좁히기에는 불충분합니다.
6번 비교를 통해야만 “중앙값 후보 그룹”을 명확히 가려낼 수 있습니다.

Median‐of‐Medians 맥락에서
이 6회 비교 과정을 n/5번 반복하여, “n/5개의 그룹별 중앙값”을 모두 구한 뒤,
그중 중앙값(m∗)을 찾는 재귀 단계의 기초가 됨.