합동 (Congruence)

합동(congruence)은 두 가지 뜻으로 쓰입니다. 정수론에서는 두 정수 a, b를 n으로 나눈 나머지가 같을 때, 즉 n이 a − b를 나눌 때 'a와 b는 n을 법으로 합동'이라 하고 a ≡ b (mod n)으로 씁니다. 추상대수에서는 이를 일반화해, 군·환 같은 대수 구조 위의 동치 관계 가운데 연산과 양립하는 것(동등한 원소끼리 연산하면 결과도 동등한 것)을 합동 관계라고 합니다.

자세히 알아보기

정수의 합동은 동치 관계(반사·대칭·추이)이면서 연산과 양립합니다. a ≡ b, c ≡ d (mod n)이면 a + c ≡ b + d, ac ≡ bd (mod n)입니다. 그래서 큰 수의 계산 중간에 언제든 나머지로 줄여도 결과가 맞습니다. 합동류(나머지가 같은 수들의 묶음)를 원소로 보면 Z/nZ가 됩니다.

일차 합동식 ax ≡ b (mod n)은 gcd(a, n)이 b를 나눌 때만 해가 있습니다. 중국인의 나머지 정리는 서로소인 법들에 대한 연립 합동식 x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)가 n₁n₂를 법으로 유일한 해를 가진다는 정리로, 큰 법의 계산을 작은 법들로 쪼개는 데 쓰입니다.

추상대수에서 합동 관계는 몫 구조를 만드는 도구입니다. 군의 합동 관계는 정규 부분군과, 환의 합동 관계는 아이디얼과 일대일로 대응합니다.

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

• 서명 검증: ECDSA 서명값은 s·k ≡ z + r·d (mod n)이라는 합동식으로 만들어지고(검증자는 k, d 없이 이 관계를 곡선 점 연산으로 확인합니다), 슈노어 서명(BIP-340)의 s = k + e·d mod n도 합동식입니다.
• RSA: 암호화와 복호화가 서로를 되돌리는 이유는 ed ≡ 1 (mod φ(n))이라는 합동 관계 덕분입니다. RSA 구현은 중국인의 나머지 정리로 복호화를 약 4배 빠르게 합니다.
• 스마트 컨트랙트: uint256 연산 결과는 실제 값과 2²⁵⁶을 법으로 합동이므로, 오버플로가 일어나도 '합동으로는 맞는' 값이 남아 버그를 알아채기 어렵습니다.

쉽게 말하면

합동은 '시계 위에서 같은 자리를 가리킨다'는 관계입니다. 14시와 2시는 12를 법으로 합동입니다.

예시

38 ≡ 14 (mod 12)입니다. 38 − 14 = 24가 12로 나누어떨어지기 때문입니다. x ≡ 2 (mod 3), x ≡ 3 (mod 5)의 해는 x ≡ 8 (mod 15)입니다.

또 3x ≡ 4 (mod 7)은 gcd(3, 7) = 1이므로 해가 하나 있으며, 3의 역원 5를 곱하면 x ≡ 20 ≡ 6 (mod 7)입니다(3 × 6 = 18 ≡ 4).