원시근 계산기

원시근 계산기에 오신 것을 환영합니다. 이 도구는 임의의 양의 정수 n에 대한 모든 법 n 원시근을 찾아주는 강력한 무료 온라인 도구입니다. 이 계산기는 단계별 검증 과정, 거듭제곱 표, 그리고 원시근이 어떻게 승법군을 생성하는지 이해하는 데 도움이 되는 애니메이션 순환군 시각화 기능을 제공합니다. 정수론을 공부하거나, 암호학 시험을 준비하거나, 프로그래밍 대회에서 모듈러 산술을 다룰 때, 이 도구는 즉각적이고 정확한 결과와 교육적인 통찰력을 제공합니다.

원시근이란 무엇인가요?

법 n의 원시근은 거듭제곱을 통해 n과 서로소인 모든 정수를 생성하는 정수 g입니다. 엄밀하게 말하면, 법 n에 대한 g의 승법 위수가 오일러 피 함수 값인 \(\varphi(n)\)과 같을 때 g를 법 n의 원시근이라고 합니다. 이는 다음과 같은 집합이

1부터 n-1까지의 정수 중 n과 서로소인 \(\varphi(n)\)개의 정수를 모두 포함함을 의미합니다. 원시근은 본질적으로 순환군 \((\mathbb{Z}/n\mathbb{Z})^*\)의 생성자입니다.

빠른 예시

n = 7인 경우를 생각해 봅시다. 7은 소수이므로 \(\varphi(7) = 6\)입니다. g = 3이 원시근인지 확인해 보겠습니다.

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

거듭제곱 결과 {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}으로, 7과 서로소인 모든 정수가 생성되었습니다. 따라서 3은 법 7의 원시근입니다.

원시근은 언제 존재하나요?

법 n에 대한 원시근은 n이 다음 형태 중 하나일 때만 존재합니다.

• n = 1, 2, 또는 4
• n = p^k (여기서 p는 홀수인 소수, k ≥ 1)
• n = 2p^k (여기서 p는 홀수인 소수, k ≥ 1)

예를 들어, 7, 9, 11, 13, 14, 18, 23, 25, 27, 46에 대해서는 원시근이 존재하지만, 8, 12, 15, 16, 20, 21, 24에 대해서는 존재하지 않습니다.

원시근 찾는 방법

1. 법 입력: 입력란에 양의 정수 n(2에서 100,000 사이)을 입력합니다.
2. 계산: "원시근 찾기" 버튼을 클릭하거나 Enter 키를 누릅니다.
3. 모든 원시근 보기: 오일러 피 함수 값 및 통계와 함께 원시근의 전체 목록을 확인합니다.
4. 거듭제곱 표 학습: 가장 작은 원시근이 어떻게 모든 서로소 잔여류를 생성하는지 검토합니다.
5. 순환군 시각화: 작은 법의 경우, 순환 구조를 보여주는 애니메이션 휠을 확인합니다.

n은 몇 개의 원시근을 가집니까?

법 n에 대해 원시근이 존재한다면, 그 개수는 다음과 같습니다.

예를 들어 n = 13일 때: \(\varphi(13) = 12\)이고 \(\varphi(12) = 4\)이므로, 법 13에 대한 원시근은 정확히 4개(2, 6, 7, 11)입니다.

검증 알고리즘

g가 법 n의 원시근인지 효율적으로 확인하려면:

1. n의 소인수분해를 사용하여 \(\varphi(n)\)을 계산합니다.
2. \(\varphi(n)\)의 모든 서로 다른 소인수 \(p_1, p_2, \ldots, p_k\)를 찾습니다.
3. 각 소인수 \(p_i\)에 대해 \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)인지 확인합니다.
4. 모든 확인을 통과하면 g는 원시근입니다.

이 방법은 \(\varphi(n)\)번의 거듭제곱 대신 \(k\)번의 지수 연산만 테스트하면 되므로 g의 모든 거듭제곱을 계산하는 것보다 훨씬 빠릅니다.

암호학에서의 원시근

디피-헬먼(Diffie-Hellman) 키 교환

디피-헬먼 프로토콜은 큰 소수 p와 법 p에 대한 원시근 g를 사용합니다. 앨리스는 비밀 키 a를 택해 \(g^a \bmod p\)를 보냅니다. 밥은 비밀 키 b를 택해 \(g^b \bmod p\)를 보냅니다. 두 사람은 공유 비밀 키 \(g^{ab} \bmod p\)를 계산합니다. 보안은 이산 로그 문제를 푸는 것이 계산적으로 매우 어렵다는 점에 의존합니다.

엘가말(ElGamal) 암호

엘가말 또한 생성자로 원시근을 사용합니다. 공개 키는 \((p, g, g^x \bmod p)\)이며, 여기서 x는 개인 키입니다. g가 모든 원소를 생성한다는 사실은 모든 메시지를 암호화할 수 있음을 보장합니다.

전자 서명

DSA(Digital Signature Algorithm) 및 관련 방식들은 전자 서명을 생성하고 검증하기 위해 \((\mathbb{Z}/p\mathbb{Z})^*\)의 부분군 내에서 원시근을 사용합니다.

참조표: 가장 작은 원시근

자주 묻는 질문

법 n에 대한 원시근이란 무엇인가요?

법 n에 대한 원시근은 거듭제곱 \(g^1, g^2, \ldots, g^{\varphi(n)}\)을 법 n으로 취했을 때 n과 서로소인 모든 정수를 생성하는 정수 g입니다. 즉, g는 전체 승법군 \((\mathbb{Z}/n\mathbb{Z})^*\)를 생성합니다. 법 n에 대한 g의 승법 위수는 오일러 피 함수 값인 \(\varphi(n)\)과 같습니다.

어떤 n 값에 대해 원시근이 존재하나요?

법 n에 대한 원시근은 n이 1, 2, 4, p^k, 또는 2p^k(여기서 p는 홀수인 소수, k ≥ 1)인 경우에만 존재합니다. 예를 들어 n = 7 (소수), n = 9 (3²), n = 14 (2×7)일 때는 원시근이 존재하지만, n = 8, 12, 15, 16일 때는 존재하지 않습니다.

n은 몇 개의 원시근을 가집니까?

법 n에 대해 원시근이 존재한다면, 원시근의 개수는 \(\varphi(\varphi(n))\)과 같습니다. 여기서 \(\varphi\)는 오일러 피 함수입니다. 예를 들어 n = 13 (소수)인 경우, \(\varphi(13) = 12\)이고 \(\varphi(12) = 4\)이므로 법 13에 대한 원시근은 정확히 4개입니다.

암호학에서 원시근이 왜 중요한가요?

원시근은 디피-헬먼 키 교환 프로토콜과 엘가말 암호 시스템의 기초가 됩니다. 이러한 암호 프로토콜에서는 큰 소수 p에 대한 원시근 g가 생성자로 사용됩니다. 보안은 이산 로그 문제의 어려움에 기반합니다. 즉, \(g^x \bmod p\)가 주어졌을 때 x를 찾는 것은 계산적으로 매우 어렵습니다.

g가 법 n에 대한 원시근인지 어떻게 확인하나요?

g가 법 n의 원시근인지 확인하려면: (1) \(\varphi(n)\)을 계산합니다. (2) \(\varphi(n)\)의 모든 소인수 \(p_1, p_2, \ldots, p_k\)를 찾습니다. (3) 각 소인수 \(p_i\)에 대해 \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)인지 확인합니다. 모든 확인을 통과하면 g는 원시근입니다. 이는 g의 모든 거듭제곱을 계산하는 것보다 훨씬 빠릅니다.

관련 도구