Adler-32

From PGWiki

Adler-32회전 해시 알고리즘의 하나로서, rsync와 같은 파일 단위 비교에 흔히 사용된다.


알고리즘

이는 아래의 수식으로 표현된다.


\begin{align}
a(k,l) &= \left( \sum\limits_{i=k}^{l} X_{i} \right) \bmod M \\
b(k,l) &= \left( \sum\limits_{i=k}^{l} (l-i+1) X_{i} \right) \bmod M \\
s(k,l) &= a(k,l) + 2^{16}b(k,l)
\end{align}\,


마지막 식은 점화식을 사용하여 아래와 같이 표현할 수 있다.


\begin{align}
a(k+1, l+1) &= (a(k, l) - X_{k} + X_{i+1}) \bmod M \\
b(k+1, l+1) &= (b(k, l) - (l-k+1) X_{k} + a(k+1, l+1)) \bmod M
\end{align}\,


이런 연속적인 값을 계산하는 방식 때문에 파일 내의 모든 가능한 오프셋을 계산하기에 적합한 특징이 있다.

실제로, 이런 단순성에도 불구하고 서로 다른 두 블록에 대한 체크섬이 일치할 확률이 매우 낮은 것으로 판명됐으며, 이런 '약한' 체크섬이 일치하는 블럭에 대해서는 '비싸고 강한' 체크섬을 다시 수행한다.