title: Impronta di Rabin
text: # Impronta di Rabin
  
  L'impronta di Rabin (Rabin fingerprint) è una funzione di rolling hash usata come fingerprint, definita tramite polinomi su un campo finito, proposta da Michael O. Rabin nel 1981.
  
  ## Definizione
  
  Dato un messaggio m di n-bit $m_0,...,m_{n-1},$ questo può essere interpretato come un polinomio di grado n-1 sul campo finito GF(2).
  
      $f(x)=m_{0}+m_{1}x+\ldots +m_{n-1}x^{n-1}$
  
  Dato un polinomio irriducibile $p(x)$ di grado k in GF(2), la fingerprint di m è il resto $r(x)$ della divisione di $f(x)$ per $p(x)$ su GF(2), che è un polinomio di grado al più k-1, ovvero un numero rappresentabile con k bit.
  
  ## Applicazioni
  
  Molte implementazioni dell'algoritmo di Rabin-Karp usano internamente l'impronta di Rabin come rolling hash. Il Low Bandwidth Network Filesystem (LBFS) usa l'impronta di Rabin per la suddivisione dei dati in blocchi a grandezza variabile resistenti alla traslazione.
  
  