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: | 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: |
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 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 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 follow-up: ↓ 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 ; follow-up: ↓ 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, ..., 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 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.
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 follow-ups: ↓ 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 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
- 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.