# Ticket #8373(new defect)

Opened 3 years ago

## finite fields constructed with non-primitive defining polynomial

Reported by: Owned by: rkirov AlexGhitza minor basic arithmetic N/A

### Description

Consider the following code:

```sage: R.<x> = PolynomialRing(GF(2))
sage: K.<a> = GF(16, modulus=x^4+x^3+x^2+x+1)
sage: a^5
1
```

This is all fine mathematically, as long as the user is clear what a is and isn't (it isn't a generator for the multiplicative group of the finite field). So the options as I see them (in increasing difficulty for implementation):

2)Rewrite the help for the GF function to indicate that the function does not return a generator necessarily (like in this specific case).

3)Find an actual generator (that might not be the polynomial x) and return that.

Opinions?

## Change History

### comment:1 in reply to: ↑ description Changed 3 years ago by fwclarke

In your example, a is a generator; it's an algebra generator. In fact a generates K in exactly the same sense in which x generates R. What you're looking for is:

```sage: R.<x> = GF(2)[]
sage: K.<a> = GF(16, modulus=x^4+x^3+x^2+x+1)
sage: K.multiplicative_generator()
a + 1
```

It would be a mistake to insist on having a primitive generator. Of your options:

(1) could slow Sage down unnecessarily, and what should it do if a user wanted to use a non-primitive generator?

(2) yes, if the documentation is confusing, it should be clarified.

(3) I don't quite understand. If you mean ignore a given modulus if it is not primitive, that would be very confusing.

What is needed, for non-prime fields of large characteristic, is a much better way of finding a multiplicative generator:

```sage: p = 65537
sage: K.<a> = GF(p^2)
sage: a.multiplicative_order() == p^2 - 1
False
sage: time K.multiplicative_generator()
CPU times: user 498.03 s, sys: 56.61 s, total: 554.64 s
Wall time: 555.20 s
a + 3
```

What's taking the time here is that the current algorithm, after deciding that a isn't a multiplicative generator, pointlessly computes the multiplicative order of all the non-zero elements in the prime field, before trying a (again), a + 1, a + 2, and succeeding with a + 3.

### comment:2 Changed 3 years ago by rkirov

I guess you are right, it is a generator as an algebra. Somehow I assumed F.<a> gives you 'a' as a multiplicative generator. So it is really a renaming of 'x'(poly var)->'a'. I didn't see the convenient function F.multiplicative_generator.

I checked that Magma has similar behavior.

```> F2 := GF(2);
> FP<x> := PolynomialRing(F2);
> F<z> := ext< F2 | x^4+x^3+x^2+x+1 >;
```

It also seems to have different algorithm for primitive element,

```> PrimitiveElement(F);
z^3 + z + 1
```

In any case I am leaving this open so someone can work on the bug you found.

Note: See TracTickets for help on using tickets.