[issue34751] Hash collisions for tuples

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

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.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue34751>
_______________________________________