finite fields constructed with non-primitive defining polynomial

[rkirov]

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

1)GF already checks modulus for irreducibility, just add check for modulus.is_primitive().

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?

[fwclarke]

Replying to rkirov:

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.

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