두 32비트 정수의 곱으로 나타낼 수 있는 64비트 정수의 비율은 약 17%에 불과하며, 이는 해시 함수 설계와 정수 곱셈의 수학적 성질을 이해하는 데 흥미로운 통찰을 제공한다.
소프트웨어 프로그래밍에서 두 정수의 곱은 흔히 오버플로와 함께 고정된 비트 수로 계산된다. 8비트 정수를 생각해 보자. 127에 127을 곱하면 오버플로와 함께 8비트 부호 없는 정수로는 1을 얻게 된다. 실제 전체 곱은 16129이다. 16129를 표현하려면 보통 16비트 정밀도를 사용한다.
따라서 우리는 전체 곱이라는 개념을 갖게 된다. 두 32비트 정수의 전체 곱은 보통 64비트로 표현된다. 내가 골몰했던 질문은 모든 64비트 정수 중에서 두 32비트 정수의 곱으로 쓸 수 있는 값의 비율이 얼마인가 하는 것이다.
왜 이런 것이 중요한지 궁금할 수 있다.
우리는 종종 해시 함수를 설계한다. 해시 함수는 입력을 받아 무작위처럼 보이는 출력을 생성하는 특별한 함수다. 몇 년 전 나는 clhash라는 매우 빠른 해시 함수를 설계했다. 이것은 수백 바이트 이상인 문자열에 대해 매우 빠른 해시 함수다. clhash를 모른다면 한번 살펴보라. 그 자체로도 흥미롭다.
이 clhash 해시 함수는 암호학 응용에서 전형적인 한 종류의 곱셈을 사용한다. 나는 우리의 접근법이 표준 곱셈에 기반한 기법들과 비교해 장점이 있다고 주장하려고 했다. 예를 들어 보자. 32비트 정수에 대한 단순한 해시 함수는 최하위 비트들과 최상위 비트들을 곱할 수 있다.
// simpleHighLowHash는 단순한(그리고 약한) 32비트 해시이며
// 상위 16비트와 하위 16비트를 곱한다.
func simpleHighLowHash(x uint32) uint32 {
high := uint16(x >> 16)
low := uint16(x & 0xFFFF)
return uint32(high) * uint32(low)
}
아마 해시 함수가 균등하길 원할 것이다. 즉 가능한 모든 32비트 해시값이 동일한 확률로 나타나야 한다. 이 경우 그것이 가능하려면 해시 함수가 모든 32비트 해시값을 만들어낼 수 있어야 하지만, 실제로는 그렇지 않다.
위대한 수학자 Erdös는 두 n비트 값의 곱으로 생성될 수 있는 모든 2n비트 값의 비율이 n이 커질수록 0으로 간다는 것을 보였다. 이는 예를 들어 10000000비트 정수끼리 곱한다면, 생성되는 100000000000000비트 정수는 상대적으로 매우 적을 것임을 뜻한다. 그러나 32비트 정수나 64비트 정수 같은 실용적인 경우는 어떨까?
16비트 정수의 곱으로 32비트 곱을 만드는 경우까지는 이 문제를 브루트포스로 쉽게 풀 수 있다. 이 경우 32비트 수들 중 약간 5분의 1을 넘는 값만이 두 16비트 정수의 곱이다. 전체 32비트 정수의 약 80%는 이 해시로는 결코 만들어지지 않는다. 그러나 실행 시간은 지수적으로 증가하므로 브루트포스는 32비트까지 확장되지 않는다.
그렇다면 32비트 경우는 어떻게 할까? 즉 두 32비트 정수를 곱해 64비트 곱을 만들 때는 어떨까? 다음 함수는 64비트 값 중 얼마의 비율을 만들어낼 수 있을까?
func simpleHighLowHash(x uint64) uint64 {
high := uint32(x >> 16)
low := uint32(x & 0xFFFFFFFF)
return uint64(high) * uint64(low)
}
정확한 결과를 얻을 수 있을까?
그렇다!!!
Webster와 그의 동료들은 정확한 계산을 확장할 수 있도록 수학적 기반을 마련했다. 그리고 그는 친절하게도 자신의 코드를 공개했다.
두 32비트 정수의 곱으로 쓸 수 있는 64비트(부호 없는) 정수는 3,215,709,724,700,470,902개다. 이는 가능한 모든 값의 약 17%다.
그렇다면 실제로 어떤 곱이 주어졌을 때 그에 해당하는 정수 쌍을 계산하는 것은 어떨까? 한 가지 접근법은 먼저 그 수의 전체 소인수분해를 구한 뒤, 그 인수들을 이용해 2^32보다 엄격히 작은 모든 가능한 약수를 구성하는 것이다. 시작할 때 후보 집합에는 1만 넣고, 각 소인수로 기존 후보들에 반복적으로 곱해 나가되 결과가 2^32 아래에 머무는 경우만 유지한다. 중복을 피하기 위해 각 소인수의 중복도까지 포함해 고유한 소인수 단위로 처리할 수 있다. 마지막으로 2^32 아래의 가장 큰 약수인 최대 후보 m을 선택하고, 남는 값 n / m을 계산한 뒤 두 개의 32비트 인수로 유효하게 나눌 수 있는지 판단한다. 일반적으로 답이 존재하더라도 유일하지는 않다. 이 방법은 한쪽 값이 최대가 되는 쌍을 반환한다. Python에서는 코드는 다음과 같을 수 있다.
for p in factor_multiplicities:
new_candidates = []
for c in candidates:
for i in range(factor_multiplicities[p] + 1):
if c * (p ** i) < 2**32:
new_candidates.append(c * (p ** i))
for new_c in new_candidates:
candidates.append(new_c)
m = max(candidates)
print(f"Maximum candidate: {m}")
leftover = n // m
print(f"Leftover: {leftover}")
if leftover >= 2**32:
print("Leftover is too large, cannot find a suitable candidate.")
더 효율적인 알고리즘을 떠올릴 수도 있을 것이다. 나는 임의의 값을 하나 고르면 대개 실패한다는 점이 흥미롭다고 생각한다. 즉 대부분의 64비트 정수는 두 32비트 정수의 곱으로 쓸 수 없다.