Opened 3 years ago
Closed 3 years ago
#25203 closed defect (fixed)
Speed up FiniteField.zeta()
Reported by: | jdemeyer | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.3 |
Component: | finite rings | Keywords: | |
Cc: | Merged in: | ||
Authors: | Jeroen Demeyer | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | 861ae14 (Commits, GitHub, GitLab) | Commit: | 861ae1453b54faf5c8f78b213b9fbc91a9c9f6f2 |
Dependencies: | Stopgaps: |
Description (last modified by )
Something like this takes forever:
sage: GF(2^1000).zeta(3)
This is because k.zeta()
is implemented by taking the power of a multiplicative generator, but computing a multiplicative generator can take a very long time (it requires factoring q-1
).
Instead, we implement a new function _element_of_factored_order
and implement both zeta
and multiplicative_generator
using that.
Change History (14)
comment:1 Changed 3 years ago by
- Description modified (diff)
comment:2 Changed 3 years ago by
- Branch set to u/jdemeyer/speed_up_finitefield_zeta__
comment:3 Changed 3 years ago by
- Commit set to e72581d02bbaf1156fed561cbb76becd08ab7164
- Status changed from new to needs_review
comment:4 Changed 3 years ago by
- Commit changed from e72581d02bbaf1156fed561cbb76becd08ab7164 to 7701a1ee63de664ffe147668c407941e8b243180
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
7701a1e | Re-implement multiplicative_generator() and zeta()
|
comment:5 Changed 3 years ago by
- Description modified (diff)
comment:6 Changed 3 years ago by
- Status changed from needs_review to needs_info
There is no clear specifications with R.zeta(n)
for a general ring R
but I would expect R.zeta(m*n) ** m == R.zeta(n)
to be True
. This might not be the case anymore with your implementation that returns "some" root of unity. I do think that your version is more useful than the previous one. But perhaps not appropriate for the name "zeta". What do you think?
comment:7 Changed 3 years ago by
I am wondering if we can somehow compute zeta(n)
in a compatible way. Suppose that somebody first asks for zeta(n)
and then zeta(n * m)
, can we enforce compatibility? Or do we need discrete logs for that?
comment:8 Changed 3 years ago by
- Commit changed from 7701a1ee63de664ffe147668c407941e8b243180 to 35b8fc4c46d98df61a93daa88866e9885c921ada
Branch pushed to git repo; I updated commit sha1. New commits:
35b8fc4 | zeta() has no compatibility guarantees
|
comment:9 Changed 3 years ago by
I just talked to Luca and we both think that it's hard to enforce compatibility for large finite fields. So I suggest that we don't do this. I added a warning to the documentation to explain this.
comment:10 Changed 3 years ago by
- Status changed from needs_info to needs_review
comment:11 Changed 3 years ago by
The doctest
sage: k.<a> = GF(2^2000) sage: p = 8877945148742945001146041439025147034098690503591013177336356694416517527310181938001 sage: z = k.zeta(p) sage: z ^ p 1
is not wonderful as it might well be that z = 1
. Sadly z.multiplicative_order()
does not terminate.
comment:12 Changed 3 years ago by
- Commit changed from 35b8fc4c46d98df61a93daa88866e9885c921ada to 861ae1453b54faf5c8f78b213b9fbc91a9c9f6f2
Branch pushed to git repo; I updated commit sha1. New commits:
861ae14 | Better doctest
|
comment:13 Changed 3 years ago by
- Milestone changed from sage-8.2 to sage-8.3
- Reviewers set to Vincent Delecroix
- Status changed from needs_review to positive_review
comment:14 Changed 3 years ago by
- Branch changed from u/jdemeyer/speed_up_finitefield_zeta__ to 861ae1453b54faf5c8f78b213b9fbc91a9c9f6f2
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
Re-implement multiplicative_generator() and zeta()