Opened 6 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:  sage7.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: 
Description (last modified by )
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 sage6.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+z2z3) 5386247743066594243
But thanks to #19016 the error now shows up!
Change History (16)
comment:1 Changed 6 years ago by
 Cc pbruin added
 Description modified (diff)
comment:2 Changed 6 years ago by
 Cc jpflori added
comment:3 Changed 6 years ago by
 Branch set to u/vdelecroix/19956
 Commit set to 4f4f231e4605f01f029fefd1889359df7fe88262
 Status changed from new to needs_review
comment:4 Changed 6 years ago by
 Description modified (diff)
comment:5 followup: ↓ 6 Changed 6 years ago by
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 ; followup: ↓ 7 Changed 6 years ago by
Replying to jdemeyer:
It would already be slightly more efficient to remove the branch and double
hash
and do something likereturn 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, ..., q1]
. 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 6 years ago by
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 6 years ago by
 Commit changed from 4f4f231e4605f01f029fefd1889359df7fe88262 to 3ef01a3cc01c688ac826851a94b7f8f96c24e146
Branch pushed to git repo; I updated commit sha1. New commits:
3ef01a3  Trac 19956: slightly better hash

comment:9 Changed 6 years ago by
I followed your suggestion but with a slightly larger value for 1009
.
comment:10 Changed 6 years ago by
Just use hash(x) + 1500007*(F.degree()  1)
by itself, no need for double hashing which only slows things down.
comment:11 Changed 6 years ago by
 Commit changed from 3ef01a3cc01c688ac826851a94b7f8f96c24e146 to e130a3046fd99adaf92725605d9675eac0c5c0a2
Branch pushed to git repo; I updated commit sha1. New commits:
e130a30  Trac 19956: remove a useless hash

comment:12 followups: ↓ 13 ↓ 14 Changed 6 years ago by
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 6 years ago by
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
 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
 Milestone changed from sage7.1 to sage7.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
 Branch changed from u/vdelecroix/19956 to e130a3046fd99adaf92725605d9675eac0c5c0a2
 Resolution set to fixed
 Status changed from positive_review to closed
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.