Opened 3 years ago
Closed 3 years ago
#25203 closed defect (fixed)
Speed up FiniteField.zeta()
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage8.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 q1
).
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  Reimplement 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 sage8.2 to sage8.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:
Reimplement multiplicative_generator() and zeta()