Construct finite fields with primitive defining polynomial

[rkirov]

Add an argument modulus="primitive" to the finite field generator GF() such that the chosen generator is guaranteed to be a generator of the multiplicative group.

Depends on #16927

CC: @pjbruin

Component: finite rings

Author: Jeroen Demeyer

Branch/Commit: e6c0c58

Reviewer: Peter Bruin

Issue created by migration from https://trac.sagemath.org/ticket/8373

[sagetrac-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]

comment:2

I guess you are right, it is a generator as an algebra. Somehow I assumed F. 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.

[jdemeyer]

comment:3

This is certainly not a bug, but possibly a feature request.

I would propose adding the option modulus="primitive" to solve this ticket.

[sagetrac-fwclarke]

comment:6

Replying to @jdemeyer:

The idea of allowing modulus='primitive' is good. But a problem with the modified description is that the discussion in comments 1 and 2 is now out of context.

[jdemeyer]

comment:7

Replying to @sagetrac-fwclarke:

Replying to @jdemeyer:

The idea of allowing modulus='primitive' is good.

And sufficient for you to consider this issue fixed?

But a problem with the modified description is that the discussion in comments 1 and 2 is now out of context.

Sure, but that's not really a problem, right?

[jdemeyer]

Dependencies: #16927

[jdemeyer]

Author: Jeroen Demeyer

[pjbruin]

Replying to @rkirov:

Also add an argument modulus="pari" (and make it the default) to use PARI's ffinit().

This already exists in PolynomialRing_dense_mod_p.irreducible_element() under the name modulus="adleman-lenstra". It is the default if no Conway polynomial is known and the characteristic is odd.

Some finite field implementations accept a string modulus, but this should be obsolete; FiniteFieldFactory.create_key_and_extra_args() uses the above method to convert a string modulus into an actual polynomial.

[jdemeyer]

comment:12

Thanks for the pointer, I was confused by PolynomialRing_dense_finite_field.irreducible_element

[jdemeyer]

comment:13

Replying to @pjbruin:

Some finite field implementations accept a string modulus, but this should be obsolete

Why should it be obsolete? I think the syntax

k.<a> = GF(p^n, modulus="primitive")

is very good to have. Note that the actual modulus polynomial is computed before the implementation is even considered. So it's not that every finite field implementation needs to be aware of this.

[pjbruin]

comment:15

Replying to @jdemeyer:

Replying to @pjbruin:

Some finite field implementations accept a string modulus, but this should be obsolete

Why should it be obsolete? I think the syntax

k.<a> = GF(p^n, modulus="primitive")

is very good to have.

Yes, it is certainly not this syntax that needs to be made obsolete!

Note that the actual modulus polynomial is computed before the implementation is even considered. So it's not that every finite field implementation needs to be aware of this.

That is what I meant; the individual implementation should never need to consider the case where modulus is a string, it should all be handled by the factory.

[jdemeyer]

Branch: u/jdemeyer/ticket/8373

[jdemeyer]

Commit: 63ec17a

[jdemeyer]

New commits:

8286a4c	Add ffprimroot, fflog, fforder
63ec17a	Allow modulus="primitive" in finite field constructor

[jdemeyer]

comment:18

Replying to @pjbruin:

That is what I meant; the individual implementation should never need to consider the case where modulus is a string, it should all be handled by the factory.

Good, this will be #16930.

[pjbruin]

comment:19

Looks good and passes tests.

[pjbruin]

Reviewer: Peter Bruin

[vbraun]

comment:20

I got this on arando (linux 32-bit):

sage -t --long src/sage/rings/polynomial/polynomial_ring.py
**********************************************************************
File "src/sage/rings/polynomial/polynomial_ring.py", line 2331, in sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_mod_n.irreducible_element
Failed example:
    GF(5)['x'].irreducible_element(32, algorithm="primitive")
Expected:
    x^32 + 4*x^31 + x^30 + 4*x^29 + 4*x^28 + 3*x^27 + 2*x^26 + x^25 + x^24 + x^23 + 4*x^21 + 3*x^20 + x^19 + 4*x^17 + 4*x^16 + 4*x^15 + 4*x^14 + 3*x^13 + x^12 + 3*x^11 + 4*x^10 + x^9 + 4*x^8 + x^7 + 2*x^6 + 4*x^5 + 4*x^4 + x^3 + 3*x^2 + 4*x + 2
Got:
    x^32 + 3*x^31 + x^30 + 4*x^28 + 2*x^27 + 2*x^26 + 2*x^24 + 2*x^23 + 2*x^22 + x^21 + 3*x^20 + 3*x^19 + x^18 + 3*x^17 + 4*x^16 + 2*x^15 + 3*x^12 + 4*x^11 + x^10 + 2*x^8 + 3*x^7 + 2*x^6 + 3*x^5 + x^4 + 4*x^3 + x + 3
**********************************************************************

[sagetrac-git]

Changed commit from 63ec17a to e6c0c58

[sagetrac-git]

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

e6c0c58

Fix for random doctest

[vbraun]

Changed branch from u/jdemeyer/ticket/8373 to e6c0c58