hash of polynomials is very bad

[vdelecroix]

A lot of conflicts:

sage: S.<t> = QQ[]
sage: from itertools import product
sage: values = [S(t) for t in product((0,1/2,1,2), repeat=5)]
sage: len(set(map(hash,values)))
565
sage: len(values)
1024

Though hashing in this situation is delicate since we want to preserve the compatibility with:

• sparse polynomials
• multivariate polynomials

[kedlaya]

I don't have product in my version of Sage, but by replacing that line with

sage: values = [S(list(t)) for t in cartesian_product([[0,1/2,1,2],] * 5)]

I was able to reproduce the issue. I need a fix for this in order to deal with hashes of ideals; see #21297.

[vdelecroix]

Right product comes from the itertools module.

[kedlaya]

To make this more specific, in case this helps to chase this down:

sage: R.<t> = QQ[]
sage: u = 2*t^3 + t^2; v = t^3 + 2*t + 1
sage: hash(u), hash(v)
(29698519856292282, 29698519856292282)

The key bit of code is in the function hash_c (omitting some comments):

for i from 0<= i <= self.degree():
    if i == 1:
        # we delay the hashing until now to not waste it on a constant poly
        var_name_hash = hash(self._parent._names[0])
    c_hash = hash(self[i])
    if c_hash != 0:
        if i == 0:
            result += c_hash
        else:
            # Hash (self[i], generator, i) as a tuple according to the algorithm.
            result_mon = c_hash
            result_mon = (1000003 * result_mon) ^ var_name_hash
            result_mon = (1000003 * result_mon) ^ i
            result += result_mon

which seems just not to work at all. Probably a complete rethink is in order here.

[vdelecroix]

(related: I did something for nf elements at #23402)

[vdelecroix]

Once #23402 is positively reviewed I will port the corresponding code here

[kedlaya]

Let's make #23402 a dependency then.

[vdelecroix]

Actually what I did in #23402 has to be rethought since it does not apply to sparse polynomials... the hashing function needs to involve the degree of the monomials in some way.

[jdemeyer]

So, is #23402 then a dependency or not?

[vdelecroix]

Let us remove the dependency as there is no coercion/hash compatibility involved between polynomial rings and number fields.