elements of finite field algebraic closure are not hashable

[vdelecroix]

We have

sage: K = GF(2).algebraic_closure()
sage: a = K.an_element()
sage: hash(a)
Traceback (most recent call last):
...
TypeError: ...

and this prevent resultant computation of bivariate polynomials

sage: R.<x,y> = K[]
sage: x.resultant(y)
Traceback (most recent call last):
...
TypeError: ...

On the way we also provide a straightforward faster powering.

---

Just as a remark, the hash we had in sage-6.8 was completely broken

sage: F = GF(2).algebraic_closure()
sage: z3 = F.gen(3)
sage: z2 = F.gen(2)
sage: hash(z2)
15616093818140894
sage: hash(z3+z2-z3)
5386247743066594243

But thanks to #19016 the error now shows up!

[vdelecroix]

Here is a naive implementation. We need to do some kind of canonicalization to get the hash value... hence it is necessarily slow. There might be some faster option if we have more compatibility with the multiplicative generators.

[vdelecroix]

New commits:

​3700aec	Trac 19956: much faster __pow__
​4f4f231	Trac 19956: implement __hash__

[jdemeyer]

It would already be slightly more efficient to remove the branch and double hash and do something like

return hash(x) + (F.degree() - 1) * 1009

[vdelecroix]

Replying to jdemeyer:

It would already be slightly more efficient to remove the branch and double hash and do something like

return hash(x) + (F.degree() - 1) * 1009

True for efficiency. But there will be collisions sooner. The reason is that map(hash, GF(q)) is [0, 1, ..., q-1]. Maybe it was a bad choice for GF(q)? What about something like

return (hash(x) + deg * p1) ^ ((deg - 1) * p2)

I am not sure about the optimal size of p1 and p2... But you are right anyway, I should get rid of the branch!

[jdemeyer]

Replying to vdelecroix:

return (hash(x) + deg * p1) ^ ((deg - 1) * p2)

I don't see why that would be better than my proposal. It is more complicated, but has the same inputs...

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3ef01a3

Trac 19956: slightly better hash

[vdelecroix]

I followed your suggestion but with a slightly larger value for 1009.

[jdemeyer]

Just use hash(x) + 1500007*(F.degree() - 1) by itself, no need for double hashing.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e130a30

Trac 19956: remove a useless hash

[jdemeyer]

How does this interact with #17569? If finite fields will now embed by default in the algebraic closure, the hashes should be preserved.

[vdelecroix]

Replying to jdemeyer:

How does this interact with #17569?

No interaction as far as I can see.

If finite fields will now embed by default in the algebraic closure, the hashes should be preserved.

True. But it is disjoint from #17569, isn't it? Even without this patch hashes are incompatible by restriction to finite fields (except the prime field). It might be tricky to provide a coherent hash that would depend on the embedding... a (far from optimal) solution for finite field could be

def __hash__(self):
    cf = self._parent.coerce_embedding()
    if cf is not None:
        return hash(cf(self))
    else:
        ... old code ...

What do you think? But I would consider this as disjoint from this ticket.

[saraedum]

Replying to jdemeyer:

If finite fields will now embed by default in the algebraic closure, the hashes should be preserved.

I am not sure that this really is a good idea: ​https://wiki.sagemath.org/EqualityCoercion In the long run we might have to move away from our "mathematical" implementation of == but this is not the focus of this ticket. The changes propose here are a clear improvement of the current situation and seem perfectly fine to me.

[vdelecroix]

Thanks for having a look! As a reviewer you should always

• check the milestone
• put your name in the "Reviewers" field

(I did it here)