Some other discrete probabilistic algorithms

We analyzed an application of Freivald's technique for verifying matrix multiplication based on fingerprinting, giving an O(n²) procedure.

For another application based on fingerprinting, verifying equality of strings we found that for strings of the size 2³² bits by comparing their identical fingerprints of size less than 70 bits the probability that the strings differ is less than 2^-32. The fingerprint for a string S is defined as b(s) (modulo p) where b(S) is S interpreted as a binary number and p is a random prime less than 2⁷⁰.

We also looked at public key cryptography and especially the RCA cryptosystem. Like in the previous application the technique requires that large primes (200-300 decimal digits) can be found efficiently. The technique relies on the fact that it is not tractable to factor numbers that are products of two such big primes.