# Division method for a hash function

Please review the problem and explain each step of the solution listed below, and give me an example of an application which this property would be undesirable in a hash function.

problem

----------

Consider a version of the division method in which h(k) = k mod m, where m = (2^p) -1 and k is a character string interpreted in radix 2^p. Show that if a string x can be derived from string y by permuting its characters, then x and y hash to the same value. <B>Give an example of an application in which this property would be undesirable in a hash function.</B>

solution

---------

All permutations can be generated by a sequence of two character interchanges. If two arbitrary characters, i and j, are switched, then the values hash to the same place.

We consider two numbers x and y which have characters i and j interchanged, and i > j.

Note: in this solution xi = x sub i and xj = x sub j (same goes for y).

x - y = (xi - yi)(m + 1)^(i-1) + (xj - yj)(m+1)^(j-1)

= (xi - xj)(m + 1)^(i-1) - (xi - xj)(m+1)^(j-1)

= (xi - xj)[(m + 1)^(i-1) - (m + 1)^(j-1) ]

= (xi - xj)(m + 1)^(j-1) * [(m + 1)^(i-j) -1]

= (xi - xj)(m + 1)^(j-1) * [(m + 1) - 1] * Summation of (m + 1)^k [from k = 0 to i - j - 1]

= 0 mod m

© BrainMass Inc. brainmass.com October 9, 2019, 5:54 pm ad1c9bdddfhttps://brainmass.com/computer-science/random-number-generation/division-method-for-a-hash-function-71748

#### Solution Summary

Division method for a hash function is examined.