Change iteration order for finite field multiplicative_generator()

[jdemeyer]

If K is a finite field implemented through PARI (the default if q > 2¹⁶), then we try to find a multiplicative generator by first trying all elements of GF(p) (the prime field). This means the following will never finish in practice:

sage: p = next_prime(10^20)
sage: K.<a> = GF(p^2)
sage: K.multiplicative_generator()

Also, a generator for the multiplicative group is often called a "primitive element" (or primitive root). We should add a method primitive_element which returns the multiplicative generator.

[kini]

Silly question, but why not just do this?

sage/rings/finite_rings/finite_field_base.pyx

@@ -87 +87 @@
         """
         from sage.categories.finite_fields import FiniteFields
         Field.__init__(self, base, names, normalize, category=FiniteFields())
+        self.primitive_element = self.multiplicative_generator
 
     def __repr__(self):
         """

The docstring you wrote is basically the same as the docstring for multiplicative_generator, so eliminating it will avoid double-maintenance pitfalls. And this way you don't get one more call frame on the stack when using the function. ... right?

And something else a bit bizarre is happening. With the diff I pasted above, the second test produces the output a, which matches the last doctest in the docstring of the multiplicative_generator method. But your patch gives a + 5, even though it's just calling multiplicative_generator, and also produces a large number of messages in stderr (which are therefore not noticed by sage -t); they all read as follows:

  ***   Warning: Mod(a,b)^n with n >> b : wasteful.

What's going on?

[jdemeyer]

Replying to kini:

And something else a bit bizarre is happening. With the diff I pasted above, the second test produces the output a, which matches the last doctest in the docstring of the multiplicative_generator method. But your patch gives a + 5, even though it's just calling multiplicative_generator

This is because of different random seeds. For large finite fields, it takes a random irreducible polynomial to generate a finite field. So one GF(19^32) is not the same as a different GF(19^32).

[kini]

Aha, I see. And the random seed is set to a known value at the beginning of a doctest session, which is why you can still have a doctest with a known output. Thanks! Any comments about other things I said? What needs work now?

[jdemeyer]

I made the obvious change primitive_element = multiplicative_generator and changed the docstring accordingly.

[jdemeyer]

Replying to kini:

  ***   Warning: Mod(a,b)^n with n >> b : wasteful.

Nice catch, see new description. New patch fixes this.

[kini]

While attempting to see what .. WARNING:: is supposed to do by looking at how it renders in the reference manual, I found to my surprise that this docstring does not even appear in the reference manual! Maybe we should make our autodoc a bit more automatic...?

I'll doctest the patch on sage.math.

[kini]

All tests pass and the patch looks good to me. Positive review.

[jdemeyer]

Milestone sage-4.7.3 deleted