Speed up FiniteField.zeta()

[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.

[jdemeyer]

New commits:

​e72581d

Re-implement multiplicative_generator() and zeta()

[git]

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

​7701a1e

Re-implement multiplicative_generator() and zeta()

[vdelecroix]

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?

[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?

[git]

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

​35b8fc4

zeta() has no compatibility guarantees

[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.

[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.

[git]

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

​861ae14

Better doctest