원시근(primitive root)

원시근(primitive root)

1. 직관적 비유

• 생각해보세요. 7개의 숫자 1, 2, 3, 4, 5, 6이 있어요 (p = 7 → 1~p-1)

• 원시근 g를 선택하면, g를 계속 곱하면서 7로 나눈 나머지를 기록하면

  • 결국 1~6 모든 숫자가 다 나온다는 거예요.

즉:

“g 하나만 가지고 1부터 p-1까지 모든 숫자를 찍어낼 수 있는 특별한 숫자”

2. 작은 예제 (p = 7)

• g = 3 → 3의 거듭제곱 mod 7:

• 보세요! 1, 2, 3, 4, 5, 6 → 1~6 모두 나왔죠?

• 그래서 3은 7의 원시근

• 반대로 g = 2 → 2^1, 2^2, …, 2^6 mod 7 = 2, 4, 1, 2, 4, 1

  • 1~6 모든 숫자가 안 나왔죠 → 2는 원시근 아님

3. 왜 DH에서 원시근을 쓰는가?

• DH에서는 g^a mod p 계산으로 공개키를 만들어요.

• g가 원시근이면:

  • 모든 가능한 값(1~p-1)을 만들 수 있어서
  • 공유키가 최대 범위를 가지며 안전성↑

• g가 원시근이 아니면:

  • 만들 수 있는 값이 제한됨 → 키 공간이 좁아지고 안전성↓

4. 요약

• 원시근 = 거듭제곱으로 1~p-1 모든 수를 만들 수 있는 특별한 수
• 비유: “하나의 씨앗(g)만 있으면 1부터 p-1까지 모든 숫자가 자라나는 수”
• DH에서 g를 원시근으로 선택해야 모든 값이 가능한 공유키를 얻음 → 안전