mersenneforum.org FNV hash challenges
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-12-21, 05:09 #1 Rich   Apr 2011 2·5 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 non-secure 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 256-bit FNV-1 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 2011-12-21 at 09:02 Reason: code tags and http link
 2011-12-23, 16:07 #2 Rich   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
2011-12-23, 18:17   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Rich I'd like to introduce you to the FNV hash http://isthe.com/chongo/tech/comp/fnv/ It's a non-secure 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 256-bit FNV-1 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.
I bet the link I made in the quote works.

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Miscellaneous Math 1 2013-11-09 23:30 Sam Kennedy Programming 1 2012-12-25 23:25 diep Math 5 2012-10-05 17:44 plandon Lounge 0 2009-06-16 13:55 Joshua2 Software 5 2009-02-23 22:59

All times are UTC. The time now is 21:26.

Sun Jan 24 21:26:34 UTC 2021 up 52 days, 17:37, 0 users, load averages: 1.30, 1.87, 1.91