Checkout
checkout
view
Your Cart Your Cart: item(s)
Add to Shopping Cart
$2.19 Instant Download
Computer Science, Data Structures and Algorithms
Other

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.  Give an example of an application in which this property would be undesirable in a hash function.

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

By OTA:  Xiao Liu, MS

OTA Rating:  4.7/5

Your Price:  $2.19  (original value ~$27.93)

What's included:

  • Plain text response
  • Attachment(s):
    • hash.doc
$2.19 Download Add to Cart

Add to Shopping Cart
$2.19 Instant Download

Page generated in 0.0154 seconds

About Us ·  Contact Us ·  Samples ·  Solutions ·  Legal Terms and Conditions ·  Privacy Policy

©2008 SolutionLibrary.com

Search for Solutions About Us Samples