전단사 (Bijective)

전단사(bijective) 함수 f: X → Y는 단사(injective, 일대일: 서로 다른 입력은 서로 다른 출력으로)이면서 동시에 전사(surjective, 위로: Y의 모든 원소가 어떤 입력의 출력)인 함수입니다. 그 결과 X와 Y의 원소가 빠짐없이, 겹침 없이 하나씩 짝지어지며, 이런 함수를 일대일 대응이라고도 합니다. 전단사 함수는 정확히 역함수를 가지는 함수, 즉 가역 함수입니다.

자세히 알아보기

유한 집합 사이에 전단사가 있으면 두 집합의 원소 수가 같습니다. 반대로 원소 수가 같은 유한 집합 사이에서는 단사이기만 하면 자동으로 전사이고, 전사이기만 해도 자동으로 단사입니다. 집합 X에서 자기 자신으로의 전단사를 순열(치환)이라 하며, n개 원소의 순열은 n!가지입니다.

전단사가 아닌 예도 중요합니다. f(x) = x²(실수 → 실수)는 f(−2) = f(2)이므로 단사가 아니고, 음수에 도달하지 못하므로 전사도 아닙니다. 해시 함수처럼 긴 입력을 짧은 출력으로 보내는 함수는 비둘기집 원리에 따라 결코 단사일 수 없습니다.

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

• 블록 암호: AES-256은 키를 하나 고정하면 128비트 블록 2¹²⁸개 위의 순열, 즉 전단사입니다. 그래야 복호화가 항상 가능합니다. 좋은 블록 암호는 '무작위로 고른 순열'과 구별되지 않아야 합니다(유사 무작위 순열).
• 인코딩: 16진수, Base58Check, Bech32는 바이트열과 '유효한' 인코딩 문자열 사이의 전단사여서(체크섬이 틀린 문자열은 거부됨) 정보 손실 없이 주소나 키를 표시합니다. BIP-39 니모닉도 엔트로피(+체크섬)와 단어열 사이의 일대일 대응입니다.
• 주소 생성은 전단사가 아님: 공개 키에서 주소를 만드는 과정은 해시를 거치므로 단방향이며 전단사가 아닙니다. 이론적으로는 여러 공개 키가 같은 주소를 가질 수 있지만, 160비트(이더리움·비트코인 P2PKH) 공간에서 이를 찾는 것은 현실적으로 불가능합니다.
• 해시 함수 내부: Keccak-f[1600] 순열처럼 해시 함수의 내부 부품은 전단사로 설계하고, 전체 구조에서 일부 출력만 잘라 써서 단방향성을 얻습니다.

쉽게 말하면

전단사는 '좌석 수와 승객 수가 같고, 모든 승객이 서로 다른 자리에 앉아 빈자리도 없는' 배정입니다.

예시

f(x) = (3x + 1) mod 10은 {0, …, 9} 위의 전단사이고, 역함수는 f⁻¹(y) = 7(y − 1) mod 10입니다(3 × 7 = 21 ≡ 1).