# 합성수 (Composite)

합성수(composite number)는 1과 자기 자신 이외의 약수를 가지는 1보다 큰 자연수, 다시 말해 두 개 이상의 소수(같은 소수가 반복되어도 됨)의 곱으로 나타낼 수 있는 수입니다. 4, 6, 8, 9, 12가 처음 몇 개의 합성수입니다. 1은 소수도 합성수도 아닙니다.

## 자세히 알아보기

산술의 기본 정리에 따라 모든 합성수는 소수들의 곱으로 유일하게 분해됩니다. 어떤 수가 합성수인지 판정하는 것(소수 판정)은 쉬운 문제입니다. 밀러-라빈 같은 확률적 판정법은 수백 자리 수도 순식간에 판정하며, 결정론적 다항 시간 알고리즘(AKS)도 존재합니다. 흥미롭게도 판정법은 '합성수다'라는 사실을 증명할 뿐 인수를 알려 주지는 않습니다. 반면 합성수의 인수를 실제로 찾아내는 소인수분해는 훨씬 어렵습니다. 이 차이가 공개 키 암호의 핵심 비대칭입니다.

페르마 판정을 속이는 카마이클 수(가장 작은 것은 561 = 3 × 11 × 17)처럼 소수인 척하는 합성수도 있어, 실무에서는 강한 판정법을 여러 번 반복합니다.

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

- RSA 모듈러스: RSA의 공개 키 n(모듈러스)은 두 큰 소수의 곱인 합성수입니다. n을 공개해도 인수 p, q를 찾기 어렵다는 것이 안전성의 전부입니다. 키를 만들 때 쓰는 소수 생성기가 약하면, 서로 다른 키가 같은 소수를 공유해 최대공약수 계산 한 번으로 깨지는 사고가 실제로 보고되었습니다.
- 타원곡선 그룹 위수: 서명용 곡선은 그룹 위수가 큰 소수이거나 '작은 보조인수 × 큰 소수' 형태여야 합니다. 비트코인 secp256k1은 위수가 소수(보조인수 1)이고, Ed25519는 위수가 8 × (큰 소수)인 합성수여서 구현에서 보조인수 처리를 신경 써야 합니다. 위수가 작은 소수들로 이루어진 합성수이면 이산 로그가 쉽게 풀립니다.

## 쉽게 말하면

합성수는 더 작은 수들의 곱으로 '쪼갤 수 있는' 수입니다. 12개짜리 달걀판을 2줄, 3줄, 4줄로 나눌 수 있는 것과 같습니다.

## 예시

12 = 2² × 3, 91 = 7 × 13은 합성수이고, 97은 소수입니다.

가장 작은 합성수는 4이고, 2보다 큰 모든 짝수는 합성수입니다. RSA-2048의 공개 키 n은 617자리 합성수이지만, 그 두 인수를 현실적인 시간 안에 찾는 방법은 공개적으로 알려져 있지 않습니다. 소수 판정은 빠르지만 인수분해는 어렵다는 이 차이가 RSA의 전제입니다.

---
출처: https://achivx.kr/glossary/composite-%ED%95%A9%EC%84%B1%EC%88%98/ · ACHIVX 용어 사전 · 수정일 2026-10-20