원시근 계산기

주어진 법 n에 대한 모든 원시근(곱셈군 (Z/nZ)*의 생성원)을 찾습니다. 양의 정수를 입력하여 원시근, 오일러 피 함수 값, 순환군 시각화 및 거듭제곱 표를 통한 단계별 검증 결과를 확인하세요.

원시근 계산기

원시근 계산기 정보

원시근 계산기는 주어진 법 n에 대한 모든 원시근(거듭제곱 \(g^1, g^2, \ldots, g^{\varphi(n)}\)이 곱셈군 \((\mathbb{Z}/n\mathbb{Z})^*\)의 모든 원소를 생성하는 정수 g)을 찾습니다. 양의 정수를 입력하면 모든 원시근, 오일러 피 함수 \(\varphi(n)\), 대화형 순환군 시각화, 거듭제곱 표 및 최소 원시근의 단계별 검증 과정을 즉시 확인할 수 있습니다.

원시근의 응용 분야

🔐

Diffie-Hellman

키 교환 프로토콜에서 원시근을 생성자로 사용

🔏

ElGamal 암호화

이산 로그에 기반한 공개키 암호 시스템

✍

디지털 서명

DSA 및 Schnorr 서명은 순환군 생성자에 의존함

🎲

의사 난수

선형 합동 생성기는 원시근의 성질을 사용함

📡

오류 정정 부호

Reed-Solomon 및 BCH 코드는 유한체의 생성자를 사용함

🧮

수론

지수 계산, 이차 잉여 및 이산 로그 문제

주요 개념 및 공식

개념	공식 / 정의	설명
원시근	\(\text{ord}_n(g) = \varphi(n)\)	법 n에 대한 차수가 오일러 피 함수 값과 같은 정수 g
오일러 피 함수	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	[1, n] 범위에서 n과 서로소인 정수의 개수
존재 조건	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	원시근은 이 형태의 n에 대해서만 존재함 (p는 홀수 소수)
원시근의 개수	\(\varphi(\varphi(n))\)	원시근이 존재할 때의 총 개수
원시근 판정법	모든 소인수 \(p \| \varphi(n)\)에 대해 \(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\)	충분 조건: φ(n)의 소인수들에 대해서만 확인
모든 근 생성	\(\gcd(k, \varphi(n)) = 1\)인 \(g^k \bmod n\)	하나의 근 g를 찾으면 나머지 모든 근을 유도 가능

원시근의 이해

법 n에 대한 원시근은 \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\)의 집합이 1부터 n−1까지의 정수 중 n과 서로소인 모든 정수의 집합과 같은 정수 g를 의미합니다. 군론 용어로 g는 순환 곱셈군 \((\mathbb{Z}/n\mathbb{Z})^*\)의 생성자(generator)입니다. 예를 들어, 3은 법 7에 대한 원시근인데, 거듭제곱 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7)이 {1, 2, 3, 4, 5, 6}의 모든 원소를 생성하기 때문입니다.

원시근은 언제 존재합니까?

수론의 고전적인 결과(가우스가 증명)에 따르면, 법 n에 대한 원시근은 n이 1, 2, 4, p^k 또는 2p^k(여기서 p는 홀수 소수, k ≥ 1) 중 하나일 때만 존재합니다. n의 다른 값에 대해서는 군 \((\mathbb{Z}/n\mathbb{Z})^*\)이 순환군이 아니며(중국인의 나머지 정리에 의해 순환군들의 직적으로 분해됨), 따라서 단일 원소가 전체 군을 생성할 수 없습니다. 예를 들어, \((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\)는 원시근을 갖지 않습니다.

원시근을 효율적으로 찾는 방법

표준 알고리즘은 두 단계로 작동합니다. 1단계: 시도를 통해 가장 작은 원시근을 찾습니다. 2부터 시작하는 각 후보 g에 대해, \(\varphi(n)\)의 모든 소인수 p에 대해 \(g^{\varphi(n)/p} \bmod n\)을 계산합니다. 이 중 어느 것도 1이 아니면 g는 원시근입니다. 실제로 가장 작은 원시근은 일반적으로 매우 작으며, 임의의 \(\epsilon > 0\)에 대해 \(O(n^\epsilon)\)일 것으로 추측됩니다. 2단계: 하나의 원시근 g를 알게 되면, 다른 모든 원시근은 \(\gcd(k, \varphi(n)) = 1\)인 \(g^k \bmod n\)이 되며, 총 \(\varphi(\varphi(n))\)개의 원시근이 존재하게 됩니다.

원시근 계산기 사용 방법

법 n 입력: 입력 필드에 양의 정수를 입력하거나 빠른 예제 버튼 중 하나를 클릭하여 값을 자동으로 채웁니다.
원시근 찾기 클릭: 버튼을 눌러 법 n에 대한 모든 원시근을 계산합니다.
결과 검토: 원시근의 개수, 전체 목록, 오일러 피 함수, 군의 차수 및 해당 n에 대해 원시근이 존재하는지 여부를 확인합니다.
시각화 탐색: n ≤ 100인 경우, 대화형 순환군 휠을 통해 각 원시근이 거듭제곱을 통해 전체 군을 어떻게 생성하는지 보여줍니다. 임의의 근 칩을 클릭하여 휠에서 순환 애니메이션을 확인하세요.
거듭제곱 표 연구: 그리드는 k = 1, 2, …, φ(n)에 대한 g^k mod n을 보여주며, 원시근과 항등원은 서로 다른 색상으로 강조 표시됩니다.

암호학에서의 원시근

원시근은 현대 암호학에서 핵심적인 역할을 합니다. Diffie-Hellman 키 교환에서 양측은 큰 소수 p와 법 p에 대한 원시근 g에 합의한 다음, 공개키 g^a mod p와 g^b mod p를 교환합니다. 공유 비밀 g^ab mod p는 도청자가 알아내기에 계산적으로 불가능한데, 이는 큰 순환군에서 이산 로그를 계산하는 것이 매우 어렵다고 믿어지기 때문입니다. 마찬가지로, ElGamal 암호화와 디지털 서명 알고리즘(DSA) 모두 원시근에 의해 생성된 군에서의 이산 로그 문제의 난이도에 의존합니다.

FAQ

법 n에 대한 원시근이란 무엇입니까?

법 n에 대한 원시근은 g¹, g², …, g^φ(n) mod n의 거듭제곱이 n과 서로소인 모든 정수를 정확히 한 번씩 생성하는 정수 g입니다. 동등하게, g의 곱셈적 차수가 φ(n)과 같으며, 이는 g가 전체 곱셈군 (Z/nZ)*를 생성한다는 것을 의미합니다.

어떤 n 값에 대해 원시근이 존재합니까?

원시근은 n이 1, 2, 4, p^k 또는 2p^k인 경우에만 존재합니다(p는 홀수 소수, k는 양의 정수). 예를 들어 n = 7(소수), n = 9(3²), n = 14(2 × 7)는 모두 원시근을 갖지만, n = 8, n = 12, n = 15는 그렇지 않습니다.

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

n이 원시근을 갖는다면, 법 n에 대한 원시근의 개수는 φ(φ(n))과 같습니다(φ는 오일러 피 함수). 예를 들어 n = 7은 φ(φ(7)) = φ(6) = 2개의 원시근(3과 5)을 가집니다.

원시근은 어떻게 찾습니까?

n의 원시근을 찾으려면: 먼저 φ(n)을 계산하고 소인수분해합니다. 그런 다음 n과 서로소인 각 후보 g에 대해, φ(n)의 모든 소인수 p에 대해 g^(φ(n)/p)가 n에 대해 1과 합동이 아닌지 확인합니다. 모든 확인을 통과하면 g는 원시근입니다. 다른 모든 근은 gcd(k, φ(n)) = 1인 g^k mod n으로 찾을 수 있습니다.

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

원시근은 Diffie-Hellman 키 교환, ElGamal 암호화 및 디지털 서명 알고리즘의 기초가 됩니다. 원시근은 이러한 암호화 프로토콜의 보안 근거인 이산 로그 문제 해결을 어렵게 만듭니다. 원시근은 군의 모든 원소를 생성하여 공격자의 탐색 공간을 최대화합니다.

이 콘텐츠, 페이지 또는 도구를 다음과 같이 인용하세요:

"원시근 계산기" - https://MiniWebtool.com/ko/원시근-계산기/에서 MiniWebtool 인용, https://MiniWebtool.com/

MiniWebtool 팀 제작. 업데이트: 2026-04-16

또한 저희의 AI 수학 해결사 GPT를 사용하여 자연어 질문과 답변으로 수학 문제를 해결할 수 있습니다.