Finite field lattices via Conway polynomials

[roed314]

Implements coercion within lattices of finite fields lying above the same prime when implemented with Conway polynomials.

sage: k = GF(9, conway=True, prefix='z')
sage: l = GF(27, conway=True, prefix='z')
sage: x = k.gen() + l.gen(); x
z6^5 + 2*z6^4 + 2*z6^3 + z6^2 + 2*z6 + 1
sage: x.parent()
Finite Field in z6 of size 3^6

When using the conway and prefix parameters, one does not need to specify an explicit variable name; if no variable name is given, it is constructed from the prefix and the degree (as in the above code snippet).

In the future, the functionality of this ticket will be incorporated into that for algebraic closures of finite fields. It will then be possible to construct compatible systems of finite fields outside the range of the Conway polynomial database using the pseudo-Conway polynomials from #14958: polynomials that satisfy all of the algebraic constraints on Conway polynomials without the lexicographic constraint that imposes uniqueness.

Apply:

• attachment: trac_8335-finite_field_coerce-5.11.b3-14888.patch
• attachment: trac_8335-no_pseudo.patch

Depends on #14958
Depends on #12142

CC: @defeo @rbeezer @sagetrac-hds @simon-king-jena @zimmermann6 @xcaruso @pjbruin @sagetrac-mraum @fredstro @sagetrac-JCooley @loefflerd @sagetrac-dfesti

Component: algebra

Keywords: days49 sd51

Author: David Roe, Jean-Pierre Flori, Peter Bruin

Reviewer: Jean-Pierre Flori, Luca De Feo

Merged: sage-5.13.beta1

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

[roed314]

comment:2

Part of a series:

8218 -> 8332 -> 7880 -> 7883 -> 8333 -> 8334 -> 8335

I tried to make each of these mostly self contained, with doctests passing after every ticket, but I didn't entirely succeed. If you're reviewing one of these tickets, applying later tickets will hopefully fix doctest failures that you're seeing.

[roed314]

Description changed:

--- 
+++ 
@@ -14,3 +14,5 @@
 Finite fields no longer require an explicit variable name (though they still accept one).  If a variable name is given, then outside the range of the Conway polynomial database a random or sparse polynomial is used for speed reasons; if no variable name is given then either a Conway polynomial or pseudo-Conway polynomial is used.
 
 Also adds methods `any_root` and `squarefree_decomposition` to polynomials over finite fields.
+
+Depends on 8218, 8332, 7880, 7883, 8333, 8334

[roed314]

Includes everything in 8218, 8332, 7880, 7883, 8333, 8334 and 8335 except the 8218 bundle, which you must apply first.

[roed314]

comment:4

Attachment: finite_field_coerce_ALL.patch.gz

For convenience, I added a giant patch which includes all the changes except the bundle at 8218 (which we want to leave as a bundle in order to preserve file history).

[JohnCremona]

Description changed:

--- 
+++ 
@@ -15,4 +15,4 @@
 
 Also adds methods `any_root` and `squarefree_decomposition` to polynomials over finite fields.
 
-Depends on 8218, 8332, 7880, 7883, 8333, 8334
+Depends on #8218, #8332, #7880, #7883, #8333, #8334

[loefflerd]

comment:6

This doesn't apply cleanly: the patch 8335_pseudo_conway.patch seems to conflict with something. FWIW, I am using 4.4.alpha0 with qseries

trac_8446.patch
trac_8446_microfix.patch
trac_8722.patch
7883_ideals.patch
8333_parent_init.patch
8333_finite_fields_to_new_coercion.patch
7585_9_1_frac_and_coerce_updates.patch
8334_residue_fields-rebased_for_8446.patch
7585_12_1_fixes.patch
8335_pseudo_conway.patch