원시근 계산기

원시근 계산기 정보

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

원시근의 응용 분야

주요 개념 및 공식

원시근의 이해

법 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))\)개의 원시근이 존재하게 됩니다.

원시근 계산기 사용 방법

1. 법 n 입력: 입력 필드에 양의 정수를 입력하거나 빠른 예제 버튼 중 하나를 클릭하여 값을 자동으로 채웁니다.
2. 원시근 찾기 클릭: 버튼을 눌러 법 n에 대한 모든 원시근을 계산합니다.
3. 결과 검토: 원시근의 개수, 전체 목록, 오일러 피 함수, 군의 차수 및 해당 n에 대해 원시근이 존재하는지 여부를 확인합니다.
4. 시각화 탐색: n ≤ 100인 경우, 대화형 순환군 휠을 통해 각 원시근이 거듭제곱을 통해 전체 군을 어떻게 생성하는지 보여줍니다. 임의의 근 칩을 클릭하여 휠에서 순환 애니메이션을 확인하세요.
5. 거듭제곱 표 연구: 그리드는 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

고급 수학 연산 도구:

• 앤티로그 계산기
• 베타 함수 계산기
• 이항 계수 계산기
• 이항 확률 분포 계산기
• 비트-계산기 추천
• 중심극한정리 계산기
• 조합 계산기
• 상보 오차 함수 계산기
• 복소수 계산기
• 엔트로피 계산기
• 오차 함수 계산기
• 지수 붕괴 계산기 - 높은 정밀도
• 지수 성장 계산기 높은 정밀도
• 지수 적분 계산기
• 지수-계산기-높은-정확도
• 팩토리얼 계산기
• 감마 함수 계산기
• 황금비율 계산기
• 반감기 계산기
• 백분율 성장 계산기 추천
• 순열 계산기
• 포아송 분포 계산기
• 다항식 근 계산기와 상세한 단계
• 확률 계산기 추천
• 확률 분포 계산기 추천
• 비율 계산기
• 이차 공식 계산기
• 공학용 계산기 추천
• 과학적 표기법 계산기
• 유효숫자 계산기 새로운
• 큐브 합계 계산기
• 연속 숫자의 합 계산기
• 제곱합 계산기
• 진리표 생성기
• 집합론 계산기
• 벤 다이어그램 생성기 (3세트)
• 중국인의 나머지 정리 계산기
• 오일러 피 함수 계산기
• 확장 유클리드 알고리즘 계산기
• 모듈러 곱셈 역원 계산기
• 연분수 계산기
• 다익스트라 최단 경로 계산기
• 최소 신장 트리 계산기
• 그래프 차수열 검증기
• 완전순열 (부분계승) 계산기
• 스털링 수 계산기
• 비둘기집 원리 계산기
• 마르코프 체인 정상 상태 계산기
• 반올림 계산기 새로운
• 음이항분포 계산기 새로운
• 중복순열 계산기 새로운
• 모듈러 거듭제곱 계산기 새로운
• 원시근 계산기
• 불 대수 간소화기 새로운
• 카르노 맵 (K-Map) 솔버 새로운
• 그래프 채색 계산기 새로운
• 위상 정렬 계산기 새로운
• 인접 행렬 계산기 새로운
• 포함배제 계산기 새로운
• 선형 계획법 솔버 새로운
• 외판원 문제 솔버 (TSP) 새로운
• 해밀턴 경로 검사기 (Hamiltonian Path Checker) 새로운
• 평면 그래프 검사기 새로운
• 네트워크 플로우 계산기 (최대 유량) 새로운
• 안정된 결혼 문제 해결기 새로운
• 군론 위수 계산기 새로운
• 환과 체 계산기 새로운