# Ticket #11946(closed enhancement: fixed)

Opened 19 months ago

## Change iteration order for finite field multiplicative_generator()

Reported by: Owned by: jdemeyer was major sage-4.8 user interface GF N/A Keshav Kini Jeroen Demeyer sage-4.8.alpha1

If K is a finite field implemented through PARI (the default if q > 216), 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.

## Change History

### comment:1 Changed 19 months ago by jdemeyer

• Owner changed from AlexGhitza to was
• Component changed from basic arithmetic to user interface

### comment:2 Changed 19 months ago by jdemeyer

• Status changed from new to needs_review

### comment:3 follow-ups: ↓ 4 ↓ 7 Changed 19 months ago by kini

Silly question, but why not just do this?

• ## sage/rings/finite_rings/finite_field_base.pyx

`diff --git a/sage/rings/finite_rings/finite_field_base.pyx b/sage/rings/finite_rings/finite_field_base.pyx`
 a """ 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?

### comment:4 in reply to: ↑ 3 Changed 19 months ago by jdemeyer

• Status changed from needs_review to needs_work

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

### comment:5 Changed 19 months ago by 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?

### comment:6 Changed 19 months ago by jdemeyer

• Status changed from needs_work to needs_review

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

### comment:7 in reply to: ↑ 3 Changed 19 months ago by jdemeyer

• Description modified (diff)
• Summary changed from Finite fields: add "primitive_element" as alias for "multiplicative_generator" to Change iteration order for finite field multiplicative_generator()

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

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

### comment:8 Changed 19 months ago by 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.

### comment:9 Changed 19 months ago by kini

• Status changed from needs_review to positive_review
• Reviewers set to Keshav Kini

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

### comment:10 Changed 19 months ago by jdemeyer

• Status changed from positive_review to closed
• Resolution set to fixed
• Merged in set to sage-4.7.3.alpha1

### comment:11 Changed 19 months ago by jdemeyer

• Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

### comment:12 Changed 19 months ago by jdemeyer

• Merged in changed from sage-4.7.3.alpha1 to sage-4.8.alpha1
• Milestone set to sage-4.8
Note: See TracTickets for help on using tickets.