mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2011-12-21, 05:09   #1
Rich
 
Apr 2011

1010 Posts
Default 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
Rich is offline   Reply With Quote
Old 2011-12-23, 16:07   #2
Rich
 
Apr 2011

2·5 Posts
Default

wblipp the link is properly broken now. I don't know whether it was before. Please fix as I can't
Rich is offline   Reply With Quote
Old 2011-12-23, 18:17   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by Rich View Post
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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Two possible challenges devarajkandadai Miscellaneous Math 1 2013-11-09 23:30
Array vs Hash Table vs Map for QS Sam Kennedy Programming 1 2012-12-25 23:25
Deep Hash diep Math 5 2012-10-05 17:44
SHA-1 Crypto Hash weakened plandon Lounge 0 2009-06-16 13:55
Pari hash table lookup Joshua2 Software 5 2009-02-23 22:59

All times are UTC. The time now is 08:25.


Sat Jul 24 08:25:03 UTC 2021 up 1 day, 2:54, 1 user, load averages: 1.40, 1.53, 1.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.