|
|
|
FNV Hash |
||
| [chongo's home] [Astronomy] [Mathematics] [Prime Numbers] [Programming] [Technology] [contacting Landon] | ||
FNV quick index
- The FNV Non-Cryptographic Hash Algorithm is now an Official IETF RFC 9923 !
- Visit the official: fnv GitHub repo
- A useful FNV-1a string calculators:
- A nice FNV-1 and FNV-1a HEX calculator: FNV-1 / FNV-1a hex
- An external FNV Wikipedia page exists
- History and use of the FNV hash
- FNV has been put into the public domain via the
Creative Commons CC0 1.0 Universal (CC0 1.0) Public Domain Dedication license.
![]()
- The FNV-1 hash in a nutshell
- The FNV-1a hash minor variation
- FNV-1/FNV-1a hash parameters
- A few remarks on FNV primes
- Changing the FNV hash size with xor-folding
- FNV hash with a non-power of 2 size
- FNV reference code
- Other FNV source code you might wish to consider
- A slight gcc optimization
- Can you help solve some of the zero hash challenges?
The basis of the FNV hash algorithm was taken from an idea sent as reviewer comments to the IEEE POSIX P1003.2 committee by Glenn Fowler and Phong Vo back in 1991. In a subsequent ballot round: Landon Curt Noll improved on their algorithm. Some people tried this hash and found that it worked rather well. In an Email message to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
FNV hashes are designed to be fast while maintaining a low collision rate. The FNV speed allows one to quickly hash lots of data while maintaining a reasonable collision rate. The high dispersion of the FNV hashes makes them well suited for hashing nearly identical strings such as URLs, hostnames, filenames, text, IP addresses, etc.
The FNV hash is in wide spread use:
FNV hash algorithms and source code been been put into the public domain via the following Creative Commons license:
CC0 1.0 Universal (CC0 1.0) Public Domain DedicationNo Copyright - CC0 - No Rights Reserved
![]()
The CC0 license means that the hash algorithms and source code has been dedicated to the public domain by waiving all of our rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law.
You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.
See the Creative Commons CC0 page for more details.
The authors of the FNV algorithm took deliberate steps to disclose the algorithm in a public forum soon after it was invented. More than a year passed after this public disclosure and the authors deliberately took no steps to patent the FNV algorithm. Therefore it is safe to say that the FNV authors have no patent claims on the FNV algorithm as published.
If you use an FNV function in an application, why not tell us about it by sending Email to:
Please include the phrase FNV hash function somewhere is the subject line of your Email.
There is no requirement to tell us you are using FNV, however if you do, we will be happy to add your application to the above list.
The core of the FNV-1 hash algorithm is as follows:
hash = offset_basis for each octet_of_data to be hashed hash = hash * FNV_prime hash = hash xor octet_of_data return hashThe offset_basis and FNV_prime can be found in the parameters of the FNV-1/FNV-1a hash section below.
NOTE: We recommend that you use the FNV-1a alternative algorithm instead of the FNV-1 hash where possible.
There is a minor variation of the FNV hash algorithm known as FNV-1a:
hash = offset_basis for each octet_of_data to be hashed hash = hash xor octet_of_data hash = hash * FNV_prime return hashThe only difference between the FNV-1a hash and the FNV-1 hash is the order of the xor and multiply. The FNV-1a hash uses the same FNV_prime and offset_basis as the FNV-1 hash of the same n-bit size.
The offset_basis and FNV_prime can be found in the parameters of the FNV-1/FNV-1a hash section below.
Some people use FNV-1a instead of FNV-1 because they see slightly better dispersion for tiny (<4 octets) chunks of memory.
One person reported that the FNV-1 hash was not as good as the FNV-1a hash, for their purposes, because the final octet is not as well dispersed. They reported that the FNV-1a hash was better for error detection, for example.
Other people report that either FNV-1 or FNV-1a make a fine hash. (Try it with with just a dash of Sage and ground Cloves :-))
NOTE: We recommend that you use the FNV-1a alternative algorithm instead of the FNV-1 hash where possible.
32 bit FNV_prime = 224 + 28 + 0x93 = 16777619
64 bit FNV_prime = 240 + 28 + 0xb3 = 1099511628211
128 bit FNV_prime = 288 + 28 + 0x3b = 309485009821345068724781371
256 bit FNV_prime = 2168 + 28 + 0x63 = 374144419156711147060143317175368453031918731002211
512 bit FNV_prime = 2344 + 28 + 0x57 =
35835915874844867368919076489095108449946327955754392558399825615420669938882575
126094039892345713852759
1024 bit FNV_prime = 2680 + 28 + 0x8d =
50164565101131186554345988110352789550307653454047907443030175238311120551081474
51509157692220295382716162651878526895249385292291816524375083746691371804094271
873160484737966720260389217684476157468082573
Part of the magic of FNV is the selection of the FNV_prime for a given sized unsigned integer. Some primes do hash better than other primes for a given integer size.
32 bit offset_basis = 2166136261
64 bit offset_basis = 14695981039346656037
128 bit offset_basis = 144066263297769815596495629667062367629
256 bit offset_basis =
100029257958052580907070968620625704837092796014241193945225284501741471925557
512 bit offset_basis =
96593031294966694980094354007163104660904187456726378961083743294344626579945829
32197716438449813051892206539805784495328239340083876191928701583869517785
1024 bit offset_basis =
14197795064947621068722070641403218320880622795441933960878474914617582723252296
73230371772215086409652120235554936562817466910857181476047101507614802975596980
40773201576924585630032153049571501574036444603635505054127112859663616102678680
82893823963790439336411086884584107735010676915
NOTE: Older versions of this web page incorrectly indicated that the 128 bit FNV_prime was 2168 + 28 + 0x59. This was not correct. While that satisfied all of the significant FNV_prime properties, it was not the smallest 128 bit FNV_prime. The 128 bit offset_basis changed from 275519064689413815358837431229664493455 to 144066263297769815596495629667062367629 was changed as a result of the 128 bit FNV_prime correction. (Sorry about that!)
These non-zero integers are the FNV-0 hashes of the following 32 octets:
chongo <Landon Curt Noll> /\../\
The \'s in the above string are not C-style escape characters. In C-string notation, these 32 octets are:
"chongo <Landon Curt Noll> /\\../\\"
Regarding the offset_basis value:
The switch from FNV-0 to FNV-1 was purely to change the offset_basis to a non-zero value. The selection of that non-zero value is arbitrary. The string:
was used because the tester was looking at an Email message from Landon in Landon's standard Email signature line. Actually the person who did that did not see very well. Landon, today, uses ()'s instead of <>'s and his ASCII bats use "oo" eyes instead of ".." as in:chongo <Landon Curt Noll> /\../\chongo (Landon Curt Noll) /\oo/\We didn't bother correcting her error because it does not matter. In the general case, almost any offset_basis will serve so long as it is non-zero.
The following calc script was used to compute the offset_basis for FNV-1 hashes:
hash_bits = insert_the_hash_size_in_bits_here; FNV_prime = insert_the_FNV_prime_here; offset_basis = 0; offset_str = "chongo <Landon Curt Noll> /\\../\\"; hash_mod = 2^hash_bits; str_len = strlen(offset_str); for (i=1; i <= str_len; ++i) { offset_basis = (offset_basis * FNV_prime) % hash_mod; offset_basis = xor(offset_basis, ord(substr(offset_str,i,1))); } print hash_bits, "bit offset_basis =", offset_basis;NOTE: The above code fragment example is written in the calc language, not in C.
FNV-0 Historic note: The FNV-0 is the historic FNV algorithm that is now deprecated. It has an offset_basis of 0. Unless the FNV-0 hash is required for historical purposes, the FNV-1 or FNV-1a should be used in place of the FNV-0 hash. Use FNV-1 and FNV-1a hashes, with their non-zero offset_basis instead. The FNV-0 hashes all buffers that contain only 0 octets to a hash value of 0. The FNV-1 and FNV-1a hash do not suffer from this minor problem.
While theory behind FNV_prime's is beyond the scope of this web page, the following text may suffice to satisfy the curious:One of the key properties to look for in an FNV_prime is how it impacts dispersion.
When s is an integer and 4 < s < 11, then FNV_prime is the smallest prime p of the form:
256int((5 + 2s)/12) + 28 + bsuch that:
- 0 < b < 28
- The number of one-bits in b is 4 or 5
- p mod 240 - 224 - 1 > 224 + 28 + 27
An FNV_prime that matches the above constraints tend to have better dispersion properties. They improve the polynomial feedback characteristic when an FNV_prime multiplies an intermediate hash value. The hash values produced are more scattered throughout the n-bit hash space.
It is a nice side effect that FNV_prime may be optimized by some compilers for some hardware. On some hardware, replacing the FNV_prime multiply with a set of shifts and adds will improve performance. In other cases where multiply may be pipelined (such as in vector mode), the set of shifts and adds may be sub-optimal. The FNV_prime were not selected for compiler optimization, they were selected for the quality of resulting hash function.
In the case where s = 5, both 16777499 and 16777619 could have been used. The narrowness of the 32-bit hash suggested that the larger prime might be better. It turned out that this level of caution was not warranted. When larger FNV hashes were developed, we opted to select the smallest prime. For compatibility with the original IEEE POSIX P1003.2 committee proposal, the historic FNV_prime for the s = 5 case was kept. The requirement that the FNV_prime mod 240 - 224 - 1 (1099494850559) must be > 224 + 28 + 27 (16777600) was added to harmonize the FNV_primes across 4 < s < 11.
The case where s < 5 is not considered because the resulting hash quality is too low. Such small hashes can, if desired, be derived from a 32 bit FNV hash by xor-folding.
The case where s > 10 is considered because the doubtful utility of such large FNV hashes and because the criteria for such large FNV_Primes is more complex, due to the sparsity of such large primes, and would needlessly clutter the criteria given above. The criteria above is a simplified form that fails to generate 2048-bit FNV_prime and a 4096-bit FNV_prime, for example. For such large primes we would need to use a more extensive prime selection criteria.
If you need an x-bit hash where x is not a power of 2, then we recommend that you compute the FNV hash that is just larger than x-bits and xor-fold the result down to x-bits. By xor-folding we mean shift the excess high order bits down and xor them with the lower x-bits.For example to produce a 24 bit FNV-1 hash in C we xor-fold fold a 32 bit FNV-1 hash:
#define MASK_24 (((u_int32_t)1<<24)-1) /* i.e., (u_int32_t)0xffffff */ #define FNV1_32_INIT ((u_int32_t)2166136261) u_int32_t hash; void *data; size_t data_len; hash = fnv_32_buf(data, data_len, FNV1_32_INIT); hash = (hash>>24) ^ (hash & MASK_24);To produce a 16 bit FNV-1 hash in C we xor-fold fold a 32 bit FNV-1 hash:
#define MASK_16 (((u_int32_t)1<<16)-1) /* i.e., (u_int32_t)0xffff */ #define FNV1_32_INIT ((u_int32_t)2166136261) u_int32_t hash; void *data; size_t data_len; hash = fnv_32_buf(data, data_len, FNV1_32_INIT); hash = (hash>>16) ^ (hash & MASK_16);To produce a 56 bit FNV-1 hash in C (on a machine with 64 bit unsigned values) we xor-fold fold a 64 bit FNV-1 hash:
#define MASK_56 (((u_int64_t)1<<56)-1) /* i.e., (u_int64_t)0xffffffffffffff */ #define FNV1_64_INIT ((u_int64_t)14695981039346656037) u_int64_t hash; void *data; size_t data_len; hash = fnv_64_buf(data, data_len, FNV1_64_INIT); hash = (hash>>56) ^ (hash & MASK_56);The above process assumes that you are using an FNV hash that at most twice as large as the x-bits that you need. For x < 16, there is no 16 bit (or less) FNV-1 hash to use.
For tiny x < 16 bit values, we recommend using a 32 bit FNV-1 hash as follows:
/* NOTE: for 0 < x < 16 ONLY!!! */ #define TINY_MASK(x) (((u_int32_t)1<<(x))-1) #define FNV1_32_INIT ((u_int32_t)2166136261) u_int32_t hash; void *data; size_t data_len; hash = fnv_32_buf(data, data_len, FNV1_32_INIT); hash = (((hash>>x) ^ hash) & TINY_MASK(x));At the expense of CPU performance, one may use a larger FNV-1 hash that is normally required in any of the above xor-folding examples. This will not produce the same standard output, but it may provide slightly better dispersion at the expense of more CPU time. All that is needed is to use a larger FNV-1 hash and to move the mask outside of the expression on the final statement.
For example, to produce a 24 bit FNV-1 hash could have used a 64 bit FNV-1 hash, in a non-standard way, as follows:
/* NOTE: non-standard use of a larger hash */ #define MASK_24 (((u_int64_t)1<<24)-1) /* i.e., (u_int64_t)0xffffff */ #define FNV1_64_INIT ((u_int64_t)14695981039346656037) u_int64_t hash; void *data; size_t data_len; hash = fnv_64_buf(data, data_len, FNV1_64_INIT); hash = (((hash>>24) ^ hash) & MASK_24);Replacing a 32 bit FNV-1 hash with a 64 bit FNV-1 hash during xor-folding might yield better dispersion at the expense of CPU time. However using an even larger FNV-1 hash is almost certainly a waste of CPU time. If you are going to use this non-standard xor-folding method, we recommend that you only do it for x < 32 bits, and only replace the 32 bit FNV-1 hash with a 64 bit FNV-1 hash.
NOTE: One may substitute the FNV-1a hash for the FNV-1 hash in any of the xor-folding examples. Some people believe that FNV-1a xor-folding gives then slightly better dispersion without any impact on CPU performance. See the FNV-1a hash description for more information.
If you really need an x-bit hash for x > 1024 bits, send us Email.
The FNV hash is designed for hash sizes that are a power of 2. If you need a hash size that is not a power of two, then you have two choices. One method id called the lazy mod mapping method and the other is called the retry method. Both involve mapping a range that is a power of 2 onto an arbitrary range.
For example, to produce a value between 0 and 2142779559 using the lazy mod mapping method, we select a 32-bit FNV hash because:
232 > 2142779559
We compute the 32-bit FNV hash value and then perform a final mod:
#define TRUE_HASH_SIZE ((u_int32_t)2142779560) /* range top plus 1 */ #define FNV1_32_INIT ((u_int32_t)2166136261) u_int32_t hash; void *data; size_t data_len; hash = fnv_32_buf(data, data_len, FNV1_32_INIT); hash %= TRUE_HASH_SIZE;
An advantage of the lazy mod mapping method is that it requires only 1 more operation: only an additional mod is performed at the end. The disadvantage of the lazy mod mapping method is that there is a bias against the larger values.
To understand this bias consider the a need to produce a value between 0 and 999999. We will compute a 32-bit FNV hash value because:
232 > 999999
We compute the 32-bit FNV hash value using the and then perform the final mod:
#define TRUE_HASH_SIZE ((u_int32_t)1000000) /* range top plus 1 */ #define FNV1_32_INIT ((u_int32_t)2166136261) u_int32_t hash; void *data; size_t data_len; hash = fnv_32_buf(data, data_len, FNV1_32_INIT); hash %= TRUE_HASH_SIZE;
The bias introduced by the final mod is slight. The values 0 through 967295 will be created by 4295 different 32-bit FNV hash values whereas the values 967296 through 999999 will be created by only 4294 different 32-bit FNV hash values. In other words, the values 0 through 967295 will occur ~1.0002328 times as often as the values 967296 through 999999.
The bias can be larger when the range is nearly as large as the range of values produced by the FNV hash. Consider using the lazy mod mapping method to produce values between 0 and 9999999999999999999. We use a 64-bit FNV hash because:
264 > 9999999999999999999
We compute the 64-bit FNV hash value using the and then perform the final mod:
#define TRUE_HASH_SIZE ((u_int64_t)10000000000000000000) /* range top plus 1 */ #define FNV1_64_INIT ((u_int64_t)14695981039346656037) u_int64_t hash; void *data; size_t data_len; hash = fnv_64_buf(data, data_len, FNV1_64_INIT); hash %= TRUE_HASH_SIZE;
Here the bias introduced by the final mod is more noticeable. The values 0 through 9999999999999999999 will be created by 2 different 64-bit FNV hash values whereas the values 10000000000000000000 through 18446744073709551615 will be created by only 1 64-bit FNV hash value.
NOTE: This bias issue may not be of concern to you, but we thought we should point out this issue just in case you care. Many applications should / will not care about this bias. Most applications can use the lazy mod mapping method without any problems. Your application, may vary however.
NOTE: One may substitute the FNV-1a hash for the FNV-1 hash in any of the lazy mod mapping method examples. Some people believe that FNV-1a lazy mod mapping method gives then slightly better dispersion without any impact on CPU performance. See the FNV-1a hash description for more information.
To produce a hash range between 0 and X use a n-bit FNV hash where n is smallest FNV hash that will produce values larger than X without the need for xor-folding.
For example, to produce a value between 0 and 49999 using the retry method, we select a 32-bit FNV hash because:
232 > 49999
Before the final mod 50000 is performed, we check to see if the 32-bit FNV hash value is one of the upper biased values. If it is, we perform additional loop cycles until is below the bias level. For example:
#define TRUE_HASH_SIZE ((u_int32_t)50000) /* range top plus 1 */
#define FNV_32_PRIME ((u_int32_t)16777619)
#define FNV1_32_INIT ((u_int32_t)2166136261)
#define MAX_32BIT ((u_int32_t)0xffffffff) /* largest 32 bit unsigned value */
#define RETRY_LEVEL ((MAX_32BIT / TRUE_HASH_SIZE) * TRUE_HASH_SIZE)
u_int32_t hash;
void *data;
size_t data_len;
hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
while (hash >= RETRY_LEVEL) {
hash = (hash * FNV_32_PRIME) + FNV1_32_INIT;
}
hash %= TRUE_HASH_SIZE;
The disadvantage of the retry method is that it sometimes requires additional calculations. An advantage of the retry method it avoids slightly biased values.
For another example, we will produce a value between 0 and 999999999999 using the retry method, we select a 64-bit FNV hash because:
264 > 999999999999
Before the final mod 1000000000000 is performed, we check to see if the 64-bit FNV hash value is one of the upper biased value. If it is, we perform additional loop cycles until it is not.
#define TRUE_HASH_SIZE ((u_int64_t)1000000000000) /* range top plus 1 */
#define FNV_64_PRIME ((u_int64_t)1099511628211)
#define FNV1_64_INIT ((u_int64_t)14695981039346656037)
#define MAX_64BIT ((u_int64_t)0xffffffffffffffff) /* largest 64 bit unsigned value */
#define RETRY_LEVEL ((MAX_64BIT / TRUE_HASH_SIZE) * TRUE_HASH_SIZE)
u_int64_t hash;
void *data;
size_t data_len;
hash = fnv_64_buf(data, data_len, FNV1_64_INIT);
while (hash >= RETRY_LEVEL) {
hash = (hash * FNV_64_PRIME) + FNV1_64_INIT;
}
hash %= TRUE_HASH_SIZE;
NOTE: One may substitute the FNV-1a hash for the FNV-1 hash in any of the retry method examples. Some people believe that FNV-1a retry method gives then slightly better dispersion without any impact on CPU performance. See the FNV-1a hash description for more information.
Pro: Yields the best results in the shortest amount of CPU time.
Con: Requires source code change to force hash range to be a power of 2 in size.
Pro: Yields the fastest results for a non-power of 2 range.
Con: Produces a slight bias against larger hash values. However if one does not care about the slight bias, then there is no problem using this technique.
Pro: Produces non-biased values for a non-power of 2 range.
Con: Requires slightly more CPU time in some cases.
FNV reference source
For up to date source, visit:
- official fnv GitHub repo
In the C source below, primes are provided for 32 bit and 64 bit unsigned integers. For compilers that do not implement the unsigned long long type, code is provided to quickly simulate the 64 bit multiply by the particular FNV_prime.
NOTE: As of version 5.0, the above source include test vectors for 32 bit and 64 bit versions of the FNV-0, FNV-1, and FNV-1a algorithms. The test_fnv.c file contains validated test vectors. To verify a compiled code, try:
- fnv source release (use the latest release) [updated: 2025 Mar 30]
- hash_32a.c - (32 bit FNV-1a algorithm)
- hash_64a.c - (64 bit FNV-1a algorithm)
- hash_32.c - (32 bit FNV-1 algorithm)
- hash_64.c - (64 bit FNV-1 algorithm)
- fnv.h - (FNV header file)
- fnv32.c - (32 bit FNV-0, FNV-1, and FNV-1a hash tool/demo) [updated: 2025 Mar 30]
- fnv64.c - (64 bit FNV-0, FNV-1, and FNV-1a hash tool/demo) updated: 2025 Mar 30]
- README.md - (README for the GitHub repo, plus how to install)
- Makefile - (Makefile to compile and install)
- have_ulong64.c - (64 bit unsigned integer type detector)
- test_fnv.c - (FNV test vectors)
make checkFor compiled code, try:
- fnv032 -t 1 -v
- fnv132 -t 1 -v
- fnv1a32 -t 1 -v
- fnv064 -t 1 -v
- fnv164 -t 1 -v
- fnv1a64 -t 1 -v
(top) Other FNV source code
Andy Allinger sent us this 32 bit FNV-1a subroutine written in FNV-1 in FORTRAN.
Nicola Bonelli has an implementation of FNV using the iovec interface:
Nicola Bonelli also wrote the following C++ FNV implementation:
Georgi Marinov (Georgi 'Kaze' 'Sanmayce') posted his very fast FNV-1a implementation:
- Best string-hash-function or an-open-letter to pro-programmer He offers this code as an C etude in spirit to our motto of:
Share and Enjoy! :-)Wayne Diamond implemented 32-bit FNV algorithm in PowerBASIC inline x86 assembly:
FUNCTION FNV32(BYVAL dwOffset AS DWORD, BYVAL dwLen AS DWORD, BYVAL offset_basis AS DWORD) AS DWORD #REGISTER NONE ! mov esi, dwOffset ;esi = ptr to buffer ! mov ecx, dwLen ;ecx = length of buffer (counter) ! mov eax, offset_basis ;set to 2166136261 for FNV-1 ! mov edi, &h01000193 ;FNV_32_PRIME = 16777619 ! xor ebx, ebx ;ebx = 0 nextbyte: ! mul edi ;eax = eax * FNV_32_PRIME ! mov bl, [esi] ;bl = byte from esi ! xor eax, ebx ;al = al xor bl ! inc esi ;esi = esi + 1 (buffer pos) ! dec ecx ;ecx = ecx - 1 (counter) ! jnz nextbyte ;if ecx is 0, jmp to NextByte ! mov FUNCTION, eax ;else, function = eax END FUNCTIONWayne said:
''Just thought I should let you know that I've ported the 32-bit FNV algorithm over to inline assembly. It's actually in PowerBASIC (www.powerbasic.com) format - a compiler I use, but the main function is all assembly. It could be optimized further in terms of saving a couple of clock cycles, but it's fairly optimized al ready - only 6 instructions in the main loop, plus 5 setup instructions, and compiles to just 33 bytes.''M.S.Schulte sent us these 32-bit FNV-1 and FNV-1a x86 assembler implementations (written in flat assembler), half of which were optimized for speed, the other half were optimized for size:
small_fnv32: ;FNV1 32bit (size: 31 bytes) ; Intel Core 2 Duo E6600: 354.20 mb/s push esi push edi mov esi, [esp + 0ch] ;buffer mov ecx, [esp + 10h] ;length mov eax, [esp + 14h] ;basis mov edi, 01000193h ;fnv_32_prime next: mul edi xor al, [esi] inc esi loop snext pop edi pop esi retn 0ch small_fnv32a: ;FNV1a 32bit (size: 31 bytes) ; Intel Core 2 Duo E6600: 327.68 mb/s push esi push edi mov esi, [esp + 0ch] ;buffer mov ecx, [esp + 10h] ;length mov eax, [esp + 14h] ;basis mov edi, 01000193h ;fnv_32_prime nexta: xor al, [esi] mul edi inc esi loop nexta pop edi pop esi retn 0ch fast_fnv32: ;FNV1 32bit (size: 36 bytes) ; Intel Core 2 Duo E6600: 565.12 mb/s push ebx push esi push edi mov esi, [esp + 10h] ;buffer mov ecx, [esp + 14h] ;length mov eax, [esp + 18h] ;basis mov edi, 01000193h ;fnv_32_prime xor ebx, ebx next: mul edi mov bl, [esi] xor eax, ebx inc esi dec ecx jnz next pop edi pop esi pop ebx retn 0ch fast_fnv32a: ;FNV1a 32bit (size: 36 bytes) ; Intel Core 2 Duo E6600: 574.95 mb/s push ebx push esi push edi mov esi, [esp + 10h] ;buffer mov ecx, [esp + 14h] ;length mov eax, [esp + 18h] ;basis mov edi, 01000193h ;fnv_32_prime xor ebx, ebx nexta: mov bl, [esi] xor eax, ebx mul edi inc esi dec ecx jnz nexta pop edi pop esi pop ebx retn 0ch
M.S.Schulte also sent us these 64-bit FNV-1 and FNV-1a x86 assembler implementations:
;FNV64 x86-64bit assembler implementation (written in flat assembler)
;FNV64-1 and FNV64-1a, both 37 bytes, (~284.13 mb/s Intel E8400)
;invoke fnv64,buffer,length,base (x64 Calling Convention)
fnv64:
mov rax, r8
mov r8, rdx
mov r9, 100000001b3h ;fnv_64_prime
xor r10, r10
next:
mul r9
mov r10b, [rcx]
xor rax, r10
inc rcx
dec r8
jnz next
ret
fnv64a:
mov rax, r8
mov r8, rdx
mov r9, 100000001b3h ;fnv_64_prime
xor r10, r10
nexta:
mov r10b, [rcx]
xor rax, r10
mul r9
inc rcx
dec r8
jnz nexta
ret
Jeffrey D. Webster has
an implementation of FNV32/64(a) written in "PurePerl" (as opposed to linking in an external C library).
David McIntosh
<Option Explicit
Public Function StrHash(text As String) As LongLong
Dim i As Long
Const mask As LongLong = &HFFFFFFFF^
Const prime As LongLong = 16777619
StrHash = 2166136261#
For i = 1 To Len(text)
StrHash = StrHash Xor Asc(Mid$(text, i, 1))
StrHash = (StrHash * prime) And mask
Next
End Function
It has been reported by several people that under the gcc compiler with -O3 on many AMD & Intel CPUs, that replacing the FNV_prime multiply with a expression of shifts and adds will improve the performance.Limited testing on our part confirmed that one can gain a few % in speed on an 1.6GHz AMD Athlon using gcc version 3.2.2 with -O3 optimization.
For a 32 bit FNV-1, we used:
while (bp < be) { /* multiply by the 32 bit FNV magic prime mod 2^32 */ #if defined(NO_FNV_GCC_OPTIMIZATION) hval *= FNV_32_PRIME; #else hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24); #endif /* xor the bottom with the current octet */ hval ^= (uint32_t)(*bp++); }For a 32 bit FNV-1a, we used:
while (bp < be) { /* xor the bottom with the current octet */ hval ^= (uint32_t)(*bp++); /* multiply by the 32 bit FNV magic prime mod 2^32 */ #if defined(NO_FNV_GCC_OPTIMIZATION) hval *= FNV_32_PRIME; #else hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24); #endif }For a 64 bit FNV-1, we used:
while (bp < be) { /* multiply by the 64 bit FNV magic prime mod 2^64 */ #if defined(NO_FNV_GCC_OPTIMIZATION) hval *= FNV_64_PRIME; #else hval += (hval << 1) + (hval << 4) + (hval << 5) + (hval << 7) + (hval << 8) + (hval << 40); #endif /* xor the bottom with the current octet */ hval ^= (uint64_t)(*bp++); }For a 64 bit FNV-1a, we used:
while (bp < be) { /* xor the bottom with the current octet */ hval ^= (uint64_t)(*bp++); /* multiply by the 64 bit FNV magic prime mod 2^64 */ #if defined(NO_FNV_GCC_OPTIMIZATION) hval *= FNV_64_PRIME; #else hval += (hval << 1) + (hval << 4) + (hval << 5) + (hval << 7) + (hval << 8) + (hval << 40); #endif }
We are interested in finding the shortest data sets, under certain constraints, that produce a FNV hash value of zero for the various sizes of the FNV-1 and FNV-1a hash function. Those who offer the best solution will receive fame and credit on the FNV web page.Zero-hash challenges:If you have a zero-value hash solution to an unsolved challenge, or if you have a better (shorted data segment) solution than one that is shown below, please send Email to:
Please use the subject line:
zero-hash challenge solutionNOTE: Please use the solution format used by Russ Cox (see below), if possible.
Please include the following information in your Email message:
- The challenge number you claim to have solved
- The name of the challenge you claim to have solved
- The length, in octets (8 bit bytes) of your proposed solution
- Who should we credit (i.e., how do you want us to credit you on our web page) for solving the challenge?
- A URL containing your proposed solution (optional)
NOTE: If your solution is large, please do not send the data set in the Email. Instead send is a URL where we can download your proposed challenge solution.
32-bit solution by Russ Cox <> on 2011-Mar-02:
There are 254 solutions of length 5, ranging from FNV32_1(01 47 6c 10 f3) = 0 to FNV32_1(fd 45 41 08 a0) = 0
Scott Pakin <> on 2011-Aug-22 reported that there are no solutions for binary data sets of length 7 or less.
64-bit solution by an anonymous scientist <
> on 2011-Oct-23:
There are no solutions for length 8. These are the solutions for length 9: FNV64_1(92 06 77 4c e0 2f 89 2a d2) = 0 FNV64_1(fb 6c 4f db 00 41 db c0 fe) = 0 FNV64_1(9f 72 72 35 80 4b 8d 6b 06) = 0 FNV64_1(3d 82 76 00 80 7c 52 62 1a) = 0 FNV64_1(58 21 f5 a2 e1 01 9d 80 e0) = 0 FNV64_1(52 a1 eb 10 a0 e9 45 96 05) = 0 FNV64_1(be 64 8a 14 e1 46 17 18 ff) = 0 FNV64_1(9e 50 1d f2 41 75 55 ac 05) = 0 FNV64_1(b3 92 a9 6f 80 e4 29 a4 63) = 0 FNV64_1(82 ba b3 41 81 0f db 83 15) = 0 FNV64_1(92 f4 6e 0e e1 b9 e5 45 2d) = 0 FNV64_1(3c ea 57 50 81 67 67 9b e0) = 0 FNV64_1(36 e3 96 34 e2 1d 36 00 61) = 0 FNV64_1(af fa ff ee 61 b0 5e c4 04) = 0 FNV64_1(d5 c9 88 15 02 2f d3 38 c2) = 0 FNV64_1(bc a7 38 51 e2 2f b1 1b 22) = 0 FNV64_1(70 f2 10 ba 02 45 37 b3 e8) = 0 FNV64_1(5b a3 a0 4e 81 fc 4f 32 5b) = 0 FNV64_1(cd 50 99 68 22 d4 78 2f b0) = 0 FNV64_1(fa ff 0d fa e2 f0 43 b4 9a) = 0 FNV64_1(16 3f ba 47 43 94 44 fe 86) = 0 FNV64_1(46 e0 03 71 c2 57 f0 bc da) = 0 FNV64_1(60 74 4a 52 e3 06 42 36 f2) = 0 FNV64_1(97 20 3a f8 a2 f6 8a 62 a6) = 0 FNV64_1(98 f5 cc d5 03 32 22 1a e2) = 0 FNV64_1(5d d5 14 e8 e3 43 8b 5a 9e) = 0 FNV64_1(95 b8 11 62 03 5a ed d2 cb) = 0 FNV64_1(f9 cb 23 1d 03 71 c5 ca 5c) = 0 FNV64_1(c3 04 1c 59 82 a5 aa 9b 55) = 0 FNV64_1(68 10 80 61 a3 5e 72 31 48) = 0 FNV64_1(43 0a eb 89 c2 c1 9d d8 2a) = 0 FNV64_1(5a a3 e3 40 23 ce 90 bc a2) = 0 FNV64_1(27 e1 3f aa a3 8f af 6a 51) = 0 FNV64_1(0c 5b ac 36 24 22 a2 7c 24) = 0 FNV64_1(ea bc d7 7c 24 49 58 66 57) = 0 FNV64_1(5a 30 62 51 83 9c 97 c3 75) = 0 FNV64_1(7a 18 75 d3 c3 88 65 0b 3a) = 0 FNV64_1(02 38 25 95 25 0b 3b 0c a8) = 0 FNV64_1(33 1c ae dd 83 fc 55 f4 63) = 0 FNV64_1(cb 87 3d b9 e5 38 0b bd ca) = 0 FNV64_1(3a 25 ba 67 a4 c7 49 80 e9) = 0 FNV64_1(49 14 3b 94 05 63 b5 de d6) = 0 FNV64_1(45 fb 0d 28 45 19 66 63 27) = 0 FNV64_1(92 7a e5 a6 e5 88 ba 55 68) = 0 FNV64_1(c3 93 7c 11 c4 1a 2f e0 8b) = 0 FNV64_1(a1 d8 5e 71 a5 6a 96 5e 64) = 0 FNV64_1(77 7b d7 7d 05 dc 73 64 c3) = 0 FNV64_1(3d 3f d4 d6 a6 71 b2 9d 65) = 0 FNV64_1(8d 45 9e d0 27 66 b4 46 34) = 0 FNV64_1(f1 da 16 a1 85 fe 43 a7 30) = 0 FNV64_1(97 6b 02 e3 66 10 3d 6e ab) = 0 FNV64_1(84 2b d9 13 a7 25 5a 8a 22) = 0 FNV64_1(0c 2b 2f d2 28 3a 91 df 95) = 0 FNV64_1(1c 01 ed aa 47 2f 64 6a 8b) = 0 FNV64_1(71 66 6f 98 47 74 48 eb 39) = 0 FNV64_1(2b b3 61 de e8 6c 33 fd 32) = 0 FNV64_1(c5 33 7e c3 87 9c 0c 24 4b) = 0 FNV64_1(b7 44 ea 2c a8 59 bc fc c5) = 0 FNV64_1(b2 8c 40 98 67 46 6f ce 35) = 0 FNV64_1(04 34 61 b3 87 d4 e5 1a 7f) = 0 FNV64_1(20 ba 15 17 e8 dd d9 f6 19) = 0 FNV64_1(36 c4 d3 ef 88 53 6e 86 56) = 0 FNV64_1(32 55 ce f0 48 73 af 8d 9d) = 0 FNV64_1(18 3c d8 70 08 71 6a 47 a3) = 0 FNV64_1(a8 ad fb 29 a8 e4 8e 82 c4) = 0 FNV64_1(47 47 bf 58 08 7f ab bc 34) = 0 FNV64_1(8f 68 71 3a e9 56 8f d0 0f) = 0 FNV64_1(64 5e dc 14 88 93 8d b4 35) = 0 FNV64_1(b4 33 d0 6d 48 bb 3a 5d 3d) = 0 FNV64_1(22 e4 4d 0a 48 bd 95 1e 8e) = 0 FNV64_1(78 6e 06 7d 48 ce db 12 33) = 0 FNV64_1(7e 1f 4d 02 48 f8 d2 a5 c2) = 0 FNV64_1(90 6b 26 4e c7 ef 12 f2 20) = 0 FNV64_1(90 10 a8 21 09 16 22 57 bc) = 0 FNV64_1(5b 1a 8c bc 09 2c a4 2d 9c) = 0 FNV64_1(2c 1a 6e 44 a9 7d 98 e0 39) = 0 FNV64_1(8a 2b 35 ab 49 97 d5 f7 bc) = 0 FNV64_1(29 bc 62 5e 0a 4e 9e 34 40) = 0 FNV64_1(e7 e6 c7 00 aa d3 26 5a 4a) = 0 FNV64_1(7e 65 e5 51 2b 66 e8 b5 b2) = 0 FNV64_1(2b d7 cf 6a 6a 6f b4 56 c9) = 0 FNV64_1(33 51 09 af ab 42 80 8b 07) = 0 FNV64_1(d1 78 30 6b c9 9c af 1f d4) = 0 FNV64_1(c6 00 f9 bf 4b 38 f0 00 c6) = 0 FNV64_1(a1 81 99 9a c9 f2 8e 4c 6f) = 0 FNV64_1(b3 d1 6c 57 2c 62 3c b0 5c) = 0 FNV64_1(c7 50 c1 4d ec de 91 e8 fd) = 0 FNV64_1(54 51 fe aa ec e9 6b f2 a2) = 0 FNV64_1(5d dc 27 f3 4b c8 b0 9a c9) = 0 FNV64_1(d2 4d e1 77 8c 0a 8f 2d 44) = 0 FNV64_1(ce e4 e5 80 ca 8a 07 dc 67) = 0 FNV64_1(0f d0 8f 67 ca 9f 94 a5 86) = 0 FNV64_1(89 e9 ed dd ed 84 84 50 26) = 0 FNV64_1(76 f5 be 03 ac 82 5a 09 26) = 0 FNV64_1(f8 71 02 ca 6c 6d a5 ae fc) = 0 FNV64_1(e8 cb 80 56 ad 00 a0 d1 d2) = 0 FNV64_1(88 89 0c dd 0c cf b2 5d d7) = 0 FNV64_1(69 ad 8f db 0d 03 8a ca 37) = 0 FNV64_1(96 58 24 93 cb bf d7 f1 fe) = 0 FNV64_1(ee b1 f6 d2 6d 9b 46 7d 3f) = 0 FNV64_1(de 64 18 d6 2e 86 5b 3c 0c) = 0 FNV64_1(24 05 66 e4 0d f1 c8 b1 d3) = 0 FNV64_1(77 d7 5f 5f ef 81 2d b3 37) = 0 FNV64_1(58 53 f5 b5 2e ec 51 fe 25) = 0 FNV64_1(ba 65 2a 3b 8e c6 bb a8 b6) = 0 FNV64_1(e5 81 4f 09 f0 0c ec f9 fa) = 0 FNV64_1(50 5b e8 f9 f0 6a 47 b4 64) = 0 FNV64_1(d3 0e f4 c7 6e d9 60 31 b5) = 0 FNV64_1(58 e4 4a 3c cd 97 d6 fd 84) = 0 FNV64_1(6f 82 aa ca 2f e7 1a 8d b1) = 0 FNV64_1(8f 50 ec 2f 2f e7 30 4c db) = 0 FNV64_1(f0 3b 01 db 6f 33 db 82 41) = 0 FNV64_1(13 3c 71 e4 8f 75 46 48 8f) = 0 FNV64_1(2f a5 a5 41 cd f5 b4 c6 45) = 0 FNV64_1(8b 1a 4c 12 30 38 c3 61 08) = 0 FNV64_1(6f 9c 5c 3f 8f d6 47 70 f7) = 0 FNV64_1(c1 0e 16 18 50 1b 47 48 f8) = 0 FNV64_1(2b 94 3f ad 30 ad 5e c4 85) = 0 FNV64_1(5f 55 92 c6 ce b9 f5 05 08) = 0 FNV64_1(42 8e 3a bb f1 bd 08 09 25) = 0 FNV64_1(28 84 f5 2b ce f1 3e 47 41) = 0 FNV64_1(25 d1 2c bf 90 5c 71 24 85) = 0 FNV64_1(d0 25 3d f3 90 64 67 ae f9) = 0 FNV64_1(c5 1d e5 36 11 a9 7b 4d e0) = 0 FNV64_1(88 c2 24 da 50 f9 55 03 dc) = 0 FNV64_1(ff 54 4f 75 cf 6d bb c4 4b) = 0 FNV64_1(9e 49 c2 63 11 d7 b0 74 25) = 0 FNV64_1(ac b1 42 65 cf 7d 84 0e 37) = 0 FNV64_1(05 a5 28 18 11 e3 0d 6a aa) = 0 FNV64_1(03 8d 11 ce f2 6f 0e 0a cf) = 0 FNV64_1(bf d6 88 3d 51 75 18 67 0e) = 0 FNV64_1(69 a2 dd 69 cf e4 94 5e e3) = 0 FNV64_1(e4 62 0b 95 b1 58 a1 d4 25) = 0 FNV64_1(c0 75 c6 ec 51 9e d4 c7 4c) = 0 FNV64_1(83 9d b3 97 32 54 9b 04 ec) = 0 FNV64_1(9a 7f 71 94 32 cf bb 97 38) = 0 FNV64_1(7a 4f e4 60 13 93 fd 7d 50) = 0 FNV64_1(76 48 71 f5 52 2f cb f7 e2) = 0 FNV64_1(da 0e 88 1f 13 ba d5 a7 2f) = 0 FNV64_1(2a be ca e7 33 12 4e 33 26) = 0 FNV64_1(79 ce 5e ee 92 27 5d c7 17) = 0 FNV64_1(36 91 77 d3 72 5a de 9f 0b) = 0 FNV64_1(3a 33 cd 8d 52 7a b8 2a d8) = 0 FNV64_1(25 66 ec c3 52 8b d0 13 4f) = 0 FNV64_1(de d7 a1 1f b2 58 65 d8 d7) = 0 FNV64_1(8a e5 cb 54 33 b0 de 92 42) = 0 FNV64_1(71 49 0a bb 33 d8 35 b3 59) = 0 FNV64_1(03 36 3b 64 f4 98 4b 21 99) = 0 FNV64_1(8c f5 50 02 d2 10 db 86 1d) = 0 FNV64_1(c3 4f cf 6e 93 4e b5 d8 b4) = 0 FNV64_1(2a fb 95 75 73 8c 85 76 82) = 0 FNV64_1(35 c0 2a 8b f5 56 45 66 45) = 0 FNV64_1(68 2a 76 44 73 cf 31 3a 8e) = 0 FNV64_1(98 4c a0 05 93 9a cf 65 a1) = 0 FNV64_1(a5 3e 3b f8 94 0e 6e 74 73) = 0 FNV64_1(4b 75 16 e9 35 47 e2 af 21) = 0 FNV64_1(3c 84 fb ee f6 10 6c 09 3f) = 0 FNV64_1(45 52 87 53 74 7c 1b 2c a1) = 0 FNV64_1(a0 8b 28 e0 d3 34 be 90 cb) = 0 FNV64_1(67 57 50 d0 16 3c 23 af e1) = 0 FNV64_1(a8 a6 4d 44 16 52 57 ba 95) = 0 FNV64_1(9e 0c be 6a 75 1d 3f 6c 20) = 0 FNV64_1(14 1b 43 7a b5 4e 40 88 b0) = 0 FNV64_1(68 3b bd d6 f7 ae d7 f9 28) = 0 FNV64_1(ab c0 61 a3 76 20 b8 f7 3b) = 0 FNV64_1(05 e8 00 91 b5 dd be 7e af) = 0 FNV64_1(14 dd 60 a4 96 19 04 05 16) = 0 FNV64_1(7e e5 14 cd 76 87 03 4c 2d) = 0 FNV64_1(07 f0 09 29 18 7d 7d fe 8a) = 0 FNV64_1(b9 b4 a5 c6 37 99 fd 49 ff) = 0 FNV64_1(d2 dd 5a 63 37 e4 08 8e d4) = 0 FNV64_1(a2 0b f2 5e 76 fd 65 2c 80) = 0 FNV64_1(c8 d7 df ba 37 e8 d9 2b 0c) = 0 FNV64_1(6e 40 03 eb 37 ea eb a6 93) = 0 FNV64_1(27 f9 53 0f 37 fc 0e 28 60) = 0 FNV64_1(c2 72 49 23 d5 ce 7e bb ef) = 0 FNV64_1(3e 11 d8 6b b6 e9 30 2f ab) = 0 FNV64_1(0e dd b7 d7 19 45 86 d7 79) = 0 FNV64_1(a3 f7 21 85 97 07 7d e1 4b) = 0 FNV64_1(4e 76 21 ee 19 67 54 55 23) = 0 FNV64_1(0f 19 18 da 38 60 1c 0b 9c) = 0 FNV64_1(a4 91 5d 2c 77 7f b4 cb c6) = 0 FNV64_1(c1 b7 ee 41 19 7a 60 4d 7e) = 0 FNV64_1(88 47 7b 0c d6 4c e0 c1 20) = 0 FNV64_1(73 88 eb 4f d6 53 4f 7c 6a) = 0 FNV64_1(f4 5a e5 b3 f9 cf 96 88 8f) = 0 FNV64_1(ba 5c b1 28 58 2f 33 16 cc) = 0 FNV64_1(04 cd 1f c8 1a 7a 20 f1 d0) = 0 FNV64_1(5f 2c 1c 63 b8 48 83 82 a4) = 0 FNV64_1(22 f5 ed a6 98 51 eb a3 f8) = 0 FNV64_1(f8 6b 6d 33 fa 65 24 bd 5c) = 0 FNV64_1(10 3b b6 ae d7 86 73 25 d3) = 0 FNV64_1(52 31 6c 5a 79 03 be 55 95) = 0 FNV64_1(af c9 ab 5e 1b 54 de 1d 84) = 0 FNV64_1(c2 ed f4 36 79 77 81 0d ee) = 0 FNV64_1(36 f5 db eb d8 30 d9 69 f6) = 0 FNV64_1(43 84 92 b9 79 90 66 a4 e6) = 0 FNV64_1(7d e9 4d 0e 1b da 69 eb 57) = 0 FNV64_1(2d 03 20 62 fb 3b 6e 88 65) = 0 FNV64_1(e5 69 ec d2 79 be d8 aa 8e) = 0 FNV64_1(ac 26 0a dd fb 68 43 1f 6d) = 0 FNV64_1(3c 96 c1 be 3a be 22 ae 76) = 0 FNV64_1(de 73 09 f1 1c 39 67 8a 0c) = 0 FNV64_1(56 2e 5f 2c 3a fd 30 40 7d) = 0 FNV64_1(68 57 ce 1c 59 e0 e0 eb 04) = 0 FNV64_1(df f7 e6 75 1c 66 88 86 90) = 0 FNV64_1(fd af f5 8b 5a 06 ae 0b 40) = 0 FNV64_1(4e cf a7 e9 1c 93 af 36 a8) = 0 FNV64_1(56 dc 13 cf fc 12 88 bb b8) = 0 FNV64_1(1f 5f c2 b2 3b 75 fb 7c 92) = 0 FNV64_1(4e 9c bb ba 5a 74 e3 a4 e1) = 0 FNV64_1(0b a0 c8 c5 1d 99 06 87 5e) = 0 FNV64_1(ff ef b0 25 1d f4 9d df db) = 0 FNV64_1(09 67 cb 8f 7c 13 3c 75 97) = 0 FNV64_1(05 bf fe 4d fd d2 6e 61 64) = 0 FNV64_1(a4 d7 4b 6d 3d 2a bb ee 4c) = 0 FNV64_1(b9 8c 01 cb 5b f2 50 15 f0) = 0 FNV64_1(31 45 17 91 1e a3 7f 25 52) = 0 FNV64_1(10 6c 0c 98 db 0f 9b 1e 88) = 0 FNV64_1(06 ec cc b6 9b da a2 3a 16) = 0 FNV64_1(23 66 38 19 7c ac 80 d3 78) = 0 FNV64_1(b8 f3 d7 98 bc 11 60 0f bf) = 0 FNV64_1(27 24 2d a8 db c2 99 28 65) = 0 FNV64_1(64 61 39 c2 bc 79 b5 b1 a6) = 0 FNV64_1(df ff 2a 12 5c fb 42 6d 01) = 0 FNV64_1(af 1d ea 4e ff 0d 46 95 5e) = 0 FNV64_1(2a b0 c6 54 9c e9 98 43 e1) = 0 FNV64_1(7c e5 9e 74 7d c8 44 ef 9e) = 0 FNV64_1(56 14 d1 31 dc ce 77 17 c3) = 0 FNV64_1(ed 6b 65 68 3f 05 36 41 9b) = 0 FNV64_1(2f d2 24 7e dd 19 4f 91 72) = 0 FNV64_1(c8 96 f0 54 9d 92 5b cc b1) = 0 FNV64_1(47 5d 76 63 be 17 24 ad d4) = 0 FNV64_1(4f 88 0b 03 9e 4a 48 ee 14) = 0 FNV64_1(26 ec 1b 56 5e b8 5d 5e 39) = 0 FNV64_1(c3 a8 2d 1a 5e fc b7 81 49) = 0 FNV64_1(14 3a 3b 0b be e7 b2 4d 75) = 0 FNV64_1(27 a0 f4 22 df b5 b6 5e 4a) = 0
Richard Heylen <> found a 128-bit FNV-1 solution on 2011-Dec-01:
The following is a solution of length 17: FNV128_1(20 28 4e 43 40 55 6f 99 25 1b 89 f4 a8 18 ec 76 c0) = 0128-bit solution by Johann N. Löfflmann on 2026-Nov-11:
These are 1 solution of length 16: FNV128_1(64 5e 06 74 86 07 80 54 48 9e 41 ff 0d 45 f5 af) = 0According to Johann N. Löfflmann: Each solution was verified independently with the FNV-1-128 implementation of Jacksum:
prints:jacksum -a fnv-1_128 -X -q hex:<hex>00000000000000000000000000000000Is 16 the shortest length, and are these all solutions of length 16? Yes.All lengths up to 16 were searched exhaustively:
- n = 1..6: exact meet-in-the-middle search in Python (stores all states after the first ceil(n/2) octets and looks up all states computed backwards from the hash 0). No solution.
- n = 7..16: the lattice search described below, run in its exhaustive mode: no pruning, and a ball that contains the whole admissible range, so every data set of the given length with hash 0 is found.
Brute force is infeasible (256^16 = 2^128), so the search uses lattice reduction:
- FNV-1 multiplies first and XORs afterwards, so FNV-1(c_1..c_n) = FNV-1a'(c_1..c_(n-1)) XOR c_n, where FNV-1a' is FNV-1a with the offset basis basis * P. The hash is 0 iff FNV-1a'(c_1..c_(n-1)) = c_n. This has exactly the form of the FNV-1a problem, with a different start value.
- An octet only changes the lowest 8 bits of the state. With u_i = (h_(i-1) XOR c_i) mod 256 and r_i = h_i mod 256 = (59 * u_i) mod 256 (59 = FNV prime mod 256), the recurrence can be written exactly as G_i = (G_(i-1) + u_i) * P - r_i (mod 2^128), with G_i = h_i - r_i. The hash is 0 iff G_(n-1) = 0 and the last octet equals r_(n-1).
- For a fixed prefix of a few octets, the remaining positions give a modular knapsack with small unknowns 0 <= u_t, r_t <= 255. This is a closest-vector problem in a fixed lattice (dimension 26 for lengths 16 and 17, with prefixes of 2 and 3 octets); only the target depends on the prefix.
- The lattice is reduced once with exact integer LLL and BKZ. Then, for every prefix, Schnorr-Euchner enumeration lists all lattice points in a ball around the centre of the cube [0,255]^(2M) that contains the whole cube. Every such point is a data set (c = s XOR u); it is accepted only if the full 128-bit FNV-1 hash, recomputed with Jacksum, is 0.
The meet-in-the-middle part takes about 30 seconds, the lattice search of lengths 7 to 15 less than a second, and length 16 took 2 seconds on 14 cores.
Richard Heylen <> found a 256-bit FNV-1 solution on 2011-Dec-17:
The following is a solution of length 37: FNV256_1(04 03 F4 7D 37 15 6D DB 3B 06 68 6F 07 0E 0E 3B 67 6E 43 53 0B 5F 5A 08 93 09 16 29 47 D9 4C 1B BD 7E 04 17 38 0A) = 0256-bit solution by Johann N. Löfflmann on 2026-Nov-10:
These are 1 solution of length 32: FNV256_1(79 21 a5 26 44 8e 73 36 74 94 c1 19 90 d8 80 57 a3 53 96 f0 a7 d4 d1 6b 77 5e c9 c0 29 f8 46 ce) = 0According to Johann N. Löfflmann: Each solution was verified independently with the FNV-1-256 implementation of Jacksum:
prints:jacksum -a fnv-1_256 -X -q hex:<hex>0000000000000000000000000000000000000000000000000000000000000000Then using a short arbitrary-precision Python implementation with:offset basis 100029257958052580907070968620625704837092796014241193945225284501741471925557, prime 2^168 + 2^8 + 0x63Johann N. Löfflmann writes:
Is 32 the shortest length? Maybe.A counting argument gives 256^n / 2^256 = 2^(8n - 256) expected solutions of length n: 1 for n = 32, 1/256 for n = 31, and less than 0.004 for all lengths up to 31 together. Under the usual assumption that FNV-1-256 behaves like a random function, the probability that a shorter solution exists is therefore below 0.4 %, even without any search.
For length 31 I additionally ran a deterministic search without pruning: for each of the 256 prefixes, all lattice points in the ball of squared radius 1.5 times the mean squared distance of the points of the cube [0,255]^58 from its centre were listed (45 minutes on 14 cores). None of them is a solution. So there is no solution of length 31 inside this ball; this part is a proof, not an estimate. The ball contains more than 99.996% of the points of the cube (computed exactly by convolving the distribution of the squared distance per coordinate). If the solutions are spread evenly over the cube, a solution of length 31 outside the ball exists with probability below 3.3e-5 * 1/256 = 1.3e-7. The same search for the lengths 30, 29 and 28 (lattice dimensions 56, 54 and 52, 15 seconds together) found nothing either; these balls contain more than 99.99% of their cubes, so the remaining probability is below 1e-9. Lengths up to 27 contribute less than 2^-40 by the counting argument. Altogether, a solution shorter than 32 exists with probability below 1.4e-7.
A fully exhaustive search would need a ball that contains the whole cube (squared radius 3 times the mean); its volume is 2^57 times that of the cube, which is out of reach.
Two independent searches of length 32 with different lattices (prefixes of 1 and of 2 octets, 10 and 20 randomized rounds) both found exactly this one solution and no other, so it is probably the only solution of length 32.
Brute force is infeasible (256^32 = 2^256), so the search uses lattice reduction:
- FNV-1 multiplies first and XORs afterwards, so FNV-1(c_1..c_n) = FNV-1a'(c_1..c_(n-1)) XOR c_n, where FNV-1a' is FNV-1a with the offset basis basis * P. The hash is 0 iff FNV-1a'(c_1..c_(n-1)) = c_n. This has exactly the form of the FNV-1a problem, with a different start value.
- An octet only changes the lowest 8 bits of the state. With u_i = (h_(i-1) XOR c_i) mod 256 and r_i = h_i mod 256 = (99 * u_i) mod 256 (99 = FNV prime mod 256), the recurrence can be written exactly as G_i = (G_(i-1) + u_i) * P - r_i (mod 2^256), with G_i = h_i - r_i. The hash is 0 iff G_(n-1) = 0 and the last octet equals r_(n-1).
- For a fixed prefix of 1 or 2 octets, the remaining 30 or 29 positions give a modular knapsack with small unknowns 0 <= u_t, r_t <= 255. This is a closest-vector problem in a fixed lattice of dimension 60 or 58; only the target depends on the prefix.
- The lattice is reduced once with exact integer LLL and BKZ-20. Then, for every prefix, Schnorr-Euchner enumeration with pruning ("extreme pruning": several rounds with randomly weighted metrics and re-randomized bases) lists the lattice points near the center of the cube [0,255]^(2M). Every such point is a binary data set (c = s XOR u); it is accepted only if the full 256-bit FNV-1 hash, recomputed with Jacksum, is 0.
- As a check, the same program, run exhaustively without pruning, reproduces exactly the published results of the binary challenges 1, 2, 7 and 8 (32 and 64 bits, FNV-1 and FNV-1a): the 254 solutions of length 5, the 238 solutions of length 9, the 2 solutions of length 4 and the single solution of length 8, and no solution of the next shorter length for challenges 1, 2 and 8. A separate meet-in-the-middle program confirms the 2 solutions of length 4 and none shorter for challenge 7, and no solution shorter than 5 for challenge 1.
The search of length 32 takes less than a minute on 14 cores.
32-bit solution by Russ Cox <> on 2011-Mar-02:
The solutions of length 4 are: FNV32_1a(cc 24 31 c4) = 0 FNV32_1a(e0 4d 9f cb) = 0
Scott Pakin <> on 2011-Aug-22 reported that there are no solutions for binary data sets of length 7 or smaller.
64-bit solution by an anonymous scientist <
> on 2011-Oct-23:
The only solution for length 8 is: FNV64_1a(d5 6b b9 53 42 87 08 36) = 0
Richard Heylen <> found a 128-bit FNV-1a solution on 2011-Dec-01:
The following are 251 solutions of length 17: FNV128_1a(00 64 5e 06 74 86 07 80 54 48 9e 41 ff 0d 45 f5 af) = 0 FNV128_1a(01 05 ad 81 e0 b7 3e 3f cb a0 72 bb bc 66 37 b2 24) = 0 FNV128_1a(01 e3 38 49 15 d1 cc 4a db 1c f3 0b 57 5c 0c ac 2c) = 0 FNV128_1a(02 2c 4a ce 75 60 97 aa 09 85 82 f0 bd b7 03 ba c6) = 0 FNV128_1a(02 dc 2f 05 bd 56 c4 16 02 3c b0 ae 11 e8 4e 82 13) = 0 FNV128_1a(02 e9 29 25 75 1a 17 f0 a9 5f a6 80 bf 68 28 a0 37) = 0 FNV128_1a(04 a1 60 5f 8b 7e 98 7d 37 e6 29 c2 3e b5 22 4b 45) = 0 FNV128_1a(04 f2 cf 79 1c cd cd 0c 77 db 32 53 e1 cc 8e c1 4c) = 0 FNV128_1a(05 a8 74 57 b8 17 1b 76 55 6c ca fe dc e2 d9 2a d1) = 0 FNV128_1a(08 0e 2b 2f 98 97 e7 cf 0b 5f 25 da c2 5a 57 87 1d) = 0 FNV128_1a(08 b1 69 31 6f a5 60 cd 90 42 fc d0 28 71 35 ff aa) = 0 FNV128_1a(08 e4 58 0d 84 b7 2b 86 15 65 51 4b 3c c9 e4 f3 a2) = 0 FNV128_1a(09 97 a2 d4 74 f0 e6 35 bf 57 08 2c e4 7c 7a 10 7a) = 0 FNV128_1a(09 e9 55 54 1d 31 70 70 60 79 15 fd 44 5a 40 0b 6e) = 0 FNV128_1a(0a 6c 15 9d 53 89 12 59 6a 46 23 f9 d8 30 70 b4 3c) = 0 FNV128_1a(0a 92 ca ef bc 7f df a5 70 77 d6 1f d8 30 d1 d4 f4) = 0 FNV128_1a(0e c8 ca 78 b4 de bd 39 73 3e c3 e5 a4 d2 d3 f0 35) = 0 FNV128_1a(10 3d 76 e4 79 f1 20 01 3e ff f3 6f fb 7e 13 bc 96) = 0 FNV128_1a(10 7e 09 e9 83 7e af ee ea 86 15 54 48 37 3a 34 2b) = 0 FNV128_1a(11 3a f5 97 30 14 56 54 96 e6 1e 21 ed 12 7d e8 13) = 0 FNV128_1a(13 00 50 d9 4c aa f2 3e 18 6c 91 05 e0 1c 1d a8 f4) = 0 FNV128_1a(13 8f 33 f8 0a ce 07 2d d5 13 98 80 da 0d 2b c6 b8) = 0 FNV128_1a(13 ef 6c 8a 16 bd 70 47 16 a1 db c5 0d c3 b3 6c d7) = 0 FNV128_1a(15 0f 03 8e fe bc 47 3d 5c d4 20 0d 9b 97 f5 c5 25) = 0 FNV128_1a(16 1a 23 41 e6 df c2 cf 60 ea 5e 0f 10 45 16 b2 8f) = 0 FNV128_1a(16 56 50 dd 43 f7 70 d1 8a 52 26 73 5b a8 85 fa 5c) = 0 FNV128_1a(16 78 ae 1b 51 56 a3 a5 25 fa 41 19 4f e9 8f d4 d9) = 0 FNV128_1a(18 1c f9 b8 60 72 25 a8 f3 d0 11 11 f5 94 07 9d 9f) = 0 FNV128_1a(1e 8b c9 4f fd 6f 20 ab de e8 7b c7 23 b6 10 db 5f) = 0 FNV128_1a(1e d8 b4 06 f1 ce da b5 1f d8 98 85 83 00 2f bc f7) = 0 FNV128_1a(20 4b 20 f0 9d fd 63 f2 82 02 d7 c7 6a 30 48 64 37) = 0 FNV128_1a(20 d8 84 b9 f0 f2 93 e4 75 07 16 c0 23 bc 86 09 d7) = 0 FNV128_1a(22 85 80 a2 35 fb 4b b0 4d c9 c5 aa 8a 15 b3 de 48) = 0 FNV128_1a(26 a4 98 82 50 4e 87 9d 19 04 37 c3 6d a8 f2 48 b7) = 0 FNV128_1a(27 01 bf d2 ff a2 90 76 34 4f 4f b6 e6 58 67 3b e7) = 0 FNV128_1a(27 13 e0 30 03 80 de ce b0 53 71 f6 0f 52 6a 98 75) = 0 FNV128_1a(27 b8 76 cf c2 ea d3 7d cf 11 ad 40 34 2f 6b 80 ee) = 0 FNV128_1a(29 e5 3d ed 3d d1 71 83 bf 61 2d 3e 1a c1 72 4c 77) = 0 FNV128_1a(29 e8 63 6f 11 5e 8d 3a 7c 63 2d 20 6e 77 2c f7 b4) = 0 FNV128_1a(29 ec f4 60 3b fa 11 7b 39 d6 41 67 5e 88 22 49 25) = 0 FNV128_1a(2a df 8f 1c 04 ae 31 44 3b 41 1e 03 11 46 87 c0 05) = 0 FNV128_1a(2c 1b eb 6f 20 d6 66 7e 52 0e 05 bb 9e 3d ba ed 40) = 0 FNV128_1a(2c 8b 15 d9 4c a1 31 88 64 eb f1 79 b6 db e6 c1 61) = 0 FNV128_1a(2c ab 3e e1 3d d0 c1 38 4e 9b b0 76 de 97 bb 21 7b) = 0 FNV128_1a(2e 97 3a e5 cf b2 a9 e5 81 24 cd 6e c2 fd 2c 1a 19) = 0 FNV128_1a(2e b2 61 39 f0 61 8e 9e 41 95 d0 87 81 d9 8f a5 f5) = 0 FNV128_1a(30 68 1e 6e 72 1b fd 6f eb c8 e4 0e 8c 20 4c c3 92) = 0 FNV128_1a(31 e4 f7 8c 29 cd d5 af 88 cb 7e 12 6a e2 91 f7 48) = 0 FNV128_1a(32 32 66 65 aa 8a c4 bf be 8d 90 0f 70 00 65 9a 3e) = 0 FNV128_1a(32 77 2c e6 84 47 10 12 cf 14 55 d4 43 69 85 06 02) = 0 FNV128_1a(32 bb 69 95 78 f5 9a 8b e5 b4 78 a1 da 18 59 7c 69) = 0 FNV128_1a(32 fb e1 b4 b0 7e 04 35 59 28 c8 75 52 bf fa df 24) = 0 FNV128_1a(35 34 c7 f4 b0 e7 43 e0 85 56 bb b6 ec 54 c6 3e 0f) = 0 FNV128_1a(38 3a 5e fd f1 7d 31 46 b0 35 58 00 d2 bc ed 0f 6e) = 0 FNV128_1a(3c 09 ba c2 86 29 64 c2 a2 81 a9 50 3f d9 2c cd 06) = 0 FNV128_1a(3c c7 87 09 21 cb b7 ac fa 36 6f 29 74 06 ff 6d ad) = 0 FNV128_1a(3e b9 c4 23 ad 23 40 b3 c9 bd 9d 57 a4 87 c2 22 bb) = 0 FNV128_1a(3e d7 95 72 06 ed 39 87 53 09 3d a8 14 1f aa f8 f6) = 0 FNV128_1a(3f 2a 98 22 f3 a8 5a 54 3e 26 49 9e 8c 7a e6 85 e7) = 0 FNV128_1a(3f 41 ac 05 7d 1c 94 ab 64 a9 0d ef eb d2 95 6e df) = 0 FNV128_1a(3f 65 52 cc 55 51 8b 95 17 a3 1c 16 d2 71 e5 bb 60) = 0 FNV128_1a(40 36 15 c5 74 8d e3 b4 88 d3 a4 d9 fa c8 9a bd 0c) = 0 FNV128_1a(42 65 bd a7 dc cf a8 7b f0 46 66 99 d4 40 19 65 f9) = 0 FNV128_1a(42 73 d9 33 78 05 78 90 00 86 2e 9f 36 5e 26 46 40) = 0 FNV128_1a(42 82 2d 16 46 05 24 9b 33 75 b1 f6 f1 f4 53 6a 81) = 0 FNV128_1a(43 39 0f cd 19 b7 37 28 2a b1 78 11 97 56 45 63 61) = 0 FNV128_1a(43 6b 01 59 cc 92 04 df db 5d a2 ad 84 8b ac fe 64) = 0 FNV128_1a(43 c7 70 71 6a 1b 13 e9 6b da 52 3b c9 c9 80 53 aa) = 0 FNV128_1a(45 13 d2 88 9b 5e 1d 7d df 28 cf 4a 10 0a b7 28 97) = 0 FNV128_1a(45 2e 7c e5 b9 7a f1 8b 56 06 7f 85 4c dd 9e 84 f3) = 0 FNV128_1a(45 40 9e 2d dd 23 8a ca 58 91 9c 5b f9 66 26 ae d0) = 0 FNV128_1a(45 78 74 16 92 52 9f 62 c5 d7 e9 fe a2 89 e7 52 ec) = 0 FNV128_1a(49 4a fe ce 6c b6 18 37 94 cb 26 ab dc 33 96 ea 82) = 0 FNV128_1a(4a 41 6b be 51 59 37 30 37 59 33 63 02 83 42 24 b3) = 0 FNV128_1a(4a 7a a6 bf cd ec 72 7a d5 ad 72 f3 a4 55 b7 62 f4) = 0 FNV128_1a(4c 2a 13 f7 b6 d5 55 f4 83 25 ba e1 8b 58 7a 1e 7b) = 0 FNV128_1a(4c b6 5a 39 4c b4 ec d7 b4 75 f5 03 9b 9a 0e 3a 1d) = 0 FNV128_1a(4e 08 d2 98 03 3c 74 38 19 7e 44 93 2c 6e 30 49 a1) = 0 FNV128_1a(4e a3 77 90 25 11 9e 0a a5 c0 28 1a 88 19 dd ff af) = 0 FNV128_1a(4e b9 72 b4 36 70 28 a6 60 ae b5 80 1f 79 3b 44 e2) = 0 FNV128_1a(50 df 0b 29 da e6 88 27 6a e7 95 56 2d 02 3c f2 8c) = 0 FNV128_1a(51 30 68 f5 c2 ee 23 b7 e8 9a f8 d7 3c 49 c3 9c 7e) = 0 FNV128_1a(52 48 82 3a 16 28 39 3a ae aa b6 61 7d 6f 67 76 7a) = 0 FNV128_1a(52 72 53 fc f1 0b 61 5f 9a 51 dd 79 ea 20 2b bc 78) = 0 FNV128_1a(53 4f 6a b2 a4 53 e7 a5 e5 fc d3 45 ba 1e 76 ec 39) = 0 FNV128_1a(53 a0 04 b6 a0 99 9b 85 08 2b 9a df 1c 9f a7 52 51) = 0 FNV128_1a(53 c8 89 85 61 3c 93 09 c6 5b c8 9d 86 d4 fb be 62) = 0 FNV128_1a(53 d9 25 94 0b fc e0 f2 ff 19 03 6d 4f b6 02 2d e1) = 0 FNV128_1a(57 1a 58 58 ad c7 28 62 6b 37 42 da 43 02 00 72 e3) = 0 FNV128_1a(57 d1 74 eb 74 83 a8 95 b2 c4 e2 e2 3e db 8b 1b 3d) = 0 FNV128_1a(59 e6 6f 7f 1d 4a da c5 e4 65 0c 76 35 59 d2 26 f9) = 0 FNV128_1a(5a 97 b2 4c b9 95 b3 b3 80 d4 65 60 88 f5 18 24 4e) = 0 FNV128_1a(5b 60 af a3 c4 0f b9 ba 1f 82 c3 9c 36 06 7e 8b 73) = 0 FNV128_1a(5e 5c c2 05 2d 96 a0 17 bc 9c a7 2d 5b 02 f3 df ab) = 0 FNV128_1a(5f cc 29 87 c0 f2 64 fb a8 bc c2 82 9a 0a 4a 1a 31) = 0 FNV128_1a(61 14 cc a9 ab cb fe dc 17 1b 9c 62 f3 df 5f 09 b9) = 0 FNV128_1a(63 22 09 ae 72 f8 d1 96 69 7c 97 1d 55 b3 53 50 58) = 0 FNV128_1a(63 e5 87 23 b4 59 8d 0e 91 f9 f7 1f 9c 1e 75 c3 5d) = 0 FNV128_1a(65 81 7b fc 04 ad 78 a5 f7 b5 8e 5c 07 25 54 cb 07) = 0 FNV128_1a(65 fc ef b8 fe ca 61 27 ec 61 99 e7 22 82 b9 ce ff) = 0 FNV128_1a(66 40 8d 1b 3a 5c 10 a5 34 db 70 16 5b a9 a4 ed 12) = 0 FNV128_1a(66 56 6a 1e 65 f7 e4 f0 b6 a5 49 f8 1f 7a 16 f4 96) = 0 FNV128_1a(66 75 1d da 8a 84 b0 0a 06 68 a6 62 81 b1 9b bb ad) = 0 FNV128_1a(6b 1c cb f8 de 58 5b 1e e3 8c 69 bb 62 f2 9a e0 bb) = 0 FNV128_1a(6c 45 32 10 4c ec c4 58 37 f3 40 26 cf 89 84 a4 18) = 0 FNV128_1a(6d 8c fc 35 30 73 7a 4c ee eb 4c ef f3 26 a8 d5 90) = 0 FNV128_1a(6e 99 92 83 71 3d 02 0c 35 a6 a5 e3 ad fd dd e4 2f) = 0 FNV128_1a(70 08 e0 42 a6 fd 8a ca 1c 75 bc 22 89 1c c8 28 ba) = 0 FNV128_1a(70 58 1f 77 2d 16 6a 2c 03 e0 35 a0 9c e4 be 4e c0) = 0 FNV128_1a(70 c5 6f 4d 88 b3 e7 69 3a 31 e7 66 26 e2 39 94 9e) = 0 FNV128_1a(71 8d 7d 71 40 77 33 d6 13 cb a3 7c cd ce 27 7b 3d) = 0 FNV128_1a(71 90 57 ff 8d 5c c8 56 5a ed f0 23 6f 74 c6 0c b0) = 0 FNV128_1a(72 cf 4b 1f a1 df 0b 98 e6 75 b2 68 01 f8 0b 1e 68) = 0 FNV128_1a(73 d1 8f 57 34 9d 67 ce 43 df a3 0f d0 27 d9 f6 0b) = 0 FNV128_1a(74 b4 b0 9e 98 32 47 38 f1 0d d0 7e 9a 06 00 45 a9) = 0 FNV128_1a(75 0d 23 a1 ae c5 ff f6 9b 12 55 6c 28 b6 a4 d3 04) = 0 FNV128_1a(75 39 38 3b 2d 7e d6 82 8f 80 d4 02 e6 3f 83 14 fc) = 0 FNV128_1a(75 9c 23 cf 30 cb 64 94 24 71 26 df b7 13 d9 e7 29) = 0 FNV128_1a(76 ae fe d4 a9 5e 2f ea 0c be 3b 7c a0 9f f4 2c 91) = 0 FNV128_1a(77 05 91 19 a1 02 55 63 83 de de 9f 46 3c 73 b5 a4) = 0 FNV128_1a(78 ce ed c4 a0 7c 18 69 f3 44 a7 29 97 c9 1b 1e 7b) = 0 FNV128_1a(7b 0f 0a c3 54 be 41 85 f0 2a fa 51 85 1d cd aa 0e) = 0 FNV128_1a(7c 84 7d 24 6a 5d 8a b9 c0 39 73 50 bb ec 18 98 b3) = 0 FNV128_1a(7c f8 89 ec cc 69 ce a0 0b c2 bd 9c 84 6c da 5d ac) = 0 FNV128_1a(7e 23 8b 75 6e 8d 97 2f e2 1d a4 0d 73 d3 d1 76 e2) = 0 FNV128_1a(7e 7d 4d 45 66 31 aa e5 b8 18 04 7b 46 89 de 84 6c) = 0 FNV128_1a(80 30 4c 4e 06 f9 4e a5 65 e5 96 fa 0b 79 bd b7 c9) = 0 FNV128_1a(80 b6 96 66 3b 8c 91 8c b4 ea 2d bd 92 86 bf 01 fd) = 0 FNV128_1a(81 60 0e 08 29 6c b7 73 fe 64 94 b6 2c dd ab 75 06) = 0 FNV128_1a(81 ca c0 07 ed 34 64 2b 5f 0b 21 50 b1 18 69 75 a3) = 0 FNV128_1a(81 e1 52 8f df 84 49 34 42 63 1e 6f a3 00 0d 39 8f) = 0 FNV128_1a(83 f0 cb 7d 7e e7 8b 44 2e a7 4d 9b 25 99 84 50 1f) = 0 FNV128_1a(84 43 1e 43 4e 85 9f 2e 65 58 ea df f4 b3 4e 8e a4) = 0 FNV128_1a(84 96 10 83 ee 54 8b 67 90 29 97 fb 12 44 29 51 fb) = 0 FNV128_1a(85 0c 54 2c 7e 4c fe 3c d5 03 61 91 89 9a e7 26 d0) = 0 FNV128_1a(85 ee 22 c7 ce b5 fb 6b 5b c1 5f 8b 71 c0 63 fc 1e) = 0 FNV128_1a(88 12 ff eb 70 fa fd fe 4a dd e1 b1 5e 27 41 99 22) = 0 FNV128_1a(88 32 8b 42 ae 78 c3 93 cf 3a 33 55 32 1d 0f f0 2d) = 0 FNV128_1a(89 16 0b 30 79 f2 60 29 14 b9 60 82 b6 21 ba 3b be) = 0 FNV128_1a(89 3e 3a 9a 04 74 43 90 c5 01 3e 35 0f f0 81 46 56) = 0 FNV128_1a(89 93 85 3d 3f 48 c4 ea 08 87 1c db 20 4a 84 45 f7) = 0 FNV128_1a(8c 77 c4 fd ed 14 9c af 48 5d 91 89 27 87 af ba 2d) = 0 FNV128_1a(8e d6 29 65 97 42 c1 e3 d4 f5 5a 08 c8 40 b3 8c 54) = 0 FNV128_1a(90 75 e8 05 80 ce 60 e5 0a 5c 0a e3 16 43 dd 55 c0) = 0 FNV128_1a(90 bb 6c a3 c8 06 5a 22 02 da 6f 27 5c 67 9e 32 9c) = 0 FNV128_1a(92 13 2d 10 54 9e eb 93 1c 57 3a 05 09 5a 5f 98 fb) = 0 FNV128_1a(93 cc a4 58 22 46 7d 9b c2 ab 72 dd 8c 38 dd a3 c8) = 0 FNV128_1a(94 5d cd 43 de 7c bb f1 20 5a ed 38 ce 16 8c 48 77) = 0 FNV128_1a(94 da 3c e9 fd 3c 70 09 6b 89 a8 28 0e ec 03 a6 31) = 0 FNV128_1a(95 69 28 ad f2 8c 33 2f 09 c4 4b 39 eb cb c8 90 3b) = 0 FNV128_1a(96 87 b9 ac fc a2 b4 10 81 f0 29 68 6e 67 76 ea 8a) = 0 FNV128_1a(96 f5 32 67 b6 08 ed ee 7c aa 30 7f 27 78 77 d2 ab) = 0 FNV128_1a(97 6f 7b 76 d3 f2 ff ad c7 6f 85 92 9d 70 71 1f 67) = 0 FNV128_1a(98 57 9c 22 83 5f e1 e1 18 66 d9 a1 3e 14 f0 e7 e9) = 0 FNV128_1a(98 8c 64 ea 32 48 ef 47 c2 6b d9 4c 21 66 b5 65 84) = 0 FNV128_1a(98 d1 21 94 81 7e de fb da 38 69 1d e2 bc f4 05 9a) = 0 FNV128_1a(9a 0a e5 6e 67 2b b9 cb 14 0a 18 c1 c6 1b da e8 88) = 0 FNV128_1a(9e 59 df 17 f9 db 9b e5 8c 9d c6 cd b0 21 0c bc d7) = 0 FNV128_1a(a0 1d d9 d1 fc a8 73 e8 df 85 27 0e fe 58 79 0f 24) = 0 FNV128_1a(a1 44 fa 78 00 12 b6 a7 5a 74 99 42 11 fa 74 80 7d) = 0 FNV128_1a(a2 b2 19 3e f1 b4 5b 25 6a 8e 45 43 3a 4b c4 eb ad) = 0 FNV128_1a(a5 86 d5 39 bc 93 3e 41 45 fb 24 8b 65 b1 c2 5b 40) = 0 FNV128_1a(a7 22 e1 cf e4 c5 ef e8 5e f4 c1 23 cd a3 73 3e 6f) = 0 FNV128_1a(a7 50 47 ab 96 a5 a3 9e 8c 5d bf 1c cc fd 5f 81 6f) = 0 FNV128_1a(a7 fe ad e3 1c c6 6b d3 7f 01 e1 0a 7e e3 d6 9f 77) = 0 FNV128_1a(ab 05 f1 6e af ed 0d e1 f5 2b 22 ac 6a 8b b3 5e b4) = 0 FNV128_1a(ab 4d 86 c2 3b 14 10 27 73 8e 99 37 ef 21 3d d6 dd) = 0 FNV128_1a(ab da 8c 5e 56 a7 97 ea 6a e7 b8 34 84 90 8f b0 88) = 0 FNV128_1a(ab f1 71 6c 94 8a 47 2f 10 9d 76 ad ac 17 93 e1 5b) = 0 FNV128_1a(ac 6b 35 fc 44 b2 1b 17 ef e6 df c8 24 9c a2 ac a5) = 0 FNV128_1a(ad 12 ad 5e 98 06 05 a4 8b 05 48 65 20 d7 71 41 72) = 0 FNV128_1a(ad 3f 4a d1 ad c4 bb 2d c5 6b 9a 2a 15 14 dd ab 94) = 0 FNV128_1a(ad cc 26 4b f6 c6 a5 56 92 83 37 b2 f6 90 c3 d4 b7) = 0 FNV128_1a(ae f7 39 b7 af 00 24 f8 24 1c c6 83 96 27 bd ea da) = 0 FNV128_1a(af e5 30 d1 b3 fc 01 dc f1 11 1b c3 ce a8 e6 0d 7f) = 0 FNV128_1a(b0 02 74 e9 1e 6d 9a c0 b7 88 dd df b9 5a 03 3d ff) = 0 FNV128_1a(b1 cd 33 03 e9 b4 6f 39 14 31 32 a6 00 9e 91 5a 62) = 0 FNV128_1a(b2 fe 42 05 50 71 81 78 e7 be 52 6d d9 03 90 40 7a) = 0 FNV128_1a(b4 c1 7d 2c 0c 1c 7a e7 3e 00 ab a1 b7 e6 31 e8 aa) = 0 FNV128_1a(b5 0c bc 69 82 07 aa bc 71 5e 3f 72 84 3f 57 6e 28) = 0 FNV128_1a(b5 ae ab 60 92 63 6e 2e 5a 93 37 ba cd b6 e5 79 49) = 0 FNV128_1a(b6 49 e3 fe 2b d8 34 20 bb eb 81 31 3c 30 36 f5 9b) = 0 FNV128_1a(b6 c1 75 56 1a 62 40 f1 de 6e 3f 80 e0 76 0d b2 16) = 0 FNV128_1a(b9 0c 13 a5 20 d5 e3 21 86 e9 3e 6e 3b 67 ba 44 c6) = 0 FNV128_1a(bb 30 54 27 00 ef c8 da ad 60 50 40 e1 e9 f3 32 76) = 0 FNV128_1a(bb 64 cc 12 f6 58 16 62 96 d1 69 68 9a 99 b3 ae 2a) = 0 FNV128_1a(bc 09 9b c3 5a 3e 77 30 3c 51 21 79 ab 37 b4 0f 5d) = 0 FNV128_1a(be ca 02 d9 bf ac d5 6a 7d d0 01 b8 04 84 12 6b 1b) = 0 FNV128_1a(be f4 3a 82 18 2b 1a 14 6c 60 42 0d 0f eb db c9 e3) = 0 FNV128_1a(c0 21 12 d2 91 14 a0 af 78 ed 4c 10 fe 58 b9 12 8c) = 0 FNV128_1a(c1 97 56 11 5d 3d d6 32 27 81 6e c3 5d 10 72 1f e3) = 0 FNV128_1a(c1 aa e4 ba 37 20 e3 6c e5 ca 52 64 cf 86 a3 16 19) = 0 FNV128_1a(c3 53 0f eb 3f 83 01 32 7f a6 bb 01 3d 58 a2 a7 a3) = 0 FNV128_1a(c5 42 3a 66 78 5e 21 49 92 fc ea 01 0b c8 5d 70 e7) = 0 FNV128_1a(c5 80 6c 07 9e fc 2c 9e 0d bf b6 b2 9d 57 95 78 60) = 0 FNV128_1a(c6 51 60 a7 58 5e 41 52 1b 66 0b 50 c5 58 82 d5 9e) = 0 FNV128_1a(c6 cf 08 be d9 d6 a8 ed c9 9c 29 c5 45 b2 a4 06 9e) = 0 FNV128_1a(c8 62 33 e6 dd ad 8c 09 e2 7c 9e e4 22 5a b7 39 93) = 0 FNV128_1a(c8 6d fb a7 df 78 2b 75 44 dc 27 18 37 f7 86 dc b0) = 0 FNV128_1a(c8 f5 7f 5e d5 b9 17 39 f9 4d 5a bb d5 f0 a7 84 4e) = 0 FNV128_1a(ce e8 04 a1 85 11 20 7d d3 bc 9f d5 de d7 fc 61 3e) = 0 FNV128_1a(cf 1d dc b1 ac 32 97 0e d0 24 a4 c7 de 29 e0 c9 da) = 0 FNV128_1a(d2 8b e2 f6 2c 71 6f de 7f 3a 99 75 bf 46 65 70 27) = 0 FNV128_1a(d3 d0 0c e1 0e 49 c6 1e 6b 3b c4 25 ea a5 5b 5a b9) = 0 FNV128_1a(d3 f4 13 f7 78 4b 13 76 46 ce e0 f9 7b bb 06 c0 27) = 0 FNV128_1a(d4 0f f7 75 7b a9 ee c9 9b c4 6b 5e 4b c1 3f 92 1e) = 0 FNV128_1a(d4 71 ee f5 c9 20 49 7c 3b ba aa e4 9c 62 ec b5 d5) = 0 FNV128_1a(d8 2b 3d ac 05 08 94 27 58 fc 01 26 9e 80 53 ed a4) = 0 FNV128_1a(d8 f2 ac e2 2e a1 3b 99 44 03 09 45 fa 72 b1 3a 68) = 0 FNV128_1a(d9 81 0d c8 26 22 65 c2 45 06 da 1f af d0 0a 61 23) = 0 FNV128_1a(d9 f8 f1 94 9d 82 91 56 94 b2 e3 7d 56 3e 5c b2 01) = 0 FNV128_1a(da 5c 9d 1f b0 39 21 dd 91 0b 69 a5 d4 73 08 12 33) = 0 FNV128_1a(db 1b ce 9f 3c 8e e7 2b b7 24 9e 0a 2c 5a 5a 5a 29) = 0 FNV128_1a(db c9 dc 7c 0e f2 74 99 16 a8 e8 61 45 5a 85 ff 38) = 0 FNV128_1a(de 14 d6 e4 9a e9 4f 26 4b b1 ed b3 17 a4 9e 5d f7) = 0 FNV128_1a(df 68 7f 31 75 5b 4c 0a 92 8f 03 d9 d7 5e 96 5a 7e) = 0 FNV128_1a(e0 a4 77 0a 19 12 fc 71 26 51 6f 27 b5 5a 0e 85 85) = 0 FNV128_1a(e0 eb 84 ca 27 40 ab 55 2e eb d0 38 48 3c c4 1d f9) = 0 FNV128_1a(e1 4c 48 25 05 6b 08 28 fc 00 a7 51 88 5a d7 c7 33) = 0 FNV128_1a(e1 c4 56 ec 5c 3b 0d 00 8d 3f 86 41 0d 47 15 fe a4) = 0 FNV128_1a(e3 16 48 ee b3 b3 a4 3b c5 cf 40 e9 a1 f2 36 3a 71) = 0 FNV128_1a(e3 57 1f 0d 61 13 aa 13 ed 33 e6 55 e1 d9 f5 99 d9) = 0 FNV128_1a(e5 03 f0 d2 36 12 fd b7 d1 e1 48 7d f7 86 db bd 4b) = 0 FNV128_1a(e5 dd 39 e3 ba 18 af 41 00 6e 61 40 cd 13 53 ed b6) = 0 FNV128_1a(e9 83 94 a6 c2 3c ce a1 3e 6f ea b3 15 a5 e0 ae 94) = 0 FNV128_1a(ea ed c5 9d b9 fa bf b3 41 98 62 20 b1 b3 83 21 44) = 0 FNV128_1a(eb 5d cb e3 fb e4 32 fb eb df bb f7 de e9 7f 37 94) = 0 FNV128_1a(eb dd ce c1 a9 25 4b 1d b6 2f 00 c0 28 99 c4 63 a7) = 0 FNV128_1a(ed 7c fc a4 67 85 bd a5 bc b1 be 70 bd 34 99 2e 21) = 0 FNV128_1a(ed f9 c6 0d 0d 42 76 d4 ae 62 03 16 e8 c2 ac 43 95) = 0 FNV128_1a(ee 6d 46 b4 ad c4 9e 72 94 f8 3d bc bc 47 7e 3f e0) = 0 FNV128_1a(ee d1 35 ef ed cd f7 5a 08 14 9a dc af e2 b5 82 17) = 0 FNV128_1a(f0 6a b2 ab 77 32 79 f8 f6 98 54 b7 a9 95 ee c2 85) = 0 FNV128_1a(f0 9d bc 9e 3f d7 72 ba 7b e2 7c d6 c7 fd d3 54 fa) = 0 FNV128_1a(f1 1f da f1 b6 66 43 0b e3 cc cc 82 9c 78 83 36 0e) = 0 FNV128_1a(f4 72 59 b2 41 fb eb a3 a2 39 ed 6e ee cf e1 ac 86) = 0 FNV128_1a(f4 7c ee 2c a1 c3 cd 6b 87 90 06 b6 0a e8 74 78 3e) = 0 FNV128_1a(f4 86 f9 07 1b 37 f6 39 3d 45 d0 e1 a8 35 23 93 0c) = 0 FNV128_1a(f4 94 09 3d 8d 0f 17 ad eb 10 ea c4 38 20 45 96 f1) = 0 FNV128_1a(f4 d8 21 db 33 3f d2 ef 17 55 24 6a 76 fc b2 aa 30) = 0 FNV128_1a(f5 a1 1b 1e 50 9a 52 b8 e3 25 dc 59 4f 5a b8 f5 03) = 0 FNV128_1a(f5 d4 6d 70 d1 e9 8f a9 d8 fc 77 24 45 f7 ac 59 7f) = 0 FNV128_1a(f6 14 60 56 5c 64 23 70 77 b9 08 ed 10 8c f1 1c 28) = 0 FNV128_1a(f8 c2 ec c3 a7 c5 a9 e9 f9 d3 c8 92 ce 99 37 a1 9f) = 0 FNV128_1a(f9 90 91 25 6c d5 c6 d9 53 90 ba ea cf b8 46 25 b5) = 0 FNV128_1a(f9 de 7d 4a 23 ad 08 53 25 37 a8 17 ca d6 d3 55 29) = 0 FNV128_1a(fa 01 20 30 dd b3 7e 0a 3d 99 3f 65 e1 19 1e 5a 3c) = 0 FNV128_1a(fc 85 2e 19 58 54 2a e4 37 4d bf 4d 9a df ae e4 1c) = 0 FNV128_1a(fe 54 fd f5 5a 75 92 44 61 69 58 e8 f7 a0 8d 2b 4f) = 0 FNV128_1a(fe 66 9b ff 64 40 27 dc d1 03 3f e5 0d 72 37 e8 78) = 0 FNV128_1a(ff 08 ff 30 74 04 10 ae 3c 0e 73 c6 e3 6a 4a 9a 69) = 0Brute force is infeasible (256^17 = 2^136), so the search uses lattice reduction:
- An octet only changes the lowest 8 bits of the state. With u_i = (h_(i-1) XOR c_i) mod 256 and r_i = h_i mod 256 = (59 * u_i) mod 256 (59 = FNV prime mod 256), the recurrence can be written exactly as G_i = (G_(i-1) + u_i) * P - r_i (mod 2^128), with G_i = h_i - r_i. The hash is 0 iff G_(n-1) = 0 and the last octet equals r_(n-1).
- For a fixed prefix of a few octets, the remaining positions give a modular knapsack with small unknowns 0 <= u_t, r_t <= 255. This is a closest-vector problem in a fixed lattice (dimension 26 for lengths 16 and 17, with prefixes of 2 and 3 octets); only the target depends on the prefix.
- The lattice is reduced once with exact integer LLL and BKZ. Then, for every prefix, Schnorr-Euchner enumeration lists all lattice points in a ball around the centre of the cube [0,255]^(2M) that contains the whole cube. Every such point is a data set (c = s XOR u); it is accepted only if the full 128-bit FNV-1a hash, recomputed with Jacksum, is 0.
The meet-in-the-middle part takes about 30 seconds, the lattice search of lengths 7 to 15 less than a second, and length 17 took 11 minutes on 14 cores.
256-bit solution by Johann N. Löfflmann on 2026-Nov-10:
These are 1 solution of length 32: FNV256_1a(3f 1e 0d e2 06 61 5b ba ca b3 c8 5b 86 61 4a e3 c8 7c 12 15 79 5c 2f bf e1 b2 ba 9f f7 88 59 31) = 0
According to Johann N. Löfflmann:
Each solution was verified independently with the FNV-1-256 implementation of Jacksum:
prints:jacksum -a fnv-1a_256 -X -q hex:<hex>
0000000000000000000000000000000000000000000000000000000000000000Then using a short arbitrary-precision Python implementation with:
offset basis 100029257958052580907070968620625704837092796014241193945225284501741471925557, prime 2^168 + 2^8 + 0x63
Johann N. Löfflmann writes:
Is 32 the shortest length? Maybe.A counting argument gives 256^n / 2^256 = 2^(8n - 256) expected solutions of length n: 1 for n = 32, 1/256 for n = 31, and less than 0.004 for all lengths up to 31 together. Under the usual assumption that FNV-1a-256 behaves like a random function, the probability that a shorter solution exists is therefore below 0.4 %, even without any search. For length 31 I additionally ran a deterministic search without pruning: for each of the 256 prefixes, all lattice points in the ball of squared radius 1.5 times the mean squared distance of the points of the cube [0,255]^58 from its centre were listed (45 minutes on 14 cores). None of them is a solution. So there is no solution of length 31 inside this ball; this part is a proof, not an estimate. The ball contains more than 99.996% of the points of the cube (computed exactly by convolving the distribution of the squared distance per coordinate). If the solutions are spread evenly over the cube, a solution of length 31 outside the ball exists with probability below 3.3e-5 * 1/256 = 1.3e-7. The same search for the lengths 30, 29 and 28 (lattice dimensions 56, 54 and 52, 15 seconds together) found nothing either; these balls contain more than 99.99% of their cubes, so the remaining probability is below 1e-9. Lengths up to 27 contribute less than 2^-40 by the counting argument. Altogether, a solution shorter than 32 exists with probability below 1.4e-7.
A fully exhaustive search would need a ball that contains the whole cube (squared radius 3 times the mean); its volume is 2^57 times that of the cube, which is out of reach.
Two independent searches of length 32 with different lattices (prefixes of 1 and of 2 octets, 10 and 20 randomized rounds) both found exactly this one solution and no other, so it is probably the only solution of length 32.
Brute force is infeasible (256^32 = 2^256), so the search uses lattice reduction:
- An octet only changes the lowest 8 bits of the state. With u_i = (h_(i-1) XOR c_i) mod 256 and r_i = h_i mod 256 = (99 * u_i) mod 256 (99 = FNV prime mod 256), the recurrence can be written exactly as G_i = (G_(i-1) + u_i) * P - r_i (mod 2^256), with G_i = h_i - r_i. The hash is 0 iff G_(n-1) = 0 and the last octet equals r_(n-1).
- For a fixed prefix of 1 or 2 octets, the remaining 30 or 29 positions give a modular knapsack with small unknowns 0 <= u_t, r_t <= 255. This is a closest-vector problem in a fixed lattice of dimension 60 or 58; only the target depends on the prefix.
- The lattice is reduced once with exact integer LLL and BKZ-20. Then, for every prefix, Schnorr-Euchner enumeration with pruning ("extreme pruning": several rounds with randomly weighted metrics and re-randomized bases) lists the lattice points near the center of the cube [0,255]^(2M). Every such point is a binary data set (c = s XOR u); it is accepted only if the full 256-bit FNV-1a hash, recomputed with Jacksum, is 0.
- As a check, the same program, run exhaustively without pruning, reproduces exactly the published results of the binary challenges 1, 2, 7 and 8 (32 and 64 bits, FNV-1 and FNV-1a): the 254 solutions of length 5, the 238 solutions of length 9, the 2 solutions of length 4 and the single solution of length 8, and no solution of the next shorter length for challenges 1, 2 and 8. A separate meet-in-the-middle program confirms the 2 solutions of length 4 and none shorter for challenge 7, and no solution shorter than 5 for challenge 1.
The search of length 32 takes less than a minute on 14 cores.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
General FNV solution by Russ Cox <> on 2011-Mar-02:
There is no such stream of NUL octets. Xor with an odd byte flips the parity of the hash. Xor with an even byte leaves it alone, as does multiplying by any of the (odd) FNV primes. Thus the final hash has the same parity as the initial offset if and only if there are an even number of odd bytes in the input. This is the reason that all the offset bases have the same parity (odd, it turns out), and it implies that any consecutive stream of NULs will have an odd (non-zero) hash.
32-bit solution by Russ Cox <> on 2011-Mar-02:
428876705 0xff octets.Peter de Rivaz <
> independently confirmed this result.
Richard Heylen <
> independently confirmed this result.
64-bit solution by Peter de Rivaz <> on 2011-Dec-13:
Richard Heylen <9896220416391497057 0xff octets.> independently confirmed this result.
128-bit solution by Johann N. Löfflmann on 2026-Nov-10:51139138437908895582755236659575676289 0xff octets.Johann N. Löfflmann writes:
It it is the only length below 2^128 with hash 0; every other solution is longer by a multiple of 2^128. Like every solution it is odd, as noted by Russ Cox <>.
Proof:
Let P be the 128-bit FNV prime, B the 128-bit offset basis, c = 0xff, M(h) = h * P and X(h) = h XOR c (all mod 2^128). FNV-1 of k octets c is g^k(B) with g = X o M. Since g^k = X o (M o X)^(k-1) o M, the hash is 0 iff f^(k-1)(B * P) = c with the FNV-1a step f(h) = (h XOR c) * P. So we need the smallest k' = k - 1 >= 0 with f^k'(x0) = c, x0 = B * P.
- f is a bijection of Z/2^128 (XOR is a bijection, P is odd). So the orbit of x0 is a single cycle, and the k' with f^k'(x0) = c form one residue class modulo its length. The smallest k' is unique and smaller than the cycle length.
- f is compatible with the reduction modulo 2^j for every j. The low 8 bits of the state run through a cycle of length L = 256 here, so k' is determined modulo 256 by the position r of c mod 256 on that cycle.
- XOR c only changes the low 8 bits, so h XOR c = h + d(s) with d(s) = (s XOR c) - s, which only depends on s = h mod 256. Hence 256 steps from y = f^r(x0) on are an affine map G(h) = A*h + C mod 2^128 with A = P^256. Powers G^q are computed by repeated squaring.
- We need the smallest q with G^q(y) = c; then k' = r + 256*q. The affine maps of Z/2^j form a group of order 2^(2j-1), so every orbit of G modulo 2^j has a power-of-2 length 2^e_j, and e_(j+1) is e_j or e_j + 1. So q is lifted bit by bit: from the unique q_j modulo 2^e_j with G^q_j(y) = c (mod 2^j), the candidates modulo 2^e_(j+1) are q_j and q_j + 2^e_j, and exactly one of them works modulo 2^(j+1) when a solution exists. Here the orbit length of y under G modulo 2^128 is 2^120, so the cycle has length 256 * 2^120 = 2^128 (it contains all states). The lifting yields k = k' + 1 = 51139138437908895582755236659575676289.
Nothing in this computation is sampled or searched heuristically, so the result is exact. It takes well under a second in Python.
Verification:
- A second, separate program computes the hash of k octets 0xff directly: it runs the FNV-1 steps explicitly up to a multiple of 256, determines the affine map of a block of 256 steps from explicit steps (and checks it on random states), and powers it. For the length above it gives 00000000000000000000000000000000; for the published length it gives fad1a1c21a8fd1cbb70aef0a845062c0. For k = 1, 255, 1000 and 4097 its results agree with the FNV-1-128 implementation of Jacksum (jacksum -a fnv-1_128 -x -q hex:ffff...).
- The low bits were also checked by plain iteration of the FNV-1 definition modulo 2^j for j = 8..22 (the cycle modulo 2^j has length 2^j): the length above gives 0 modulo 2^j for every such j, the published length already fails for j = 8.
- The same method reproduces the other published results of the 0xff challenges: FNV-1 for 32, 64, 256, 512 and 1024 bits (428876705, 9896220416391497057, and the results by Richard Heylen) and FNV-1a for 32, 64, 128, 256, 512 and 1024 bits (3039744951 and the results by Peter de Rivaz). Challenge 27 is the only one where it differs.
256-bit solution by Richard Heylen <> on 2011-Dec-14:
Peter de Rivaz <971310111339922874984865931636119693708047768520568964839262806324177446
08641 0xff octets.> independently confirmed this result.
512-bit solution by Richard Heylen <> on 2011-Dec-14:
Peter de Rivaz <612806956068056576215461080927099484400241024395026354420378459322301684
399722907408508285157251830003265846176457230616192353760639874361657361
1559921729 0xff octets.> independently confirmed this result.
Richard Heylen <> on 2011-Dec-14 found a 1024-bit solution:
416676424643376760772449487657397580462250574503060952762179226758571093
761689059455392577969506880247688215845019822014535567311051405867916840
497646798425786609620276239990874926250263846724497488057368971095038212
934393820920453733216924021449681744199270750560657371464991242494173425
0024772314731200245 0xff octets.Peter de Rivaz <
> independently confirmed this solution.
The length found by Richard Heylen <
> is the shortest one. In fact it is the only length below 2^1023 for which the 1024-bit FNV-1 hash of that many 0xff octets is 0; every other solution is longer by a multiple of 2^1023.
1024-bit solution by Johann N. Löfflmann on 2026-Nov-10:
416676424643376760772449487657397580462250574503060952762179226758571093
761689059455392577969506880247688215845019822014535567311051405867916840
497646798425786609620276239990874926250263846724497488057368971095038212
934393820920453733216924021449681744199270750560657371464991242494173425
0024772314731200245 0xff octets.Johann N. Löfflmann writes:
It it is the only length below 2^128 with hash 0; every other solution is longer by a multiple of 2^128. Like every solution it is odd, as noted by Russ Cox <
>.
Proof:
Let P be the 1024-bit FNV prime, B the 1024-bit offset basis, c = 0xff, M(h) = h * P and X(h) = h XOR c (all mod 2^1024). FNV-1 of k octets c is g^k(B) with g = X o M. Since g^k = X o (M o X)^(k-1) o M, the hash is 0 iff f^(k-1)(B * P) = c with the FNV-1a step f(h) = (h XOR c) * P. So we need the smallest k' = k - 1 >= 0 with f^k'(x0) = t, x0 = B * P, t = c.
- f is a bijection of Z/2^1024 (XOR is a bijection, P is odd). So the orbit of x0 is a single cycle, and the k' with f^k'(x0) = c form one residue class modulo its length. The smallest k' is unique and smaller than the cycle length.
- f is compatible with the reduction modulo 2^j for every j: the low j bits of f(h) only depend on the low j bits of h. In particular the low 8 bits s of the state run through a cycle of a permutation of Z/256. For x0 this cycle has length L = 128, so k' is determined modulo 128 by the position r of c mod 256 on that cycle.
- XOR 0xff only changes the low 8 bits, so h XOR 0xff = h + d(s) with d(s) = (s XOR 0xff) - s, which only depends on s = h mod 256. Hence L = 128 steps from y = f^r(x0) on are an affine map G(h) = A*h + C mod 2^1024 with A = P^128 and a constant C. Powers G^q are computed by repeated squaring of affine maps, so f^n for huge n costs only a few thousand multiplications.
- We need the smallest q with G^q(y) = c; then k' = r + 128*q. The affine maps of Z/2^j form a group of order 2^(2j-1), so every orbit of G modulo 2^j has a length 2^e_j that is a power of 2, and e_(j+1) is e_j or e_j + 1. Therefore q can be lifted bit by bit: from the unique q_j modulo 2^e_j with G^q_j(y) = c (mod 2^j), the candidates modulo 2^e_(j+1) are q_j and q_j + 2^e_j, and exactly one of them works modulo 2^(j+1) when a solution exists. Here the orbit length of y under G modulo 2^1024 is 2^1016, so the cycle of x0 under f has length 128 * 2^1016 = 2^1023 (half of all states), and the lifting yields:
k = k' + 1 =
416676424643376760772449487657397580462250574503060952762179226758571093
761689059455392577969506880247688215845019822014535567311051405867916840
497646798425786609620276239990874926250263846724497488057368971095038212
934393820920453733216924021449681744199270750560657371464991242494173425which is the length found by Richard Heylen <
>.
Verification:
- A second, separate program computes the hash of k octets 0xff directly: it runs the FNV-1 steps explicitly up to a multiple of 256, determines the affine map of a block of 256 steps from explicit steps (and checks it on random states), and powers it. For the length above it gives 0. For k = 1, 255, 1000 and 4097 its results agree with the FNV-1-1024 implementation of Jacksum (jacksum -a fnv-1_1024 -x -q hex:ffff...).
- The same method reproduces the solved 0xff challenges on your page: FNV-1 for 32, 64, 256 and 512 bits (428876705, 9896220416391497057 and the results by Richard Heylen) and FNV-1a for 32 bits (3039744951).
32-bit solution by Russ Cox <> on 2011-Mar-02:
3039744951 0xff octets.Peter de Rivaz <
> independently confirmed this result.
Richard Heylen <
> independently confirmed this result.
Peter de Rivaz <> on 2011-Dec-13 found a 64-bit solution:
5125902172520635575 0xff octets.Richard Heylen <
> independently confirmed this partial solution.
64-bit solution by Johann N. Löfflmann on 2026-Nov-10:
5125902172520635575 0xff octets.Johann N. Löfflmann writes:
The length found by Peter de Rivaz <> is the shortest one. In fact it is the only length below 2^64 for which the 64-bit FNV-1a hash of that many 0xff octets is 0; every other solution is longer by a multiple of 2^64.
As noted by Russ Cox <
>, the length is odd.
Proof:
Let P be the 64-bit FNV prime, B the 64-bit offset basis and f(h) = (h XOR 0xff) * P mod 2^64. The FNV-1a hash of k octets 0xff is f^k(B), so we need the smallest k >= 1 with f^k(B) = 0. Write x0 = B and t = 0.
- f is a bijection of Z/2^64 (XOR is a bijection, P is odd). So the orbit of x0 is a single cycle, and the k with f^k(x0) = 0 form one residue class modulo its length. The smallest k is unique and smaller than the cycle length.
- f is compatible with the reduction modulo 2^j for every j: the low j bits of f(h) only depend on the low j bits of h. In particular the low 8 bits s of the state run through a cycle of a permutation of Z/256. For x0 this cycle has length L = 256, so k is determined modulo 256 by the position r of 0 mod 256 on that cycle.
- XOR 0xff only changes the low 8 bits, so h XOR 0xff = h + d(s) with d(s) = (s XOR 0xff) - s, which only depends on s = h mod 256. Hence L = 256 steps from y = f^r(x0) on are an affine map G(h) = A*h + C mod 2^64 with A = P^256 and a constant C. Powers G^q are computed by repeated squaring of affine maps, so f^n for huge n costs only a few thousand multiplications.
- We need the smallest q with G^q(y) = 0; then k = r + 256*q. The affine maps of Z/2^j form a group of order 2^(2j-1), so every orbit of G modulo 2^j has a length 2^e_j that is a power of 2, and e_(j+1) is e_j or e_j + 1. Therefore q can be lifted bit by bit: from the unique q_j modulo 2^e_j with G^q_j(y) = 0 (mod 2^j), the candidates modulo 2^e_(j+1) are q_j and q_j + 2^e_j, and exactly one of them works modulo 2^(j+1) when a solution exists. Here the orbit length of y under G modulo 2^64 is 2^56, so the cycle of x0 under f has length 256 * 2^56 = 2^64 (it contains all states), and the lifting yields:
k = 5125902172520635575 0xff octets, which is the length found by Peter de Rivaz <
>.
Nothing in this computation is sampled or searched heuristically, so the result is exact. It takes at most 2 seconds in Python.
Verification:
Peter de Rivaz <> on 2012-Mar-22 found a 128-bit solution:
195988526173479582814801599910495893127 0xff octets.Richard Heylen <
> independently confirmed this solution.
128-bit solution by Johann N. Löfflmann on 2026-Nov-10:
195988526173479582814801599910495893127 0xff octets.Johann N. Löfflmann writes:
The length found by Peter de Rivaz <> is the shortest one. In fact it is the only length below 2^128 for which the 128-bit FNV-1a hash of that many 0xff octets is 0; every other solution is longer by a multiple of 2^128.
As noted by Russ Cox <
>, the length is odd.
Proof:
Let P be the 128-bit FNV prime, B the 128-bit offset basis and f(h) = (h XOR 0xff) * P mod 2^128. The FNV-1a hash of k octets 0xff is f^k(B), so we need the smallest k >= 1 with f^k(B) = 0. Write x0 = B and t = 0.
- f is a bijection of Z/2^128 (XOR is a bijection, P is odd). So the orbit of x0 is a single cycle, and the k with f^k(x0) = 0 form one residue class modulo its length. The smallest k is unique and smaller than the cycle length.
- f is compatible with the reduction modulo 2^j for every j: the low j bits of f(h) only depend on the low j bits of h. In particular the low 8 bits s of the state run through a cycle of a permutation of Z/256. For x0 this cycle has length L = 256, so k is determined modulo 256 by the position r of 0 mod 256 on that cycle.
- XOR 0xff only changes the low 8 bits, so h XOR 0xff = h + d(s) with d(s) = (s XOR 0xff) - s, which only depends on s = h mod 256. Hence L = 256 steps from y = f^r(x0) on are an affine map G(h) = A*h + C mod 2^128 with A = P^256 and a constant C. Powers G^q are computed by repeated squaring of affine maps, so f^n for huge n costs only a few thousand multiplications.
- We need the smallest q with G^q(y) = 0; then k = r + 256*q. The affine maps of Z/2^j form a group of order 2^(2j-1), so every orbit of G modulo 2^j has a length 2^e_j that is a power of 2, and e_(j+1) is e_j or e_j + 1. Therefore q can be lifted bit by bit: from the unique q_j modulo 2^e_j with G^q_j(y) = 0 (mod 2^j), the candidates modulo 2^e_(j+1) are q_j and q_j + 2^e_j, and exactly one of them works modulo 2^(j+1) when a solution exists. Here the orbit length of y under G modulo 2^128 is 2^120, so the cycle of x0 under f has length 256 * 2^120 = 2^128 (it contains all states), and the lifting yields:
k = 195988526173479582814801599910495893127, which is the length found by Peter de Rivaz <
>.
Nothing in this computation is sampled or searched heuristically, so the result is exact. It takes at most 2 seconds in Python.
Verification:
- A second, separate program computes the hash of k octets 0xff directly: it runs the FNV-1a steps explicitly up to a multiple of 256, determines the affine map of a block of 256 steps from explicit steps (and checks it on random states), and powers it. For the length above it gives 0. For k = 1, 255, 1000 and 4097 its results agree with the FNV-1a-128 implementation of Jacksum (jacksum -a fnv-1a_128 -x -q hex:ffff...).
- The same method reproduces the solved 0xff challenges on your page: FNV-1 for 32, 64, 256 and 512 bits (428876705, 9896220416391497057 and the results by Richard Heylen) and FNV-1a for 32 bits (3039744951).
Peter de Rivaz <> which is the length found by Peter de Rivaz <
> independently confirmed this solution.
256-bit solution by Johann N. Löfflmann on 2026-Nov-10:
12136526130860792277829844191736234974568157406942901196428697312695752207543 0xff octets.Johann N. Löfflmann writes:
The length found by Peter de Rivaz <> is the shortest one. In fact it is the only length below 2^256 for which the 256-bit FNV-1a hash of that many 0xff octets is 0; every other solution is longer by a multiple of 2^256.
As noted by Russ Cox <
>, the length is odd.
Proof:
Let P be the 256-bit FNV prime, B the 256-bit offset basis and f(h) = (h XOR 0xff) * P mod 2^256. The FNV-1a hash of k octets 0xff is f^k(B), so we need the smallest k >= 1 with f^k(B) = 0. Write x0 = B and t = 0.
- f is a bijection of Z/2^256 (XOR is a bijection, P is odd). So the orbit of x0 is a single cycle, and the k with f^k(x0) = 0 form one residue class modulo its length. The smallest k is unique and smaller than the cycle length.
- f is compatible with the reduction modulo 2^j for every j: the low j bits of f(h) only depend on the low j bits of h. In particular the low 8 bits s of the state run through a cycle of a permutation of Z/256. For x0 this cycle has length L = 256, so k is determined modulo 256 by the position r of 0 mod 256 on that cycle.
- XOR 0xff only changes the low 8 bits, so h XOR 0xff = h + d(s) with d(s) = (s XOR 0xff) - s, which only depends on s = h mod 256. Hence L = 256 steps from y = f^r(x0) on are an affine map G(h) = A*h + C mod 2^256 with A = P^256 and a constant C. Powers G^q are computed by repeated squaring of affine maps, so f^n for huge n costs only a few thousand multiplications.
- We need the smallest q with G^q(y) = 0; then k = r + 256*q. The affine maps of Z/2^j form a group of order 2^(2j-1), so every orbit of G modulo 2^j has a length 2^e_j that is a power of 2, and e_(j+1) is e_j or e_j + 1. Therefore q can be lifted bit by bit: from the unique q_j modulo 2^e_j with G^q_j(y) = 0 (mod 2^j), the candidates modulo 2^e_(j+1) are q_j and q_j + 2^e_j, and exactly one of them works modulo 2^(j+1) when a solution exists. Here the orbit length of y under G modulo 2^256 is 2^248, so the cycle of x0 under f has length 256 * 2^248 = 2^256 (it contains all states), and the lifting yields
k = 12136526130860792277829844191736234974568157406942901196428697312695752207543, which is the length found by Peter de Rivaz <
>.
Nothing in this computation is sampled or searched heuristically, so the result is exact. It takes at most 2 seconds in Python.
Verification:
- A second, separate program computes the hash of k octets 0xff directly: it runs the FNV-1a steps explicitly up to a multiple of 256, determines the affine map of a block of 256 steps from explicit steps (and checks it on random states), and powers it. For the length above it gives 0. For k = 1, 255, 1000 and 4097 its results agree with the FNV-1a-256 implementation of Jacksum (jacksum -a fnv-1a_256 -x -q hex:ffff...).
- The same method reproduces the solved 0xff challenges on your page: FNV-1 for 32, 64, 256 and 512 bits (428876705, 9896220416391497057 and the results by Richard Heylen) and FNV-1a for 32 bits (3039744951).
Peter de Rivaz <> on 2012-Mar-22 found a 512-bit solution:
445359075217293949446034810045247904893303946817563293272717969680141569
1296990024719495460337025148681118235657374213045756833266718213854105365691076111 0xff octets.Richard Heylen <
> independently confirmed this solution.
512-bit solution by Johann N. Löfflmann on 2026-Nov-10:
445359075217293949446034810045247904893303946817563293272717969680141569
1296990024719495460337025148681118235657374213045756833266718213854105365691076111 0xff octets.Johann N. Löfflmann writes:
The length found by Peter de Rivaz <> is the shortest one. In fact it is the only length below 2^512 for which the 512-bit FNV-1a hash of that many 0xff octets is 0; every other solution is longer by a multiple of 2^512.
As noted by Russ Cox <
>, the length is odd.
Proof:
Let P be the 512-bit FNV prime, B the 512-bit offset basis and f(h) = (h XOR 0xff) * P mod 2^512. The FNV-1a hash of k octets 0xff is f^k(B), so we need the smallest k >= 1 with f^k(B) = 0. Write x0 = B and t = 0.
- f is a bijection of Z/2^512 (XOR is a bijection, P is odd). So the orbit of x0 is a single cycle, and the k with f^k(x0) = 0 form one residue class modulo its length. The smallest k is unique and smaller than the cycle length.
- f is compatible with the reduction modulo 2^j for every j: the low j bits of f(h) only depend on the low j bits of h. In particular the low 8 bits s of the state run through a cycle of a permutation of Z/256. For x0 this cycle has length L = 256, so k is determined modulo 256 by the position r of 0 mod 256 on that cycle.
- XOR 0xff only changes the low 8 bits, so h XOR 0xff = h + d(s) with d(s) = (s XOR 0xff) - s, which only depends on s = h mod 256. Hence L = 256 steps from y = f^r(x0) on are an affine map G(h) = A*h + C mod 2^512 with A = P^256 and a constant C. Powers G^q are computed by repeated squaring of affine maps, so f^n for huge n costs only a few thousand multiplications.
- We need the smallest q with G^q(y) = 0; then k = r + 256*q. The affine maps of Z/2^j form a group of order 2^(2j-1), so every orbit of G modulo 2^j has a length 2^e_j that is a power of 2, and e_(j+1) is e_j or e_j + 1. Therefore q can be lifted bit by bit: from the unique q_j modulo 2^e_j with G^q_j(y) = 0 (mod 2^j), the candidates modulo 2^e_(j+1) are q_j and q_j + 2^e_j, and exactly one of them works modulo 2^(j+1) when a solution exists. Here the orbit length of y under G modulo 2^512 is 2^504, so the cycle of x0 under f has length 256 * 2^504 = 2^512 (it contains all states), and the lifting yields:
k = 445359075217293949446034810045247904893303946817563293272717969680141569
1296990024719495460337025148681118235657374213045756833266718213854105365691076111, which is the length found by Peter de Rivaz <>.
Nothing in this computation is sampled or searched heuristically, so the result is exact. It takes at most 2 seconds in Python.
Verification:
- A second, separate program computes the hash of k octets 0xff directly: it runs the FNV-1a steps explicitly up to a multiple of 256, determines the affine map of a block of 256 steps from explicit steps (and checks it on random states), and powers it. For the length above it gives 0. For k = 1, 255, 1000 and 4097 its results agree with the FNV-1a-512 implementation of Jacksum (jacksum -a fnv-1a_512 -x -q hex:ffff...).
- The same method reproduces the solved 0xff challenges on your page: FNV-1 for 32, 64, 256 and 512 bits (428876705, 9896220416391497057 and the results by Richard Heylen) and FNV-1a for 32 bits (3039744951).
Peter de Rivaz <> on 2012-Mar-22 found a 1024-bit solution:
712131032390661212423469446429778580303529367161714287727915539272088837
388997682828851224650621762650604398414532544740385461220466517818153731
651665570936392160298954932547331005615954561744064764751259871084045735
302812555692177957250787849447135140298017119914349292668850620197682629
52245579219890855775 0xff octets.Richard Heylen <
> independently confirmed this solution.
NOTE: Russ Cox <
> observed that as a consequence of his solution to the consecutive NUL octet challenge, any consecutive stream of 0xff with a zero FNV-1 or FNV-1a hash of any size must be of odd length.
1024-bit solution by Johann N. Löfflmann on 2026-Nov-10:
445359075217293949446034810045247904893303946817563293272717969680141569
1296990024719495460337025148681118235657374213045756833266718213854105365691076111 0xff octets.Johann N. Löfflmann writes:
The length found by Peter de Rivaz <> is the shortest one. In fact it is the only length below 2^1024 for which the 1024-bit FNV-1a hash of that many 0xff octets is 0; every other solution is longer by a multiple of 2^1024.
As noted by Russ Cox <
>, the length is odd.
Proof:
Let P be the 1024-bit FNV prime, B the 1024-bit offset basis and f(h) = (h XOR 0xff) * P mod 2^1024. The FNV-1a hash of k octets 0xff is f^k(B), so we need the smallest k >= 1 with f^k(B) = 0. Write x0 = B and t = 0.
- f is a bijection of Z/2^1024 (XOR is a bijection, P is odd). So the orbit of x0 is a single cycle, and the k with f^k(x0) = 0 form one residue class modulo its length. The smallest k is unique and smaller than the cycle length.
- f is compatible with the reduction modulo 2^j for every j: the low j bits of f(h) only depend on the low j bits of h. In particular the low 8 bits s of the state run through a cycle of a permutation of Z/256. For x0 this cycle has length L = 128, so k is determined modulo 128 by the position r of 0 mod 256 on that cycle.
- XOR 0xff only changes the low 8 bits, so h XOR 0xff = h + d(s) with d(s) = (s XOR 0xff) - s, which only depends on s = h mod 256. Hence L = 128 steps from y = f^r(x0) on are an affine map G(h) = A*h + C mod 2^1024 with A = P^128 and a constant C. Powers G^q are computed by repeated squaring of affine maps, so f^n for huge n costs only a few thousand multiplications.
- We need the smallest q with G^q(y) = 0; then k = r + 128*q. The affine maps of Z/2^j form a group of order 2^(2j-1), so every orbit of G modulo 2^j has a length 2^e_j that is a power of 2, and e_(j+1) is e_j or e_j + 1. Therefore q can be lifted bit by bit: from the unique q_j modulo 2^e_j with G^q_j(y) = 0 (mod 2^j), the candidates modulo 2^e_(j+1) are q_j and q_j + 2^e_j, and exactly one of them works modulo 2^(j+1) when a solution exists. Here the orbit length of y under G modulo 2^1024 is 2^1016, so the cycle of x0 under f has length 128 * 2^1016 = 2^1023 (half of all states), and the lifting yields:
k = 712131032390661212423469446429778580303529367161714287727915539272088837
388997682828851224650621762650604398414532544740385461220466517818153731
651665570936392160298954932547331005615954561744064764751259871084045735
302812555692177957250787849447135140298017119914349292668850620197682629
52245579219890855775, which is the length found by Peter de Rivaz <>.
Nothing in this computation is sampled or searched heuristically, so the result is exact. It takes at most 2 seconds in Python.
Verification:
- A second, separate program computes the hash of k octets 0xff directly: it runs the FNV-1a steps explicitly up to a multiple of 256, determines the affine map of a block of 256 steps from explicit steps (and checks it on random states), and powers it. For the length above it gives 0. For k = 1, 255, 1000 and 4097 its results agree with the FNV-1a-1024 implementation of Jacksum (jacksum -a fnv-1a_1024 -x -q hex:ffff...).
- The same method reproduces the solved 0xff challenges on your page: FNV-1 for 32, 64, 256 and 512 bits (428876705, 9896220416391497057 and the results by Richard Heylen) and FNV-1a for 32 bits (3039744951).
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
32-bit solution by Russ Cox <> on 2011-Mar-02:
The solutions of length 5 are: FNV32_1(07 65 76 4a 3b) = 0 \a e v J ; FNV32_1(27 0f 56 47 0a) = 0 ' ^O V G \n FNV32_1(30 17 22 62 62) = 0 0 ^W " b b FNV32_1(30 33 53 42 5b) = 0 0 3 S B [ FNV32_1(54 20 75 7b 5b) = 0 T space u { [ FNV32_1(62 61 2c 31 71) = 0 b a , 1 q
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
64-bit solution by Peter de Rivaz <> on 2011-Mar-11:
Rudi Cilibrasi <The shortest solution is of length 10: FNV64_1(10 17 34 7c 28 61 38 72 64 4d) = 0 ^P ^H 4 ! ( a 8 r d M There are no solutions shorter than length 10.>, on 2014-Dec-26, verified the above 64-bit solution and found 43 more of the same length:
FNV64_1(0d 20 3f 5c 4f 7e 5e 18 56 64 ) = 0 FNV64_1(11 79 03 18 05 4e 13 3d 6d 74 ) = 0 FNV64_1(12 31 5a 0c 01 04 39 09 30 01 ) = 0 FNV64_1(15 5b 15 18 37 74 55 47 64 6f ) = 0 FNV64_1(21 47 5b 64 66 75 01 59 61 7a ) = 0 FNV64_1(29 28 57 2f 5b 0c 36 70 43 12 ) = 0 FNV64_1(29 78 6c 48 2e 3e 24 7b 10 25 ) = 0 FNV64_1(33 14 71 7d 24 03 6a 67 5c 20 ) = 0 FNV64_1(34 45 09 75 1d 05 6a 78 14 46 ) = 0 FNV64_1(35 46 77 16 38 13 2a 2e 21 4b ) = 0 FNV64_1(36 24 60 55 52 06 7b 60 6a 65 ) = 0 FNV64_1(39 41 05 59 56 32 5c 64 0d 72 ) = 0 FNV64_1(3d 23 1d 04 12 1e 70 38 66 78 ) = 0 FNV64_1(40 61 13 53 2a 14 45 2b 40 68 ) = 0 FNV64_1(44 08 7c 16 2e 1b 65 0d 1e 0a ) = 0 FNV64_1(4c 50 01 3f 50 4f 62 4d 59 5a ) = 0 FNV64_1(61 73 26 4a 71 39 06 47 29 5d ) = 0 FNV64_1(6a 6a 02 16 37 5f 28 53 72 46 ) = 0 FNV64_1(72 31 6f 68 3c 6f 39 0d 66 18 ) = 0 FNV64_1(72 3a 40 76 02 58 35 24 19 29 ) = 0 FNV64_1(01 44 42 05 34 6a 2f 29 31 10 ) = 0 FNV64_1(01 5e 68 02 53 4a 76 3d 1e 78 ) = 0 FNV64_1(04 66 63 3c 0c 4b 70 73 15 09 ) = 0 FNV64_1(0f 45 7c 0b 30 05 18 69 5d 55 ) = 0 FNV64_1(11 15 3d 2e 4c 25 59 30 7f 49 ) = 0 FNV64_1(12 1f 1a 1b 26 02 4a 16 0e 4b ) = 0 FNV64_1(12 2a 1c 09 73 52 7d 08 0c 20 ) = 0 FNV64_1(1c 47 57 23 14 1e 59 74 7a 3f ) = 0 FNV64_1(20 65 5b 68 4a 25 09 34 6c 21 ) = 0 FNV64_1(21 76 29 45 59 77 59 56 6b 26 ) = 0 FNV64_1(25 1d 3f 20 69 20 58 6e 6f 62 ) = 0 FNV64_1(31 30 02 56 05 58 0d 3e 6a 62 ) = 0 FNV64_1(33 69 2a 25 2f 34 06 2f 04 3a ) = 0 FNV64_1(34 1d 36 4e 2f 71 70 50 30 24 ) = 0 FNV64_1(39 04 2d 0f 12 65 01 26 2b 79 ) = 0 FNV64_1(4d 16 6a 48 6c 5e 7e 58 0a 30 ) = 0 FNV64_1(60 09 50 68 4b 21 4f 5b 1f 73 ) = 0 FNV64_1(65 32 24 01 20 44 2a 53 03 7d ) = 0 FNV64_1(65 7e 7c 15 40 13 64 2b 6e 43 ) = 0 FNV64_1(67 51 4f 1d 5c 18 47 03 3f 0a ) = 0 FNV64_1(71 1f 70 0b 78 25 43 0d 08 5b ) = 0 FNV64_1(7a 5f 63 61 14 38 16 10 09 01 ) = 0 FNV64_1(7f 4f 19 62 60 61 6e 16 4b 02 ) = 0
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
256-bit solution by Johann N. Löfflmann on 2026-Nov-10:
These are 7 solutions of length 37:
FNV256_1(0a 7e 06 62 60 6d 08 2d 7b 26 13 61 52 58 7f 5b 66 63 47 1f 24 41 6d 56 65 16 01 69 41 31 1e 52 2a 0d 2c 1d 6a) = 0   \n ~ ^F b ` m ^H - { & ^S a R X Del [ f c G ^_ $ A m V e ^V ^A i A 1 ^^ R * \r , ^] j
FNV256_1(14 48 33 5c 41 1d 27 67 6d 6b 0e 5b 48 43 28 76 67 3d 5b 2c 58 2d 6e 03 67 5b 1a 31 2b 39 1a 02 06 0b 3f 51 3b) = 0   ^T H 3 \ A ^] ' g m k ^N [ H C ( v g = [ , X - n ^C g [ ^Z 1 + 9 ^Z ^B ^F ^K ? Q ;
FNV256_1(1d 33 53 46 15 2a 61 28 34 7d 33 01 07 77 35 1e 72 5a 58 04 79 46 0e 4c 77 24 66 3b 78 1d 65 7f 73 25 7e 42 20) = 0   ^] 3 S F ^U * a ( 4 } 3 ^A ^G w 5 ^^ r Z X ^D y F ^N L w $ f ; x ^] e Del s % ~ B space
FNV256_1(27 03 52 53 5a 3a 65 2a 54 15 76 62 71 2d 22 3d 4b 42 1e 2d 06 29 0b 0d 68 64 3c 0c 77 0e 33 1e 48 4c 33 07 66) = 0   ' ^C R S Z : e * T ^U v b q - " = K B ^^ - ^F ) ^K \r h d < ^L w ^N 3 ^^ H L 3 ^G f
FNV256_1(27 69 50 3a 33 42 47 39 01 25 4d 36 2d 79 06 13 63 2c 42 4a 14 39 7c 1f 3e 58 38 58 09 35 4f 6f 63 5d 58 71 5c) = 0   ' i P : 3 B G 9 ^A % M 6 - y ^F ^S c , B J ^T 9 | ^_ > X 8 X \t 5 O o c ] X q \
FNV256_1(40 38 45 11 54 74 51 55 6d 56 73 26 52 56 24 5f 47 13 32 29 62 04 30 2a 27 74 68 3c 3b 2b 0f 1b 71 7a 73 1d 13) = 0   @ 8 E ^Q T t Q U m V s & R V $ _ G ^S 2 ) b ^D 0 * ' t h < ; + ^O Esc q z s ^] ^S
FNV256_1(74 21 3f 74 4a 67 2f 64 63 46 3d 6c 1a 1d 2b 60 3b 53 17 36 3e 66 58 31 19 6c 2f 41 3d 3e 14 06 59 6a 5c 4c 02) = 0   t ! ? t J g / d c F = l ^Z ^] + ` ; S ^W 6 > f X 1 ^Y l / A = > ^T ^F Y j \ L ^B
NOTE: Control characters in caret notation are used above.
According to Johann N. Löfflmann:
Each solution was verified independently with the FNV-1-256 implementation of Jacksum:
prints:jacksum -a fnv-1_256 -X -q hex:<hex>
0000000000000000000000000000000000000000000000000000000000000000Then using a short arbitrary-precision Python implementation with:
offset basis 100029257958052580907070968620625704837092796014241193945225284501741471925557, prime 2^168 + 2^8 + 0x63
Johann N. Löfflmann writes:
Is 37 the shortest length? Maybe.A counting argument gives 127^n / 2^256 expected solutions of length n (alphabet of 127 octets) than 0.0004 for all lengths up to 35 together:
n = 37: ~5.98 n = 36: ~0.047 n = 35: ~0.00037
- n = 36: a search with 10 randomized rounds over all 127 one-character prefixes found no solution. Its coverage cannot be measured directly (only about 0.06 candidate points of the linearized equations are expected in the whole search space), but the same settings found about 80 % of the solutions of length 37 in a single run (see below). Under the usual assumption that FNV-1-256 behaves like a random function, the probability that a solution of length 36 exists but was missed is then about 1 % (0.047 * 0.2), and at most about 5 % even if the search had found nothing at all.
- n = 37: two independent searches with different lattices (prefixes of 1 and of 2 characters) found 6 solutions each, 5 of them in both, so 7 different ones. A capture-recapture estimate gives about 7.2 solutions of length 37 in total (the counting argument expects about 6); probably the list above is complete or misses one solution.
Brute force is infeasible (127^37 ~ 2^258.6), so the search uses lattice reduction:
- FNV-1 multiplies first and XORs afterwards, so FNV-1(c_1..c_n) = FNV-1a'(c_1..c_(n-1)) XOR c_n, where FNV-1a' is FNV-1a with the offset basis basis * P. The hash is 0 iff FNV-1a'(c_1..c_(n-1)) = c_n. This has exactly the form of the FNV-1a problem, with a different start value.
- Every character is < 0x80, so the XOR only changes the lowest 7 bits of the state. With u_i = (h_(i-1) XOR c_i) mod 128 and r_i = h_i mod 128 = (99 * u_i) mod 128 (99 = FNV prime mod 128), the recurrence can be written exactly as G_i = (G_(i-1) + u_i) * P - r_i (mod 2^256), with G_i = h_i - r_i. The hash is 0 iff G_(n-1) = 0 and the last character equals r_(n-1).
- For a fixed prefix of 1 or 2 characters, the remaining 35 or 34 positions give a modular knapsack with small unknowns 0 <= u_t, r_t <= 127. This is a closest-vector problem in a fixed lattice of dimension 70 or 68; only the target depends on the prefix.
- The lattice is reduced once with exact integer LLL and BKZ-20. Then, for every prefix, Schnorr-Euchner enumeration with pruning ("extreme pruning": several rounds with randomly weighted metrics and re-randomized bases) lists the lattice points near the center of the cube [0,127]^(2M). Each point is translated back into characters and accepted only if no octet is NUL or >= 0x80 and the full 256-bit FNV-1 hash, recomputed with Jacksum, is 0.
- The same program, run exhaustively without pruning, reproduces exactly the published results of the 32- and 64-bit challenges (37, 38, 43, 49, 50, 55, 56, 61, 62, 67, 68), and it found the 128-bit solutions of challenges 39 and 45 (all solutions of length 19, proven exhaustively).
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
32-bit solution by Russ Cox <> on 2011-Mar-02:
The solutions of length 5 are: FNV32_1a(12 3b 5b 23 20) = 0 ^R ; [ # space FNV32_1a(2b 21 3d 79 47) = 0 + ! = y G FNV32_1a(2f 06 3c 37 71) = 0 / ^F < 7 q FNV32_1a(36 38 6d 2a 20) = 0 6 8 m * space FNV32_1a(40 24 1b 38 42) = 0 @ $ Esc 8 B FNV32_1a(4c 39 59 56 11) = 0 L 9 Y V ^Q FNV32_1a(59 08 26 60 62) = 0 Y \b & ` b FNV32_1a(60 4a 63 6f 11) = 0 ` J c o ^Q FNV32_1a(65 53 4e 2e 31) = 0 e S N . 1
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
64-bit solutions by Rudi Cilibrasi <> on 2014-Dec-26 believes there are no other solutions of the same or shorter length:
FNV64_1a(07 1e 62 37 2c 02 40 42 14 69 ) = 0 FNV64_1a(0a 4d 3e 21 16 68 02 0e 0c 6d ) = 0 FNV64_1a(0a 59 59 0e 24 44 2a 7b 60 70 ) = 0 FNV64_1a(0f 73 15 07 1b 6f 38 4b 17 39 ) = 0 FNV64_1a(10 28 59 4f 6d 07 0f 45 3f 2e ) = 0 FNV64_1a(16 43 29 25 71 1b 5c 65 7a 03 ) = 0 FNV64_1a(1c 7f 21 5c 2d 09 1a 03 7f 69 ) = 0 FNV64_1a(21 30 49 43 3d 56 6c 6f 61 59 ) = 0 FNV64_1a(26 04 5d 12 7c 7d 66 61 0c 26 ) = 0 FNV64_1a(3d 2e 20 68 78 22 69 58 3c 3b ) = 0 FNV64_1a(3d 66 7f 2f 6e 36 53 40 30 5d ) = 0 FNV64_1a(42 21 21 7b 16 0e 2f 65 67 25 ) = 0 FNV64_1a(46 2e 24 74 64 6f 3c 01 07 24 ) = 0 FNV64_1a(51 76 58 74 4d 3e 40 46 70 25 ) = 0 FNV64_1a(54 14 18 68 68 4b 14 3c 0a 72 ) = 0 FNV64_1a(58 59 54 4d 5c 4d 45 46 0d 7c ) = 0 FNV64_1a(5f 22 6b 57 6b 3d 2d 76 24 63 ) = 0 FNV64_1a(60 22 10 0e 59 21 65 39 7a 69 ) = 0 FNV64_1a(65 05 78 75 4f 47 3a 15 6a 23 ) = 0 FNV64_1a(65 79 15 0c 1d 73 32 40 5a 26 ) = 0 FNV64_1a(67 2c 21 55 66 46 29 7b 68 04 ) = 0 FNV64_1a(01 1c 4f 49 78 7e 12 6e 6d 61 ) = 0 FNV64_1a(05 46 2b 0d 6f 5f 67 1d 63 49 ) = 0 FNV64_1a(09 1c 11 5b 68 01 09 23 37 48 ) = 0 FNV64_1a(09 5c 02 44 11 06 58 5d 27 3f ) = 0 FNV64_1a(13 67 10 1b 08 30 2a 55 71 2a ) = 0 FNV64_1a(20 0e 75 1d 51 65 72 0a 62 0b ) = 0 FNV64_1a(21 41 46 17 02 63 03 5b 5b 76 ) = 0 FNV64_1a(22 42 59 2e 18 0a 14 6f 57 72 ) = 0 FNV64_1a(2d 64 37 3d 74 48 18 3e 38 4e ) = 0 FNV64_1a(30 5e 64 66 59 24 65 64 5f 06 ) = 0 FNV64_1a(31 51 18 5b 43 5f 3a 6b 60 49 ) = 0 FNV64_1a(36 48 0e 56 31 6f 17 59 38 0d ) = 0 FNV64_1a(3d 03 4f 76 44 69 7b 5b 3d 04 ) = 0 FNV64_1a(4d 1a 06 77 15 33 08 4d 01 21 ) = 0 FNV64_1a(56 1b 0d 31 28 39 04 09 35 63 ) = 0 FNV64_1a(56 35 71 38 31 4a 13 14 74 53 ) = 0 FNV64_1a(5f 01 62 60 20 4f 4a 62 5c 42 ) = 0 FNV64_1a(65 68 4f 66 68 21 3b 07 06 02 ) = 0 FNV64_1a(69 59 67 0c 2a 65 07 0d 46 0d ) = 0 FNV64_1a(69 5c 69 45 1a 78 3f 7b 49 21 ) = 0 FNV64_1a(6c 03 4c 6c 0f 05 4a 4e 7c 1c ) = 0 FNV64_1a(6c 38 33 4a 46 30 40 15 60 63 ) = 0 FNV64_1a(6c 55 0c 32 30 01 28 2f 2d 25 ) = 0 FNV64_1a(6e 09 5a 3a 1d 2b 63 77 16 44 ) = 0 FNV64_1a(6e 70 20 3e 33 19 4a 0f 07 77 ) = 0 FNV64_1a(7a 47 54 16 6e 75 42 78 2f 48 ) = 0 FNV64_1a(7b 3e 68 34 5f 71 43 2a 13 12 ) = 0As reported by Joseph Crail <
> on 2026-Jul-05:
There are no other solutions for non-NUL data sets of length 10 or smaller.As a quick sketch of my method, I shrank the search space for possible solutions by finding all strings of a given length that generate a hash with some number of consecutive suffix of zeroes, giving me a several order of magnitude reduction in possible candidates. I then evaluated all candidates in parallel to find any true solutions.
Joseph Crail kindly provided a formal write-up of my work in regards to the above.
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
128-bit solutions by Johann N. Löfflmann on 2026-Nov-09:These are 30 solutions of length 19 (control characters in caret notation): FNV128_1a(03 03 05 5f 49 0f 32 66 30 1b 42 61 54 4a 2f 48 67 03 40) = 0 ^C ^C ^E _ I ^O 2 f 0 Esc B a T J / H g ^C @ FNV128_1a(06 30 36 7a 34 76 6f 3f 6e 4b 12 39 0c 28 09 1c 25 1b 7c) = 0 ^F 0 6 z 4 v o ? n K ^R 9 ^L ( \t ^\ % Esc | FNV128_1a(07 12 51 40 27 76 2a 18 21 37 3b 50 1f 74 0d 7b 16 69 4f) = 0 ^G ^R Q @ ' v * ^X ! 7 ; P ^_ t \r { ^V i O FNV128_1a(0a 4e 18 14 09 2a 2d 1d 7d 66 07 19 76 46 7c 3d 04 20 58) = 0 \n N ^X ^T \t * - ^] } f ^G ^Y v F | = ^D space X FNV128_1a(0c 25 77 16 7e 4d 4d 5c 51 3e 1c 1e 7a 67 6c 36 1d 0a 1c) = 0 ^L % w ^V ~ M M \ Q > ^\ ^^ z g l 6 ^] \n ^\ FNV128_1a(13 02 67 57 46 1b 14 1c 05 26 04 49 2f 79 0a 6c 4e 5f 10) = 0 ^S ^B g W F Esc ^T ^\ ^E & ^D I / y \n l N _ ^P FNV128_1a(18 44 42 37 33 7b 69 18 42 26 55 39 55 5c 51 19 33 42 31) = 0 ^X D B 7 3 { i ^X B & U 9 U \ Q ^Y 3 B 1 FNV128_1a(1d 20 0b 6d 18 73 2e 30 0b 0f 4e 1d 65 2f 66 6c 17 12 23) = 0 ^] space ^K m ^X s . 0 ^K ^O N ^] e / f l ^W ^R # FNV128_1a(21 6f 5a 6a 76 28 42 77 25 18 35 27 10 62 78 7e 58 24 15) = 0 ! o Z j v ( B w % ^X 5 ' ^P b x ~ X $ ^U FNV128_1a(24 26 49 09 76 63 0e 17 6a 2d 5c 3a 1f 10 7f 1f 71 68 4e) = 0 $ & I \t v c ^N ^W j - \ : ^_ ^P Del ^_ q h N FNV128_1a(27 7d 15 4d 16 7b 7e 5b 51 4b 39 42 68 0a 13 7b 0c 62 12) = 0 ' } ^U M ^V { ~ [ Q K 9 B h \n ^S { ^L b ^R FNV128_1a(29 58 2a 73 17 65 54 2b 6d 68 54 0a 6f 23 52 35 3d 03 12) = 0 ) X * s ^W e T + m h T \n o # R 5 = ^C ^R FNV128_1a(2a 0e 23 59 6b 3a 19 5a 2d 6b 0b 24 2e 16 07 62 54 0f 3c) = 0 * ^N # Y k : ^Y Z - k ^K $ . ^V ^G b T ^O < FNV128_1a(2f 54 6f 41 09 65 21 77 02 14 5c 12 79 11 1b 58 42 0b 02) = 0 / T o A \t e ! w ^B ^T \ ^R y ^Q Esc X B ^K ^B FNV128_1a(3f 17 79 3e 46 65 33 31 28 26 13 47 23 79 2c 7f 5a 78 7e) = 0 ? ^W y > F e 3 1 ( & ^S G # y , Del Z x ~ FNV128_1a(3f 1d 72 60 22 39 7c 5d 16 01 0f 77 46 6a 19 40 65 79 61) = 0 ? ^] r ` " 9 | ] ^V ^A ^O w F j ^Y @ e y a FNV128_1a(47 3d 53 5b 52 24 1e 56 16 18 05 37 19 7b 4b 41 14 52 31) = 0 G = S [ R $ ^^ V ^V ^X ^E 7 ^Y { K A ^T R 1 FNV128_1a(49 63 18 18 0f 5d 12 0b 47 3a 4b 41 68 40 4c 36 12 6a 11) = 0 I c ^X ^X ^O ] ^R ^K G : K A h @ L 6 ^R j ^Q FNV128_1a(4b 14 42 18 69 19 0a 60 4a 7d 37 3f 44 63 2d 39 72 2c 02) = 0 K ^T B ^X i ^Y \n ` J } 7 ? D c - 9 r , ^B FNV128_1a(4c 4b 5c 62 54 1b 44 0a 69 11 21 60 56 5b 01 64 5e 15 01) = 0 L K \ b T Esc D \n i ^Q ! ` V [ ^A d ^ ^U ^A FNV128_1a(4e 7e 2d 48 76 29 64 41 31 4d 31 13 1f 46 72 26 64 0a 07) = 0 N ~ - H v ) d A 1 M 1 ^S ^_ F r & d \n ^G FNV128_1a(50 63 0f 10 69 71 2a 41 69 16 5f 05 76 4b 6b 4d 5f 7b 72) = 0 P c ^O ^P i q * A i ^V _ ^E v K k M _ { r FNV128_1a(5b 72 4b 61 4f 64 35 40 4d 55 5b 3d 1d 4f 47 15 54 06 3e) = 0 [ r K a O d 5 @ M U [ = ^] O G ^U T ^F > FNV128_1a(61 3e 1d 55 13 0a 3e 41 68 41 64 75 36 0e 40 41 08 51 64) = 0 a > ^] U ^S \n > A h A d u 6 ^N @ A \b Q d FNV128_1a(61 6b 32 6c 33 68 06 77 19 0a 43 11 27 07 06 5c 55 57 5c) = 0 a k 2 l 3 h ^F w ^Y \n C ^Q ' ^G ^F \ U W \ FNV128_1a(6b 2e 04 51 4d 1d 27 50 03 2f 5a 0c 4e 7c 2c 17 10 42 33) = 0 k . ^D Q M ^] ' P ^C / Z ^L N | , ^W ^P B 3 FNV128_1a(73 4b 6f 6b 59 61 69 46 7f 71 27 27 24 43 7f 4f 18 42 0f) = 0 s K o k Y a i F Del q ' ' $ C Del O ^X B ^O FNV128_1a(74 21 2b 7f 20 69 7e 01 76 62 18 72 11 32 16 42 51 32 0c) = 0 t ! + Del space i ~ ^A v b ^X r ^Q 2 ^V B Q 2 ^L FNV128_1a(78 71 35 58 22 62 4a 47 0a 77 2a 1c 23 34 24 02 0a 03 77) = 0 x q 5 X " b J G \n w * ^\ # 4 $ ^B \n ^C w FNV128_1a(7a 30 18 2d 04 4d 6a 1e 43 3d 26 3c 64 76 09 7f 1e 45 1e) = 0 z 0 ^X - ^D M j ^^ C = & < d v \t Del ^^ E ^^According to Johann N. Löfflmann: Each solution was verified independently with the FNV-1a-128 implementation of Jacksum:
prints:jacksum -a fnv-1a_128 -X -q hex:<hex>00000000000000000000000000000000Then using a short arbitrary-precision Python implementation with:offset basis 144066263297769815596495629667062367629 prime 2^88 + 2^8 + 0x3bJohann N. Löfflmann writes:
Is 19 the shortest length, and are these all solutions of length 19? Yes.All lengths up to 19 were searched exhaustively:
- n = 1..6: exact meet-in-the-middle search with a separate Python program that does not share code with the lattice search. It stores all FNV-1a states after the first ceil(n/2) characters and looks up all states computed backwards from the hash 0. No solution.
- n = 7..19: the lattice search described below, run in its exhaustive mode: no pruning, and the enumeration ball contains the whole cube of admissible values, so it finds every string of the given length with hash 0. For n = 17..19, prefixes of 1, 2 and 4 characters were fixed (127, 16129 and 260144641 lattice problems of dimension 30, 30 and 28), which keeps the enumeration small (n = 19: about 16 minutes on 14 cores). No solution for n <= 18. For n = 19, the search found exactly the 30 solutions listed above, the same ones as an earlier pruned search.
The counting argument agrees: 127^n / 2^128 gives about 27.6 expected solutions for n = 19 and about 0.22 for n = 18.
The exhaustive mode was checked against your page: for 32 and 64 bits it reproduces exactly the published solutions of challenges 37, 38, 43, 49, 50, 55, 56, 61, 62, 67 and 68, and finds no solution of the next shorter length in each case. The meet-in-the-middle program reproduces the published 32-bit results of challenges 43, 55 and 67.
Brute force is infeasible (127^19 ~ 2^132.8), so the search uses lattice reduction:
- Every character is < 0x80, so the XOR only changes the lowest 7 bits of the state. With u_i = (h_{i-1} XOR c_i) mod 128 and r_i = h_i mod 128 = (59 * u_i) mod 128 (59 = FNV prime mod 128), the recurrence can be written exactly as G_i = (G_{i-1} + u_i) * P - r_i (mod 2^128), with G_i = h_i - r_i. The hash is 0 iff G_{n-1} = 0 and the last character equals r_{n-1}.
- The n - 1 = 18 positions give a modular knapsack with small unknowns 0 <= u_t, r_t <= 127. This is a closest-vector problem in a 36-dimensional lattice.
- The lattice is reduced with exact integer LLL and BKZ-20. Then Schnorr-Euchner enumeration with pruning ("extreme pruning": several rounds with randomly weighted metrics and re-randomized bases) lists the lattice points in the cube [0,127]^36. Each point is translated back into characters c = s XOR u and accepted only if no octet is NUL and the full 128-bit hash, recomputed with Jacksum, is 0.
- As a check, the same program, run exhaustively without pruning, reproduces exactly the published results for challenge 43 (32-bit, non-NUL: the 9 solutions of length 5), challenges 55/56 (printable, 32/64-bit) and challenges 67/68 (alphanumeric, 32/64-bit).
The same 36 lattice points also settle n = 19 for challenge 57 (printable ASCII): none of them is printable, which is why its shortest length is 20. I am sending that solution separately.
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
256-bit solution by Johann N. Löfflmann on 2026-Nov-10:
These are 5 solutions of length 37:
FNV256_1a(04 06 20 4a 3c 59 1f 78 38 62 13 3f 02 1e 16 64 74 34 36 22 3e 7e 67 3b 3f 7e 6c 7b 11 43 47 60 1c 49 2c 06 3f) = 0 ^D ^F space J < Y ^_ x 8 b ^S ? ^B ^^ ^V d t 4 6 " > ~ g ; ? ~ l { ^Q C G ` ^\ I , ^F ?
FNV256_1a(09 58 34 2d 49 17 74 5a 48 2d 36 27 13 73 37 0d 1d 32 64 06 0f 42 1c 01 01 6b 61 36 2b 23 66 63 04 78 6f 5a 1f) = 0 \t X 4 - I ^W t Z H - 6 ' ^S s 7 \r ^] 2 d ^F ^O B ^\ ^A ^A k a 6 + # f c ^D x o Z ^_
FNV256_1a(10 60 45 63 1f 0c 4b 09 43 22 53 08 4f 28 34 1e 27 79 43 0b 04 6a 56 37 37 6a 24 77 77 06 4a 29 7d 0d 06 40 76) = 0 ^P ` E c ^_ ^L K \t C " S ^H O ( 4 ^^ ' y C ^K ^D j V 7 7 j $ w w ^F J ) } \r ^F @ v
FNV256_1a(1f 03 6c 54 7e 4e 53 59 10 5c 27 77 50 7f 7a 1a 1d 01 43 6c 37 0e 48 6b 5f 2c 1d 0d 01 31 3c 60 19 71 53 19 10) = 0 ^_ ^C l T ~ N S Y ^P \ ' w P Del z ^Z ^] ^A C l 7 ^N H k _ , ^] \r ^A 1 < ` ^Y q S ^Y ^P
FNV256_1a(2a 1c 4e 44 0d 18 5f 46 6c 13 2d 6c 36 08 79 36 3f 6d 37 40 1a 42 6c 0b 08 20 48 78 56 4d 21 22 24 66 38 68 72) = 0 * ^\ N D \r ^X _ F l ^S - l 6 ^H y 6 ? m 7 @ ^Z B l ^K ^H space H x V M ! " $ f 8 h r
NOTE: Control characters in caret notation are used above.
According to Johann N. Löfflmann:
Each solution was verified independently with the FNV-1a-256 implementation of Jacksum:
prints:jacksum -a fnv-1a_256 -X -q hex:<hex>
0000000000000000000000000000000000000000000000000000000000000000Then using a short arbitrary-precision Python implementation with:
offset basis 100029257958052580907070968620625704837092796014241193945225284501741471925557, prime 2^168 + 2^8 + 0x63
Johann N. Löfflmann writes:
Is 37 the shortest length? Maybe.A counting argument gives 127^n / 2^256 expected solutions of length n (alphabet of 127 octets) than 0.0004 for all lengths up to 35 together:
n = 37: ~5.98 n = 36: ~0.047 n = 35: ~0.00037
- n = 36: a search with 10 randomized rounds over all 127 one-character prefixes found no solution. Its coverage cannot be measured directly (only about 0.06 candidate points of the linearized equations are expected in the whole search space), but the same settings found about 75 % of the solutions of length 37 in a single run (see below). Under the usual assumption that FNV-1a-256 behaves like a random function, the probability that a solution of length 36 exists but was missed is then about 1 % (0.047 * 0.25), and at most about 5 % even if the search had found nothing at all.
- * n = 37: two independent searches with different lattices (prefixes of 1 and of 2 characters) found 4 solutions each, 3 of them in both, so 5 different ones. A capture-recapture estimate gives about 5.3 solutions of length 37 in total, in line with the counting argument; probably the list above is complete or misses one solution.
Brute force is infeasible (127^37 ~ 2^258.6), so the search uses lattice reduction:
- Every character is < 0x80, so the XOR only changes the lowest 7 bits of the state. With u_i = (h_(i-1) XOR c_i) mod 128 and r_i = h_i mod 128 = (99 * u_i) mod 128 (99 = FNV prime mod 128), the recurrence can be written exactly as G_i = (G_(i-1) + u_i) * P - r_i (mod 2^256), with G_i = h_i - r_i. The hash is 0 iff G_(n-1) = 0 and the last character equals r_(n-1).
- For a fixed prefix of 1 or 2 characters, the remaining 35 or 34 positions give a modular knapsack with small unknowns 0 <= u_t, r_t <= 127. This is a closest-vector problem in a fixed lattice of dimension 70 or 68; only the target depends on the prefix.
- The lattice is reduced once with exact integer LLL and BKZ-20. Then, for every prefix, Schnorr-Euchner enumeration with pruning ("extreme pruning": several rounds with randomly weighted metrics and re-randomized bases) lists the lattice points near the center of the cube [0,127]^(2M). Each point is translated back into characters and accepted only if no octet is NUL or >= 0x80 and the full 256-bit FNV-1a hash, recomputed with Jacksum, is 0.
- The same program, run exhaustively without pruning, reproduces exactly the published results of the 32- and 64-bit challenges (37, 38, 43, 49, 50, 55, 56, 61, 62, 67, 68), and it found the 128-bit solutions of challenges 39 and 45 (all solutions of length 19, proven exhaustively).
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
32-bit hash solution by Russ Cox <> on 2011-Mar-02:
The solutions of length 5 are: FNV32_1(30 33 53 42 5b) = 0 0 3 S B [ FNV32_1(54 20 75 7b 5b) = 0 T Space u { [ FNV32_1(62 61 2c 31 71) = 0 b a , 1 q
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
64-bit solution by Rudi Cilibrasi <>, on 2014-Dec-26 believes there are no other solutions of the same or shorter length:
FNV64_1(21 76 29 45 59 77 59 56 6b 26) = 0 !v)EYwYVk&Johann N. Löfflmann, on 2026-Nov-09, proved that there is exactly 1 solution of length 10.
How Johann N. Löfflmann checked their proof:
- Lengths 1..6: exact meet-in-the-middle search (stores all states after the first ceil(n/2) characters and looks up all states computed backwards from the hash 0). No solution for any of the four challenges.
- Lengths 7..10: an exhaustive lattice search. The XOR with a character < 0x80 only changes the lowest 7 bits of the state, which makes the zero-hash condition an exact linear equation with small unknowns. All its solutions in the admissible range are enumerated without pruning, inside a ball that contains the whole range, so the search finds every string of a given length with hash 0. Result: no solution below the published length, and at the published length exactly the published solutions.
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
128-bit solutions by Johann N. Löfflmann on 2026-Nov-09:These are 5 solutions of length 20: FNV128_1(3d 6c 3f 2b 43 3b 64 6f 76 51 59 38 47 4b 42 50 75 5e 4a 46) = 0 =l?+C;dovQY8GKBPu^JF FNV128_1(56 69 79 32 68 6d 79 6b 41 30 56 46 45 3a 65 3d 36 5b 2b 5e) = 0 Viy2hmykA0VFE:e=6[+^ FNV128_1(5b 4f 27 41 2f 69 43 20 35 6d 23 20 7c 3e 66 68 40 36 4c 47) = 0 [O'A/iC 5m# |>fh@6LG FNV128_1(68 4a 3c 7b 59 48 4e 7b 29 5d 54 69 4d 49 48 65 45 77 31 5d) = 0 hJ<{YHN{)]TiMIHeEw1] FNV128_1(6e 7e 35 71 35 76 69 31 49 79 42 7c 6f 3d 35 51 71 77 32 30) = 0 n~5q5vi1IyB|o=5Qqw20According to Johann N. Löfflmann: Each solution was verified independently with the FNV-1a-128 implementation of Jacksum:
prints:jacksum -a fnv-1_128 -X -q hex:<hex>00000000000000000000000000000000Then using a short arbitrary-precision Python implementation with:offset basis 144066263297769815596495629667062367629 prime 2^88 + 2^8 + 0x3bJohann N. Löfflmann writes:
Is 20 the shortest length? Yes.All lengths up to 19 were searched exhaustively:
- n = 1..6: exact meet-in-the-middle search with a separate Python program that does not share code with the lattice search. It stores all FNV-1 states after the first ceil(n/2) characters and looks up all states computed backwards from the hash 0. No solution.
- n = 7..19: the lattice search described below, run in its exhaustive mode: no pruning, and the enumeration ball contains the whole cube of admissible values, so it finds every string of the given length with hash 0. For n = 18 and 19, prefixes of 2 and 4 characters were fixed (9025 and 81450625 lattice problems of dimension 30 and 28), which keeps the enumeration small (n = 19: about 3-4 minutes on 14 cores). No solution.
The counting argument agrees: 95^n / 2^128 gives about 10.5 expected solutions for n = 20 and about 0.11 for n = 19.
Whether the 5 solutions above are all solutions of length 20 is not proven. The pruned search for n = 20 ran 400 randomized rounds; the last 340 rounds found no new solution, so the list is very likely complete. An exhaustive search of n = 20 would take roughly 8 hours on 14 cores.
The exhaustive mode was checked against your page: for 32 and 64 bits it reproduces exactly the published solutions of challenges 37, 38, 43, 49, 50, 55, 56, 61, 62, 67 and 68, and finds no solution of the next shorter length in each case. The meet-in-the-middle program reproduces the published 32-bit results of challenges 43, 55 and 67.
So, assuming the program is correct, 20 is the shortest length.
Brute force is infeasible, so the search uses lattice reduction:
- FNV-1 multiplies first and XORs afterwards, so FNV-1(c_1..c_n) = FNV-1a'(c_1..c_(n-1)) XOR c_n, where FNV-1a' is FNV-1a with the offset basis basis * P. The hash is 0 iff FNV-1a'(c_1..c_(n-1)) = c_n. This has exactly the form of the FNV-1a problem, with a different start value.
- Every character is < 0x80, so each XOR only changes the lowest 7 bits of the state. With u_i = (h_(i-1) XOR c_i) mod 128 and r_i = h_i mod 128 = (59 * u_i) mod 128 (59 = FNV prime mod 128), the FNV-1a recurrence can be written exactly as G_i = (G_(i-1) + u_i) * P - r_i (mod 2^128), with G_i = h_i - r_i. For a fixed prefix, the remaining 18 positions give a modular knapsack with small unknowns 0 <= u_t, r_t <= 127. This is a closest-vector problem in a fixed 36-dimensional lattice; only the target depends on the prefix.
- The lattice is reduced once with exact integer LLL and BKZ-20. Then, for every prefix, Schnorr-Euchner enumeration with pruning ("extreme pruning": several rounds with randomly weighted metrics and re-randomized bases) lists the lattice points in the cube [0,127]^36. Each point is translated back into characters and accepted only if all octets are printable and the full 128-bit FNV-1 hash, recomputed with Jacksum, is 0.
- As a check, the same program, run exhaustively without pruning, reproduces exactly the published FNV-1 results for challenges 37 and 38 (non-NUL, 32/64-bit: 6 and 44 solutions), 49 and 50 (printable, 32/64-bit: 3 solutions and !v)EYwYVk&) and 61 and 62 (alphanumeric, 32/64-bit: 14 and 3 solutions), and the corresponding FNV-1a results.
NOTE: By printable ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x40 - 0x7e]
NOTE: By printable ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x40 - 0x7e]
NOTE: By printable ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x40 - 0x7e]
NOTE: By printable ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x40 - 0x7e]
32-bit hash solution by Russ Cox <> on 2011-Mar-02:
The solutions of length 5 are: FNV32_1a(2b 21 3d 79 47) = 0 + ! = y G FNV32_1a(36 38 6d 2a 20) = 0 6 8 m * Space FNV32_1a(65 53 4e 2e 31) = 0 e S N . 1
NOTE: By printable ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x40 - 0x7e]
64-bit solutions by Rudi Cilibrasi <>, on 2014-Dec-26 believes there are no other solutions of the same or shorter length:
FNV64_1a(21 30 49 43 3d 56 6c 6f 61 59) = 0 !0IC=VloaY FNV64_1a(3d 2e 20 68 78 22 69 58 3c 3b) = 0 =. hx"iX<; FNV64_1a(51 76 58 74 4d 3e 40 46 70 25) = 0 QvXtM%gt;@Fp% FNV64_1a(5f 22 6b 57 6b 3d 2d 76 24 63) = 0 _"kWk=-v$cAs reported by Joseph Crail <
> on 2026-Jul-05:
There are no other solutions for printable data sets of length 10 or smaller.As a quick sketch of my method, I shrank the search space for possible solutions by finding all strings of a given length that generate a hash with some number of consecutive suffix of zeroes, giving me a several order of magnitude reduction in possible candidates. I then evaluated all candidates in parallel to find any true solutions.
Joseph Crail kindly provided a formal write-up of my work in regards to the above.
Johann N. Löfflmann, on 2026-Nov-09, proved that there is exactly 4 solutions of length 10.
How Johann N. Löfflmann checked their proof:
- Lengths 1..6: exact meet-in-the-middle search (stores all states after the first ceil(n/2) characters and looks up all states computed backwards from the hash 0). No solution for any of the four challenges.
- Lengths 7..10: an exhaustive lattice search. The XOR with a character < 0x80 only changes the lowest 7 bits of the state, which makes the zero-hash condition an exact linear equation with small unknowns. All its solutions in the admissible range are enumerated without pruning, inside a ball that contains the whole range, so the search finds every string of a given length with hash 0. Result: no solution below the published length, and at the published length exactly the published solutions.
NOTE: By printable ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x40 - 0x7e]
128-bit solutions by Johann N. Löfflmann on 2026-Nov-09:These are 10 solutions of length 20: FNV128_1a(25 54 32 5b 4e 2d 34 5e 48 6f 4d 34 79 3c 4a 5a 2e 6f 62 54) = 0 %T2[N-4^HoM4y<JZ.obT FNV128_1a(2e 4d 5c 28 45 39 61 2a 31 56 35 44 31 4e 79 7d 50 7c 4c 36) = 0 .M\(E9a*1V5D1Ny}P|L6 FNV128_1a(34 22 33 5d 77 39 4b 62 62 72 73 68 6a 60 65 2b 2e 65 46 68) = 0 4"3]w9Kbbrshj`e+.eFh FNV128_1a(34 7c 5e 36 45 30 5b 23 22 65 4c 40 47 6f 22 4b 5c 71 58 53) = 0 4|^6E0[#"eL@Go"K\qXS FNV128_1a(3b 4b 2f 5a 31 4e 33 70 41 37 7c 6f 2e 4d 6d 7d 7a 40 33 6f) = 0 ;K/Z1N3pA7|o.Mm}z@3o FNV128_1a(3d 42 3f 40 2b 23 71 41 7b 70 57 63 48 2f 34 37 59 26 38 75) = 0 =B?@+#qA{pWcH/47Y&8u FNV128_1a(50 54 3f 3a 28 26 78 7b 51 37 63 4f 26 31 3f 2a 6e 68 72 3f) = 0 PT?:(&x{Q7cO&1?*nhr? FNV128_1a(53 5c 4a 21 4c 5b 7a 45 3b 63 4f 51 38 37 39 64 43 34 4c 62) = 0 S\J!L[zE;cOQ879dC4Lb FNV128_1a(6a 26 57 65 30 68 75 21 77 26 40 45 46 37 64 7b 71 29 63 5a) = 0 j&We0hu!w&@EF7d{q)cZ FNV128_1a(6b 4a 65 6d 77 63 4e 66 57 4c 20 75 5f 48 39 29 6d 3f 5e 2d) = 0 kJemwcNfWL u_H9)m?^- The hex column is authoritative; the last solution contains a space (0x20).According to Johann N. Löfflmann: Each solution was verified independently with the FNV-1a-128 implementation of Jacksum:
prints:jacksum -a fnv-1a_128 -X -q hex:<hex>00000000000000000000000000000000Then using a short arbitrary-precision Python implementation with:offset basis 144066263297769815596495629667062367629 prime 2^88 + 2^8 + 0x3bJohann N. Löfflmann writes:
Is 20 the shortest length? Yes.All lengths up to 19 were searched exhaustively:
- n = 1..6: exact meet-in-the-middle search with a separate Python program that does not share code with the lattice search. It stores all FNV-1a states after the first ceil(n/2) characters and looks up all states computed backwards from the hash 0. No solution.
- n = 7..19: the lattice search described below, run in its exhaustive mode: no pruning, and the enumeration ball contains the whole cube of admissible values, so it finds every string of the given length with hash 0. For n = 18 and 19, prefixes of 2 and 4 characters were fixed (9025 and 81450625 lattice problems of dimension 30 and 28), which keeps the enumeration small (n = 19: about 3-4 minutes on 14 cores). No solution.
The counting argument agrees: 95^n / 2^128 gives about 10.5 expected solutions for n = 20 and about 0.11 for n = 19.
Whether the 10 solutions above are all solutions of length 20 is not proven. The pruned search for n = 20 ran 400 randomized rounds; the last 340 rounds found no new solution, so the list is very likely complete. An exhaustive search of n = 20 would take roughly 8 hours on 14 cores.
The exhaustive mode was checked against your page: for 32 and 64 bits it reproduces exactly the published solutions of challenges 37, 38, 43, 49, 50, 55, 56, 61, 62, 67 and 68, and finds no solution of the next shorter length in each case. The meet-in-the-middle program reproduces the published 32-bit results of challenges 43, 55 and 67.
So, assuming the program is correct, 20 is the shortest length.
NOTE: By printable ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x40 - 0x7e]
NOTE: By printable ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x40 - 0x7e]
NOTE: By printable ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x40 - 0x7e]
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
32-bit hash solution by Russ Cox <> on 2011-Mar-02:
The solutions of length 6 are: FNV32_1(33 64 37 41 35 4b) = 0 3 d 7 A 5 K FNV32_1(39 71 36 4d 71 33) = 0 9 q 6 M q 3 FNV32_1(48 48 59 53 4c 45) = 0 H H Y S L E FNV32_1(54 72 4c 64 5a 31) = 0 T r L d Z 1 FNV32_1(56 4c 33 42 71 43) = 0 V L 3 B q C FNV32_1(57 41 64 32 60 57) = 0 W A d 2 ` W FNV32_1(59 55 6f 31 39 6c) = 0 Y U o 1 9 l FNV32_1(59 66 36 68 50 36) = 0 Y f 6 h P 6 FNV32_1(68 49 72 6a 46 6a) = 0 h I r j F j FNV32_1(6e 60 62 76 33 52) = 0 n ` b v 3 R FNV32_1(70 6c 49 7a 6c 60) = 0 p l I z l ` FNV32_1(75 4d 6b 60 39 51) = 0 u M k ` 9 Q FNV32_1(79 73 6f 70 48 6c) = 0 y s o p H l FNV32_1(7a 63 49 6b 43 65) = 0 z c I k C e
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
NOTE: By non-NUL ASCII string we mean any arbitrary collection of non-NUL ASCII 8-bit characters in the range: [0x01 - 0x7f].
64-bit solutions by Rudi Cilibrasi <>, on 2014-Dec-26 believes there are no other solutions of the same or shorter length:
FNV64_1(4d 74 35 4b 65 78 6e 79 33 31 6e) = 0 Mt5Kexny31n FNV64_1(4f 6a 53 48 6a 69 6b 50 4e 59 56) = 0 OjSHjikPNYV FNV64_1(59 49 41 39 59 57 4d 4f 41 52 58) = 0 YIA9YWMOARXJohann N. Löfflmann, on 2026-Nov-09, proved that there is exactly 3 solutions of length 11.
How Johann N. Löfflmann checked their proof:
- Lengths 1..6: exact meet-in-the-middle search (stores all states after the first ceil(n/2) characters and looks up all states computed backwards from the hash 0). No solution for any of the four challenges.
- Lengths 7..11: an exhaustive lattice search. The XOR with a character < 0x80 only changes the lowest 7 bits of the state, which makes the zero-hash condition an exact linear equation with small unknowns. All its solutions in the admissible range are enumerated without pruning, inside a ball that contains the whole range, so the search finds every string of a given length with hash 0. Result: no solution below the published length, and at the published length exactly the published solutions.
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
128-bit solutions by Johann N. Löfflmann on 2026-Nov-09:These are 5 solutions of length 22: FNV128_1(35 6b 64 69 43 66 34 69 44 70 36 31 39 30 33 65 7a 34 4f 32 65 48) = 0 5kdiCf4iDp61903ez4O2eH FNV128_1(36 70 71 64 76 52 57 66 66 33 64 5a 30 4f 36 57 73 6b 49 77 31 63) = 0 6pqdvRWff3dZ0O6WskIw1c FNV128_1(59 4c 73 47 6e 68 53 56 56 34 64 4e 45 7a 41 54 63 48 6f 59 44 4a) = 0 YLsGnhSVV4dNEzATcHoYDJ FNV128_1(66 72 33 53 6c 7a 30 32 66 4f 6f 4d 65 4e 75 6a 60 74 57 5a 6f 38) = 0 fr3Slz02fOoMeNuj`tWZo8 FNV128_1(6a 63 6e 78 51 67 56 62 47 60 50 46 70 47 44 49 72 42 66 38 30 55) = 0 jcnxQgVbG`PFpGDIrBf80UAccording to Johann N. Löfflmann: Each solution was verified independently with the FNV-1a-128 implementation of Jacksum:
prints:jacksum -a fnv-1_128 -X -q hex:<hex>00000000000000000000000000000000Then using a short arbitrary-precision Python implementation with:offset basis 144066263297769815596495629667062367629 prime 2^88 + 2^8 + 0x3bJohann N. Löfflmann writes:
Is 22 the shortest length? Maybe.A counting argument gives 63^n / 2^128 expected solutions of length n (alphabet of 63 octets).
n = 22: ~11.3 n = 21: ~0.18 n = 20: ~0.003
- n = 21: 120 rounds over all 63^2 = 3969 two-character prefixes found 125119 of about 127008 expected candidate points (recall about 98.5 %) and no solution. The probability that a solution of length 21 exists but was missed is therefore about 0.18 * 0.015 ~ 0.3 %.
- n = 22: 3 rounds over all 63^3 = 250047 three-character prefixes (recall about 62 %) found the 5 solutions above. More rounds would very likely find more solutions of length 22 (about 11 are expected in total).
- n = 20: 60 rounds over all 63 one-character prefixes (recall about 95 %) found no solution.
Two of the solutions contain a backtick (0x60), which is part of the alphabet as defined on your page; the other three use only [0-9A-Za-z]. This is not a proof, but a shorter solution is very unlikely (about 0.3 %), assuming FNV-1-128 behaves like a random function.
Brute force is infeasible, so the search uses lattice reduction:
- FNV-1 multiplies first and XORs afterwards, so FNV-1(c_1..c_n) = FNV-1a'(c_1..c_(n-1)) XOR c_n, where FNV-1a' is FNV-1a with the offset basis basis * P. The hash is 0 iff FNV-1a'(c_1..c_(n-1)) = c_n. This has exactly the form of the FNV-1a problem, with a different start value.
- Every character is < 0x80, so each XOR only changes the lowest 7 bits of the state. With u_i = (h_(i-1) XOR c_i) mod 128 and r_i = h_i mod 128 = (59 * u_i) mod 128 (59 = FNV prime mod 128), the FNV-1a recurrence can be written exactly as G_i = (G_(i-1) + u_i) * P - r_i (mod 2^128), with G_i = h_i - r_i. For a fixed prefix, the remaining 18 positions give a modular knapsack with small unknowns 0 <= u_t, r_t <= 127. This is a closest-vector problem in a fixed 36-dimensional lattice; only the target depends on the prefix.
- The lattice is reduced once with exact integer LLL and BKZ-20. Then, for every prefix, Schnorr-Euchner enumeration with pruning ("extreme pruning": several rounds with randomly weighted metrics and re-randomized bases) lists the lattice points in the cube [0,127]^36. Each point is translated back into characters and accepted only if all octets are alphanumeric and the full 128-bit FNV-1 hash, recomputed with Jacksum, is 0.
- As a check, the same program, run exhaustively without pruning, reproduces exactly the published FNV-1 results for challenges 37 and 38 (non-NUL, 32/64-bit: 6 and 44 solutions), 49 and 50 (printable, 32/64-bit: 3 solutions and !v)EYwYVk&) and 61 and 62 (alphanumeric, 32/64-bit: 14 and 3 solutions), and the corresponding FNV-1a results.
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
32-bit hash solution by Russ Cox <> on 2011-Mar-02:
A fun 32-bit hash solution by KKChen (from China) was reported on 2026-Mar-25:The solutions of length 6 are: FNV32_1a(33 70 6a 4e 71 4d) = 0 3 p j N q M FNV32_1a(35 52 30 4c 67 37) = 0 5 R 0 L g 7 FNV32_1a(37 6f 45 34 38 36) = 0 7 o E 4 8 6 FNV32_1a(42 52 34 32 71 66) = 0 B R 4 2 q f FNV32_1a(46 6f 75 42 53 72) = 0 F o u B S r FNV32_1a(47 6b 6b 7a 46 44) = 0 G k k z F D FNV32_1a(48 56 47 5a 71 39) = 0 H V G Z q 9 FNV32_1a(49 77 50 53 64 54) = 0 I w P S d T FNV32_1a(60 6e 72 59 33 47) = 0 ` n r Y 3 G FNV32_1a(71 7a 73 30 55 44) = 0 q z s 0 U D FNV32_1a(73 58 62 73 73 72) = 0 s X b s s r FNV32_1a(75 68 34 74 53 49) = 0 u h 4 t S IFNV32_1a(68 6d 61 64 76 2e 69 63 6f) = 0 hmadv.ico
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
64-bit solution by Rudi Cilibrasi <>, on 2014-Dec-26 believes there are no other solutions of the same or shorter length:
FNV64_1a(37 37 6b 65 70 51 46 51 38 4b 6c) = 0 77kepQFQ8Kl
As reported by Joseph Crail <> on 2026-Jul-05:
There are no other solutions for alphanumeric data sets of length 11 or smaller.As a quick sketch of my method, I shrank the search space for possible solutions by finding all strings of a given length that generate a hash with some number of consecutive suffix of zeroes, giving me a several order of magnitude reduction in possible candidates. I then evaluated all candidates in parallel to find any true solutions.
Joseph Crail kindly provided a formal write-up of my work in regards to the above.
Johann N. Löfflmann, on 2026-Nov-09, proved that there is exactly 1 solution of length 11.
How Johann N. Löfflmann checked their proof:
- Lengths 1..6: exact meet-in-the-middle search (stores all states after the first ceil(n/2) characters and looks up all states computed backwards from the hash 0). No solution for any of the four challenges.
- Lengths 7..11: an exhaustive lattice search. The XOR with a character < 0x80 only changes the lowest 7 bits of the state, which makes the zero-hash condition an exact linear equation with small unknowns. All its solutions in the admissible range are enumerated without pruning, inside a ball that contains the whole range, so the search finds every string of a given length with hash 0. Result: no solution below the published length, and at the published length exactly the published solutions.
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
128-bit solutions by Johann N. Löfflmann on 2026-Nov-09:These are 10 solutions of length 22: FNV128_1a(31 6e 38 5a 49 6c 54 78 7a 6e 4c 56 59 48 6d 4d 4d 41 6a 30 41 57) = 0   1n8ZIlTxznLVYHmMMAj0AW FNV128_1a(35 4b 70 4e 75 44 59 61 72 78 53 51 45 71 7a 66 66 47 5a 4d 71 41) = 0   5KpNuDYarxSQEqzffGZMqA FNV128_1a(44 4b 73 73 33 6a 42 30 62 52 36 4d 57 51 67 52 4c 6d 38 77 32 4b) = 0   DKss3jB0bR6MWQgRLm8w2K FNV128_1a(44 69 30 41 78 45 46 41 7a 56 6a 4e 59 43 42 61 35 72 6c 41 6e 6c) = 0   Di0AxEFAzVjNYCBa5rlAnl FNV128_1a(53 4f 68 47 57 76 44 65 4d 53 73 31 63 78 52 77 4b 49 57 6c 69 52) = 0   SOhGWvDeMSs1cxRwKIWliR FNV128_1a(56 58 55 64 75 46 65 42 41 7a 48 53 45 32 57 36 75 50 5a 58 72 4d) = 0   VXUduFeBAzHSE2W6uPZXrM FNV128_1a(68 7a 6c 57 75 57 6e 37 53 4e 75 34 35 39 32 32 68 4f 47 45 67 53) = 0   hzlWuWn7SNu45922hOGEgS FNV128_1a(6a 41 6c 63 64 57 61 7a 48 39 44 63 56 70 62 4f 38 53 58 64 47 62) = 0   jAlcdWazH9DcVpbO8SXdGb FNV128_1a(70 56 6f 4a 46 4e 53 6a 34 32 55 31 76 48 77 34 61 5a 71 4f 70 57) = 0   pVoJFNSj42U1vHw4aZqOpW FNV128_1a(79 74 64 77 46 60 56 6b 41 53 37 62 56 4e 54 63 73 37 52 56 58 66) = 0   ytdwF`VkAS7bVNTcs7RVXfNOTE: Nine of them use only [0-9A-Za-z]; the last one contains a backtick (0x60), which is part of the alphabet as defined on your page.
According to Johann N. Löfflmann: Each solution was verified independently with the FNV-1a-128 implementation of Jacksum:
prints:jacksum -a fnv-1a_128 -X -q hex:<hex>00000000000000000000000000000000Then using a short arbitrary-precision Python implementation with:offset basis 144066263297769815596495629667062367629 prime 2^88 + 2^8 + 0x3bJohann N. Löfflmann writes:
Is 22 the shortest length? Maybe.A counting argument gives 63^n / 2^128 expected solutions of length n (alphabet of 63 octets).
n = 22: ~11.3 n = 21: ~0.18 n = 20: ~0.003Searches for lengths 20 and 21 found no solution, covering an estimated 99.1 % (n = 20) and 98.2 % (n = 21; 120 randomized rounds over all 3969 two-character prefixes, 124732 of about 127008 expected candidate points) of all candidates that satisfy the linearized equations described below. Under the usual assumption that FNV-1a-128 behaves like a random function, the probability that a shorter solution exists but was missed is about 0.3 % (0.18 * 0.018).
Brute force is infeasible (63^22 ~ 2^131.5), so the search uses lattice reduction:
- Every character is < 0x80, so the XOR only changes the lowest 7 bits of the state. With u_i = (h_{i-1} XOR c_i) mod 128 and r_i = h_i mod 128 = (59 * u_i) mod 128 (59 = FNV prime mod 128), the recurrence can be written exactly as G_i = (G_{i-1} + u_i) * P - r_i (mod 2^128), with G_i = h_i - r_i. The hash is 0 iff G_{n-1} = 0 and the last character equals r_{n-1}.
- For a fixed prefix (3 characters for n = 22), the remaining 18 positions give a modular knapsack with small unknowns 0 <= u_t, r_t <= 127. This is a closest-vector problem in a fixed 36-dimensional lattice; only the target depends on the prefix.
- The lattice is reduced once with exact integer LLL and BKZ-20. Then, for every prefix, Schnorr-Euchner enumeration with pruning ("extreme pruning": several rounds with randomly weighted metrics and re-randomized bases) lists the lattice points near the center of the cube [0,127]^36. Each point is translated back into characters c = s XOR u and accepted only if all of them are in the alphabet and the full 128-bit hash, recomputed with Jacksum, is 0.
- As a check, the same program finds exactly the published results for challenge 67 (the 12 solutions of length 6 for 32-bit FNV-1a, none of length 5) and challenge 68 (77kepQFQ8Kl for 64-bit FNV-1a, none of length 10) when it is run exhaustively, without pruning.
For n = 22, 14 rounds were run (about 3.5 hours on 14 cores). They found 10 of the ~11 expected solutions.
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
NOTE: By alphanumeric ASCII string we mean any arbitrary collection of ASCII digits, UPPER-case letters, and lower-case letters.
|
© 1994-2013
Landon Curt Noll chongo (was here) /\oo/\ $Revision: 8.34 $ $Date: 2026/11/13 20:10:37 $ |