#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) Commit: 861ae1453b54faf5c8f78b213b9fbc91a9c9f6f2
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

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 20 months ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 20 months ago by jdemeyer

  • Branch set to u/jdemeyer/speed_up_finitefield_zeta__

comment:3 Changed 20 months ago by jdemeyer

  • Commit set to e72581d02bbaf1156fed561cbb76becd08ab7164
  • Status changed from new to needs_review

New commits:

e72581dRe-implement multiplicative_generator() and zeta()

comment:4 Changed 20 months ago by git

  • Commit changed from e72581d02bbaf1156fed561cbb76becd08ab7164 to 7701a1ee63de664ffe147668c407941e8b243180

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7701a1eRe-implement multiplicative_generator() and zeta()

comment:5 Changed 20 months ago by jdemeyer

  • Description modified (diff)

comment:6 Changed 20 months ago by vdelecroix

  • 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 20 months ago by jdemeyer

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 20 months ago by git

  • Commit changed from 7701a1ee63de664ffe147668c407941e8b243180 to 35b8fc4c46d98df61a93daa88866e9885c921ada

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

35b8fc4zeta() has no compatibility guarantees

comment:9 Changed 20 months ago by jdemeyer

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 20 months ago by jdemeyer

  • Status changed from needs_info to needs_review

comment:11 Changed 20 months ago by vdelecroix

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 20 months ago by git

  • Commit changed from 35b8fc4c46d98df61a93daa88866e9885c921ada to 861ae1453b54faf5c8f78b213b9fbc91a9c9f6f2

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

861ae14Better doctest

comment:13 Changed 20 months ago by vdelecroix

  • 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 19 months ago by vbraun

  • Branch changed from u/jdemeyer/speed_up_finitefield_zeta__ to 861ae1453b54faf5c8f78b213b9fbc91a9c9f6f2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.