# n을 법으로 하는 곱셈군 (Multiplicative Group of Integers Modulo n, Zn*)

Zn*(또는 (Z/nZ)*)는 1부터 n−1까지의 정수 가운데 n과 서로소인 것들만 모아, n을 법으로 하는 곱셈을 연산으로 갖는 군입니다. 이 원소들은 곱셈 역원을 가지므로 '가역원의 군' 또는 '기약 잉여류군'이라고도 합니다. 원소의 개수는 오일러 피 함수 φ(n)입니다. (Zn은 아연의 원소 기호와 표기가 같지만 여기서는 수학 기호입니다.)

## 자세히 알아보기

Zn*는 유한 아벨 군입니다. 라그랑주 정리에 따라 모든 원소 a에 대해 a^φ(n) ≡ 1 (mod n)이 성립하는데, 이것이 오일러 정리이고 n이 소수 p이면 페르마의 소정리 a^(p−1) ≡ 1 (mod p)가 됩니다.

Zn*가 하나의 원소(원시근)로 모두 생성되는 순환군인지는 n에 따라 다릅니다. 순환군이 되는 것은 n = 1, 2, 4, p^k, 2p^k(p는 홀수 소수)인 경우뿐입니다. 예를 들어 Z8* = {1, 3, 5, 7}은 모든 원소의 제곱이 1이어서 순환군이 아닙니다. 반면 소수 p에 대한 Zp*는 항상 위수 p−1인 순환군입니다.

φ(n)은 n의 소인수분해를 알면 쉽게 계산됩니다. n = pq이면 φ(n) = (p−1)(q−1)입니다. 반대로 φ(n)을 알면 p + q = n − φ(n) + 1이 되어 p, q를 이차방정식으로 바로 구할 수 있으므로, p, q를 모른 채 φ(n)을 구하는 것은 n을 인수분해하는 것과 동등하게 어렵습니다.

## 블록체인·암호화폐에서는

- RSA: 공개 지수 e와 비밀 지수 d를 ed ≡ 1 (mod φ(n))(또는 카마이클 함수 λ(n))이 되게 고르고, Zn*에서의 거듭제곱으로 암호화·서명합니다. RSA의 안전성은 이산 로그가 아니라 인수분해의 어려움에 기대고 있습니다.
- 디피-헬만과 DSA: 고전적인 키 교환과 DSA는 큰 소수 p에 대한 Zp*의 부분군에서 이산 로그 문제의 어려움을 이용합니다.
- 현재의 흐름: 비트코인·이더리움·트론 등 주요 블록체인은 Zn* 기반 RSA·DSA 대신 같은 안전성을 훨씬 짧은 키로 얻는 타원곡선 그룹(secp256k1, Ed25519)을 사용합니다. 다만 RSA는 웹 인증서와 거래소 인프라에서 여전히 널리 쓰입니다. 양자 컴퓨터의 쇼어 알고리즘은 두 방식 모두를 위협하므로 양자 내성 암호로의 전환이 진행 중입니다.

## 쉽게 말하면

Zn*는 '시계 산술에서 나눗셈이 가능한 숫자들만 모아 놓은 모임'입니다. 이 안에서는 곱하고 되돌리는 것이 언제나 가능합니다.

## 예시

n = 10이면 Z10* = {1, 3, 7, 9}, φ(10) = 4입니다. 3 × 7 = 21 ≡ 1이므로 3과 7은 서로의 역원이고, 3^4 = 81 ≡ 1 (mod 10)으로 오일러 정리가 성립합니다.

---
출처: https://achivx.kr/glossary/multiplicative-group-of-integers-modulo-n-n%EC%9D%84-%EB%B2%95%EC%9C%BC%EB%A1%9C-%ED%95%98%EB%8A%94-%EA%B3%B1%EC%85%88%EA%B5%B0/ · ACHIVX 용어 사전 · 수정일 2026-10-20