Algebraic Hashing

Algebraic Hashing은 polynomial modulo 2를 활용하는 Hash Function입니다.

key가 n개의 bit로 구성되고 결과물인 Hash code가 m개의 bit로 구성된다면

key는 각 계수가 key의 bit에 대응되는 (n - 1)차 다항식으로 만들 수 있고,

Hash code는 각 계수가 Hash code의 bit에 대응되는 (m - 1)차 다항식으로 만들 수 있습니다.

그리고 Hash Function에 사용되는 m차 다항식 P을 추가적으로 생성합니다.

P 또한 모든 계수가 0 혹은 1로 표현됩니다.

이러한 3개의 다항식들은 K(x) mod P(x) = H(x)와 같은 관계를 가지게 됩니다.

주의할 점은 mod연산은 integer를 계산하는 것처럼 나눗셈 연산을 하는 것이 아닌 xor연산을 한다는 것입니다.

예를 들어 n = 15, m = 10이고

P(x) = 1*x^10 + 0*x^9 + 1*x^8 + 0*x^7 + 0*x^6 + 1*x^5 + 1*x^4 + 0*x^3 + 1*x^2 + 1*x + 1*x^0  
K(x) = 1*x^14 + 1*x^13 + 1*x^12 + 0*x^11 + 1*x^10 + 0*x^9 + 1*x^8 + 0*x^7 + 0*x^6 + 1*x^5 + 1*x^4 + 0*x^3 + 1*x^2 + 1*x + 1*x^0 

이와 같은 가정 하에 Hash code를 구해보겠습니다.

K(x) mod P(x)를 쉽게 표현해본다면

                                           1 1 0 1 1
                      ______________________________
1 0 1 0 0 1 1 0 1 1 1| 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1
                   xor 1 0 1 0 0 1 1 0 1 1 1
                      ______________________________
                         1 0 0 1 1 0 0 1 0 0 0
                   xor   1 0 1 0 0 1 1 0 1 1 1
                      ______________________________
                           0 1 1 1 1 1 1 1 1 1 1
                   xor     0 0 0 0 0 0 0 0 0 0 0
                      ______________________________
                             1 1 1 1 1 1 1 1 1 1 1
                   xor       1 0 1 0 0 1 1 0 1 1 1
                      ______________________________
                               1 0 1 1 0 0 1 0 0 0 1   
                   xor         1 0 1 0 0 1 1 0 1 1 1
                      ______________________________
                               0 0 0 1 0 1 0 0 1 1 0 <= result

결과적으로 H(x) = x^7 + x^5 + x^2 + x, 0010100110이 Hash code가 됩니다.