Re: who wants a crack at this

From: Francois Grieu (fgrieu_at_micronet.fr)
Date: 06/27/03 

Date: Fri, 27 Jun 2003 10:30:21 +0200

In article <fdbae11.0306261633.5bd9e666@posting.google.com>,
 roger_for_nntp@hotmail.com (Roger Fleming) wrote about:

> hash (possibly excepting an implicit mod 2^32) is:
> hash = c[0]* m**7 + c[1]* m**6 + c[2]* m**5 + c[3]* m**4
> + c[4]* m**3 + c[5]* m**2 + c[6]* m + c[7]

> Since m is known, all the values of m**i can be calculated in advance,
> leaving us with a simple linear equation on 8 unknowns - complicated
> very slightly by the small range of permitted values for c[].
>
> If m is 26 or greater, and an implicit mod 2^32 is _not_ done, then
> the solution is unique and can be trivially found the same way you
> would convert numbers into base m.

Indeed, save this should be m>=27, since each c[] is in [0..26]

> If a mod 2^32 is done, then there will be a small number
> (=~ 26* (m**8 - 1)/(m - 1) / 2**32 ) of candidates for each value,
> each of which can be easily found by adding the appropriate number
> of 2**32's, then converting to base m.

I think the mod 2^32 case is harder: you do not know "the appropriate
number of 2**32's" and for m on say 10 bits, it is too costly to
enumerate the roughly 2^40 possible values.

An educated brute force attack is to make a table of the 27^4 values
of hash - ( c[4]* m**3 + c[5]* m**2 + c[6]* m + c[7]) mod 2^32
and organize it in a quicly searchable data structure (like a hash
table); then for each of the 27^4 values of
(c[0]* m**7 + c[1]* m**6 + c[2]* m**5 + c[3]* m**4 ) mod 2^32
we try to find if there is an entry in the table with this value,
in which case we have found a solution. The expected number of
searches is about 1000 before a solution is found.
[As an optimization, we can use that numbers in the table are
clustered as 27^3 sequences of 27 consecutive numbers, which allows
for a much more efficient data structure]

I wonder what are the more general approaches to solve the problem,
say if the hash was mod 2^128, with 27 digits in [0..26]
(27^27 is about 2^128), and m an arbitrary odd 128 bits integer.

   François Grieu

Relevant Pages

  • Re: Hashes are good, but not good enough.
    ... PJH> the case where a hash is the appropriate data structure. ... RAM (but note that many databases also use hash-based indexes, so hashes ...
    (comp.lang.perl.misc)
  • Re: combining hashes
    ... >>> A hash is an ordered data structure indexed by a specific key. ... My mind's eye sees it differently. ... c> An array is ...
    (comp.lang.perl.misc)
  • Re: I am needing a gentle introduction to accessing a perl array from a reference
    ... The data structure here is nothing more than a flat array. ... There is no hash anywhere in your code up at the top... ... Returns a list consisting of all the keys of the named hash. ... We need an understanding of the data structure if we are ...
    (comp.lang.perl.misc)
  • Re: Hash order bug?
    ... a review of one's Data Structures course may be in order ... did I realize that the underlying data structure is a hash, ... If you need to iterate through a hash in order by key, ...
    (comp.lang.ruby)
  • Re: use SDBM_File - Cant use string as a HASH ref
    ... I'm trying to tie this kind of hash into SDBM ... DBM files can only store simple values like strings and numbers. ... serialize the data structure as a string before storing it in the DBM, ... there were 100 perfect squares ...
    (perl.beginners)