Fingerprinting

Supongamos que se quiere controlar si dos bitstrings x,y de longitud n son iguales o no. Los dos están en lugares separados y el envio de x a donde se encuentra y (y vice versa) es caro (n es por ejemplo del orden 10¹⁰).

Si se está dispuesto a tomar de vez en cuando una decisión equivocada, un método es calcular:

con p un número primo, H(x) el número entero representado por x y verificar si H_p(x) =H_p(y).

Lo anterior tiene como desventaja que se cometen errores sistemáticos. Usando un elemento estocástico los pueden convertir en errores no-sistemáticos que el usuario puede acotar.

Dado k y M;
Repeat k veces:
Elige arbitrariamente un número primo menor que M;
Calcula H_p(x), H_p(y);
Si son distintos: termina y concluye que son diferentes;
end repeat
Concluye que x=y.

Usando las propiedades de la distribución de conteo, se obtiene que la probabilidad P de que H_p(x) = H_p(y) sin que x=y, es igual a:

donde es el número de primos menor que M. Se tiene la propiedad que si 0< a < 2ⁿ, el número de primos que dividen a es acotado por . Entonces:

Dado que , se puede acotar fácilmente P.

La probabilidad de sacar una conclusión equivocada -dado que cada iteración es un evento independiente - es igual a P^k. Si el usuario está dispuesto de aceptar errores pero con una probabilidad (positiva) que él puede acotar, entonces se obtiene un algoritmo probabilístico más seguro y muchas veces también más rápido.