Author tim.peters
Recipients eric.smith, jdemeyer, mark.dickinson, rhettinger, sir-sigurd, tim.peters
Date 2018-09-24.21:37:16
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1537825036.07.0.545547206417.issue34751@psf.upfronthosting.co.za>
In-reply-to
Content
Jeroen, I understood the part about -2 from your initial report ;-)  That's why the last code I posted didn't use -2 at all (neither -1, which hashes to -2).  None of the very many colliding tuples contained -2 in any form.  For example, these 8 tuples all have the same hash now:

(-4,  -4,  -4,  40)    (-4,  -4,  4, -48)
( 4,   4,  -4,  40)    ( 4,   4,  4, -48)
(-4,  28, -28, -48)    (-4,  28, 28,  40)
( 4, -28, -28, -48)    ( 4, -28, 28,  40)

Your last example (with (3, -2) and (-3, 0)) also implicitly relies on that:

    j is even implies (j ^ -3) == -(j ^ 3)

There are apparently piles of similar identities :-(

I appreciate that

    a*M + C = b*M + C (mod N)

implies

    a = b (mod N)

when M is coprime to N, and also that the theory of linear combinations modulo 2**K is far better known than the well-hidden theory FNV developed.
History
Date User Action Args
2018-09-24 21:37:16tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, eric.smith, jdemeyer, sir-sigurd
2018-09-24 21:37:16tim.peterssetmessageid: <1537825036.07.0.545547206417.issue34751@psf.upfronthosting.co.za>
2018-09-24 21:37:16tim.peterslinkissue34751 messages
2018-09-24 21:37:16tim.peterscreate