search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.37k stars 466 forks source link

Finite field lattices via Conway polynomials #8335

Closed roed314 closed 11 years ago

roed314 commented 14 years ago

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:

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 commented 14 years ago
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 commented 14 years ago

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 commented 14 years ago

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

roed314 commented 14 years ago
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 commented 14 years ago

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
11d1fc49-71a1-44e1-869f-76be013245a0 commented 14 years ago
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
roed314 commented 13 years ago

Attachment: 8335_pseudo_conway.patch.gz

Apply first

roed314 commented 13 years ago
comment:8

To work against 4.7, apply 8335_pseudo_conway.patch then 8335_finite_field_coerce_vs_47.patch.

roed314 commented 13 years ago

Apply second

roed314 commented 13 years ago

Attachment: 8335_finite_field_coerce.patch.gz

Against 4.7 for patchbot

roed314 commented 13 years ago
comment:9

Attachment: 8335_finite_field_coerce_vs_47.patch.gz

To work against 4.7, apply 8335_pseudo_conway.patch then 8335_finite_field_coerce_vs_47.patch.

roed314 commented 13 years ago
comment:10

Apply 8335_pseudo_conway.patch, 8335_finite_field_coerce_vs_47.patch

defeo commented 13 years ago
comment:11

I still get the following failures on 4.7.1.alpha4 with 8335_pseudo_conway.patch and 8335_finite_field_coerce_vs_47.patch applied:

    sage -t -long devel/sage/sage/matrix/matrix2.pyx # 2 doctests failed
    sage -t -long devel/sage/sage/rings/finite_rings/constructor.py # 1 doctests failed
defeo commented 13 years ago
comment:12

I also get 7 warnings when building the docs. These all seem to be missing blank lines and unmatched backquoutes in sage/rings/finite_rings/constructor.py

jpflori commented 11 years ago

Attachment: trac_8335-pseudo_conway-5.7.b3.patch.gz

Patch for PCP; rebased on top of 5.7.beta3.

jpflori commented 11 years ago

Attachment: trac_8335-finite_field_coerce-5.7.b3.patch.gz

Patch for coercion; rebased on top of 5.7.beta3.

jpflori commented 11 years ago

Patch for doc fixes; rebased on top of 5.7.beta3.

jpflori commented 11 years ago
comment:14

Attachment: trac_8335-doc-5.7.beta3.patch.gz

These patches were quite old and things have moved around since they were written. As a consequence, part of the old patches now apply to different files, that is the case of the NTL GF2E implementation which has been split in a Python and a Cython file.

Some pseudo Conway polys changed so that two doctests now fail (not corrected in the patches cause I did not take the time to think about it, feel free to do it). As these pseudo Conway polynomials are not unique, I'm not sure if the procedure to generate them is deterministic or to which point randomness comes into play and if the failing doctests are just due to some routine called during the generation which may give a different result since the patches were originally written.

Not really sure how to cast restriction on the is_square and squarefree_decomposition methods, nor what I've changed makes sense, I've come up with this quickly, feel free to correct it. The basic problem was that now Sage supports function fields where we have no p-th roots and that raised an AttributeError when calling is_square which called squarefree_decomposition in some doctests.

The doc now builds ok and looks nice (although I did not have LaTeX on my computer), but may need some revamping. Nonetheless it would be great to get this in quickly.

jpflori commented 11 years ago

Description changed:

--- 
+++ 
@@ -15,4 +15,10 @@

 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.
+
+__APPLY__
+
+*[attachment: trac_8335-pseudo_conway-5.7.b3.patch](https://github.com/sagemath/sage-prod/files/10648212/trac_8335-pseudo_conway-5.7.b3.patch.gz)
+*[attachment: trac_8335-finite_field_coerce-5.7.b3.patch](https://github.com/sagemath/sage-prod/files/10648213/trac_8335-finite_field_coerce-5.7.b3.patch.gz)
+*[attachment: trac_8335-doc-5.7.b3.patch](https://github.com/sagemath/sage-prod/files/10648215/trac_8335-doc-5.7.b3.patch.gz)
jpflori commented 11 years ago
comment:15

I've just launche "make ptestlong" (only tested the ring dir before) and saw some errors on screen, will report later.

jpflori commented 11 years ago

Fixes

jpflori commented 11 years ago
comment:16

Attachment: trac_8335-doc-5.7.b3.patch.gz

There were problem doing coercion because Sage now tried to define algebraic extension of Integers(1) and failed on ArithmeticError when trying 0^0, or depth of recursion if that was changed to return 1.

I've added an extension method to the IntegerModring_generic class to handle separatly this ring.

Did not check everything is fine though.

jpflori commented 11 years ago

Description changed:

--- 
+++ 
@@ -20,5 +20,7 @@
 __APPLY__

 *[attachment: trac_8335-pseudo_conway-5.7.b3.patch](https://github.com/sagemath/sage-prod/files/10648212/trac_8335-pseudo_conway-5.7.b3.patch.gz)
+
 *[attachment: trac_8335-finite_field_coerce-5.7.b3.patch](https://github.com/sagemath/sage-prod/files/10648213/trac_8335-finite_field_coerce-5.7.b3.patch.gz)
+
 *[attachment: trac_8335-doc-5.7.b3.patch](https://github.com/sagemath/sage-prod/files/10648215/trac_8335-doc-5.7.b3.patch.gz)
9d1e1357-99b4-475c-9e69-e66344a5dd57 commented 11 years ago
comment:18

I went looking through some papers by Heath and Loehr and it appears that the output of an algorithm to compute a pseudo-conway polynomial will most likely not be deterministic unless f.any_root() is deterministic for polynomials in finite fields (something I'm not entirely sure about).

In this case, I'm not sure what to do about the tests, but I agree that it would be nice to move this patch along - but I'm not qualified to review it.

jpflori commented 11 years ago
comment:19

We have some Sage meeting near Paris in France today, with a tutorial about ... finite fields. We'll try to polish this one up there.

roed314 commented 11 years ago
comment:20

Fantastic! I've been meaning to get back to this but have been busy with other things. Let me know what comes up and I can review your changes if necessary.

jpflori commented 11 years ago
comment:21

That got broken again in 5.7.b4 by #13064.

jpflori commented 11 years ago
comment:22

Rebased on top of 5.7.b4.

jpflori commented 11 years ago
comment:23

With the last set of patches, it passes make ptestlong except:

jpflori commented 11 years ago
comment:24

I've fixed some additional stuff and have new two concerns (in addition to the matrix2 stuff I've not dealt with):

jpflori commented 11 years ago
comment:25

The problem with matrix2.pyx is with multiplying a matrix with coefficients living in Q with a matrix with elements in an extension field. It seems the coercion model tries to put the second one in the prime subfield and fails with the "not in prime field" TypeError.

jpflori commented 11 years ago
comment:26

This is caused by the "fix" I proposed before to return IntegerMod(1) for algebraic extension of IntegerMod(1), because now I feel a common parent is chosen as IntegerMod(1), but this is a prime field and the element from the extension field "cannot" be cast there.

A proper solution could be to investigate the infinite loop we get when the ArithmeticError is replaced with returning a unit when computing 0^0. Another solution might be to forbid extension of IntegerMod(1) so that we don't get crappy common parents.

jpflori commented 11 years ago
comment:27

I think I got the infinite loop.

During the initialization of the quotient ring, when trying to create the "one" element from the quotient ring of integer mod 1 quotiented by something, it tries to compute a remainder in polynomial_quotient_ring_element.py: "polynomial %= f" around line 137 but the mod operation is not defined for the Polynomial_ring_dense class, so this raises an AttributeError and falls back to the fallback implementation which tries to compute 0^0 which now tries to create 1 which is looked up for at the position 1 of a table of precomputed value of length the modulus+1 = 1 which is surely non sense, fails to create a IntegerrMod_int and raises a TypeError which gets caught in polynomial_quotient_ring.py around line 430 and loops...

jpflori commented 11 years ago
comment:28

And of course if we return 0 (== 1) for 0^0, then the generic quo_rem loops forever as we are computing 0 % 0 and the degree will never fall...

jpflori commented 11 years ago

Dependencies: #13894

jpflori commented 11 years ago
comment:30

Forget my rant about something becoming conway and having potential performance issues. It only occurs if we have the conway polynomial precomputed, so no worries.

I've removed the code calling factor_cunningham unconditionally (or rather, not through an option as in finite_rings/element_base.pyx). At some point this should get automatically triggered when cunningham tables are included (#7240, #12133) and integer factorization is improved (#12125, #12117), so calling factor_cunningham directly won't be that useful anyway.

jpflori commented 11 years ago
comment:31

The doctests which changed were surely not caused by different randomness but because some checks in compute_pseudo_conway_polynomial were wrong, e.g. the results for next_prime(10000)**11 was x^11 + x + 7 whose root is not of order p^11-1 but p^11-1/2

jpflori commented 11 years ago

Attachment: trac_8335-finite_field_coerce-5.7.b4.patch.gz

jpflori commented 11 years ago

Work Issues: coercion madness

jpflori commented 11 years ago

Description changed:

--- 
+++ 
@@ -19,8 +19,8 @@

 __APPLY__

-*[attachment: trac_8335-pseudo_conway-5.7.b3.patch](https://github.com/sagemath/sage-prod/files/10648212/trac_8335-pseudo_conway-5.7.b3.patch.gz)
+*[attachment: trac_8335-pseudo_conway-5.7.b4.patch](https://github.com/sagemath/sage-prod/files/10648217/trac_8335-pseudo_conway-5.7.b4.patch.gz)

-*[attachment: trac_8335-finite_field_coerce-5.7.b3.patch](https://github.com/sagemath/sage-prod/files/10648213/trac_8335-finite_field_coerce-5.7.b3.patch.gz)
+*[attachment: trac_8335-finite_field_coerce-5.7.b4.patch](https://github.com/sagemath/sage-prod/files/10648216/trac_8335-finite_field_coerce-5.7.b4.patch.gz)

-*[attachment: trac_8335-doc-5.7.b3.patch](https://github.com/sagemath/sage-prod/files/10648215/trac_8335-doc-5.7.b3.patch.gz)
+*[attachment: trac_8335-doc-5.7.b4.patch](https://github.com/sagemath/sage-prod/files/10648218/trac_8335-doc-5.7.b4.patch.gz)
jpflori commented 11 years ago

Attachment: trac_8335-pseudo_conway-5.7.b4.patch.gz

jpflori commented 11 years ago

Attachment: trac_8335-doc-5.7.b4.patch.gz

jpflori commented 11 years ago

Attachment: trac_8335-pseudo_conway-5.8.b0.patch.gz

jpflori commented 11 years ago

Attachment: trac_8335-finite_field_coerce-5.8.b0.patch.gz

jpflori commented 11 years ago

Changed work issues from coercion madness to none

jpflori commented 11 years ago
comment:33

The patches should be quite ok now. This needs 5.8.beta0, or at least > 5.7.beta4. I've made quite a bit of changes to all the coercion stuff, so that definitely needs review. With a minimal set of changes to sources files you can now create algebraic extensions of the Integers(1) and let it be considered as a quotient of a univariate poly ring, etc. and everything that came up when I was trying to rebase the patches. In particular, now the modulus var of an AlgebraicExtensionFunctor is always a polynomial, but I've added an additional optional field named conway to encode the fact we're dealing with pseudo-conway extensions of ff.

Please test, rant, whatever!

jpflori commented 11 years ago

Description changed:

--- 
+++ 
@@ -19,8 +19,8 @@

 __APPLY__

-*[attachment: trac_8335-pseudo_conway-5.7.b4.patch](https://github.com/sagemath/sage-prod/files/10648217/trac_8335-pseudo_conway-5.7.b4.patch.gz)
+*[attachment: trac_8335-pseudo_conway-5.8.b0.patch](https://github.com/sagemath/sage-prod/files/10648219/trac_8335-pseudo_conway-5.8.b0.patch.gz)

-*[attachment: trac_8335-finite_field_coerce-5.7.b4.patch](https://github.com/sagemath/sage-prod/files/10648216/trac_8335-finite_field_coerce-5.7.b4.patch.gz)
+*[attachment: trac_8335-finite_field_coerce-5.8.b0.patch](https://github.com/sagemath/sage-prod/files/10648220/trac_8335-finite_field_coerce-5.8.b0.patch.gz)

-*[attachment: trac_8335-doc-5.7.b4.patch](https://github.com/sagemath/sage-prod/files/10648218/trac_8335-doc-5.7.b4.patch.gz)
+*[attachment: trac_8335-fixes-5.8.b0.patch](https://github.com/sagemath/sage-prod/files/10648222/trac_8335-fixes-5.8.b0.patch.gz)
jpflori commented 11 years ago
comment:34

This passes "make ptestlong" on a usual x86_64 ubuntu 12.04.1.

roed314 commented 11 years ago
comment:35

Awesome! I will take a look this weekend.

jpflori commented 11 years ago
comment:36

Attachment: trac_8335-fixes-5.8.b0.2.patch.gz

Previous version was not qrefreshed...