hashing values for sfor total of ( possible (rspairs notice that the number of (abpairs and the number of (rspairs is identicalthus each (rspair will correspond to exactly one (abpair if we can solve for (abin terms of and but that is easyas beforesubtracting equations yields ( ( (mod )which means that by multiplying both sides by the unique multiplicative inverse of ( (which must existsince is not zero and is prime)we obtain ain terms of and then follows finallythis means that the probability that and collide is equal to the probability that (mod )and the above analysis allows us to assume that and are chosen randomlyrather than and immediate intuition would place this probability at /mbut that would only be true if were an exact multiple of mand all possible (rspairs were equally likely since is primeand sthat is not exactly trueso more careful analysis is needed for given rthe number of values of that can collide mod is at most  / - (the - is because sit is easy to see that this is at most ( )/ thus the probability that and will generate collision is at most / (we divide by becauseas mentioned earlier in the proofthere are only choices for given rthis implies that the hash family is universal implementation of this hash function would seem to require two mod operationsone mod and the second mod figure shows simple implementation in ++assuming that is significantly less than because the computations must now be exactly as specifiedand thus overflow is no longer acceptablewe promote to long long computationswhich are at least bits howeverwe are allowed to choose any prime pas long as it is larger than henceit makes sense to choose prime that is most favorable for computations one such prime is prime numbers of this form are known as mersenne primesother mersenne primes include and just as multiplication by mersenne prime such as can be implemented by bit shift and subtracta mod operation involving mersenne prime can also be implemented by bit shift and an additionsuppose (mod pif we divide by ( )then ( rwhere qand rare the quotient and remainderrespectively thusr ( (mod pand since ( (mod )we obtain qr(mod pfigure implements this ideawhich is known as the carter-wegman trick on line the bit shift computes the quotient and the bitwise-and computes the remainder when dividing by ( )these bitwise operations work because ( is an exact power int universalhashint xint aint bint pint return static_caststatic_casta mfigure simple implementation of universal hashing