20111221, 05:09  #1 
Apr 2011
10_{10} Posts 
FNV hash challenges
I'd like to introduce you to the FNV hash http://http://isthe.com/chongo/tech/comp/fnv/
It's a nonsecure fast hashing function which comes in 32 bit, 64 bit, 128 bit etc up to 1024 bit variants. The data is xor'ed a byte at a time with the lowest byte of the hash. The hash value is scrambled by multiplying it (implicitly modulo some power of two) by some reasonably large prime with certain qualities. One of the authors is Landon Curt Noll whom you might know from his (co)discovery of the 25th and 26th Mersenne primes. He posts a number of challenges which are related to finding the least amounts of various data that make various different lengths and variants of hash evaluate to zero. I have found the following results. I imagine some of them can be improved and I'm sure further solutions are within easy grasp. Richard Heylen Code:
Challenge 4 The following sequence of bytes hashes to 0 using 256bit FNV1 4 3 F4 7D 37 15 6D DB 3B 6 68 6F 7 E E 3B 67 6E 43 53 B 5F 5A 8 93 9 16 29 47 D9 4C 1B BD 7E 4 17 38 Almost certainly not the shortest! I expect the shortest to be around 32 or 33 bytes 64 bit challenge 26 9896220416391497057 0xff octets. 128 bit challenge 27 51139138437908895582755236659575676289 0xff octets. 256 bit challenge 28 97131011133992287498486593163611969370804776852056896483926280632417744608641 0xff octets. 512 bit challenge 29 6128069560680565762154610809270994844002410243950263544203784593223016843997229074085082851572518300032658461764572306161923537606398743616573611559921729 0xff octets. 1024 bit challenge 30 4166764246433767607724494876573975804622505745030609527621792267585710937616890594553925779695068802476882158450198220145355673110514058679168404976467984257866096202762399908749262502638467244974880573689710950382129343938209204537332169240214496817441992707505606573714649912424941734250024772314731200245 0xff octets. I'm not completely confident that this last value is the smallest. Last fiddled with by wblipp on 20111221 at 09:02 Reason: code tags and http link 
20111223, 16:07  #2 
Apr 2011
2·5 Posts 
wblipp the link is properly broken now. I don't know whether it was before. Please fix as I can't

20111223, 18:17  #3  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Two possible challenges  devarajkandadai  Miscellaneous Math  1  20131109 23:30 
Array vs Hash Table vs Map for QS  Sam Kennedy  Programming  1  20121225 23:25 
Deep Hash  diep  Math  5  20121005 17:44 
SHA1 Crypto Hash weakened  plandon  Lounge  0  20090616 13:55 
Pari hash table lookup  Joshua2  Software  5  20090223 22:59 