Opened 7 years ago

Closed 6 years ago

#19956 closed defect (fixed)

elements of finite field algebraic closure are not hashable

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-7.3
Component: finite rings Keywords:
Cc: pbruin, jpflori Merged in:
Authors: Vincent Delecroix Reviewers: Julian Rüth
Report Upstream: N/A Work issues:
Branch: e130a30 (Commits, GitHub, GitLab) Commit: e130a3046fd99adaf92725605d9675eac0c5c0a2
Dependencies: Stopgaps:

Status badges

Description (last modified by 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!

Change History (16)

comment:1 Changed 7 years ago by vdelecroix

  • Cc pbruin added
  • Description modified (diff)

comment:2 Changed 7 years ago by vdelecroix

  • Authors set to u/vdelecroix/19956
  • Cc jpflori added

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.

comment:3 Changed 7 years ago by vdelecroix

  • Authors changed from u/vdelecroix/19956 to Vincent Delecroix
  • Branch set to u/vdelecroix/19956
  • Commit set to 4f4f231e4605f01f029fefd1889359df7fe88262
  • Status changed from new to needs_review

New commits:

3700aecTrac 19956: much faster __pow__
4f4f231Trac 19956: implement __hash__

comment:4 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:5 follow-up: Changed 7 years ago by 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

comment:6 in reply to: ↑ 5 ; follow-up: Changed 7 years ago by 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!

comment:7 in reply to: ↑ 6 Changed 7 years ago by 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...

comment:8 Changed 7 years ago by git

  • Commit changed from 4f4f231e4605f01f029fefd1889359df7fe88262 to 3ef01a3cc01c688ac826851a94b7f8f96c24e146

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

3ef01a3Trac 19956: slightly better hash

comment:9 Changed 7 years ago by vdelecroix

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

comment:10 Changed 7 years ago by jdemeyer

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

Last edited 7 years ago by jdemeyer (previous) (diff)

comment:11 Changed 7 years ago by git

  • Commit changed from 3ef01a3cc01c688ac826851a94b7f8f96c24e146 to e130a3046fd99adaf92725605d9675eac0c5c0a2

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

e130a30Trac 19956: remove a useless hash

comment:12 follow-ups: Changed 7 years ago by jdemeyer

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

comment:13 in reply to: ↑ 12 Changed 7 years ago by 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.

comment:14 in reply to: ↑ 12 Changed 6 years ago by saraedum

  • Status changed from needs_review to positive_review

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.

comment:15 Changed 6 years ago by vdelecroix

  • Milestone changed from sage-7.1 to sage-7.3
  • Reviewers set to Julian Rüth

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)

comment:16 Changed 6 years ago by vbraun

  • Branch changed from u/vdelecroix/19956 to e130a3046fd99adaf92725605d9675eac0c5c0a2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.