Factorization in iterated extensions of finite fields

[Julian Rüth]

At the moment there is no factorization implemented in iterated extensions of finite fields:

sage: K = GF(2)
sage: R.<x> = K[]
sage: L.<x> = K.extension(x^2 + x + 1)
sage: R.<y> = L[]
sage: M.<y> = L.extension(y^2 + y + x)
sage: R.<T> = M[]
sage: (T^2 + T + x).factor()
NotImplementedError

The reason is that M in the above example is just a quotient of a polynomial ring over L. Here, we implement isomorphisms (for this special case) to a simple extensions of a prime field over which factorization is implemented. We also implement univariate factorization for polynomial quotient rings if an isomorphism to a field which supports such factorization is known.

[git]

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

​ec1b78b	fix typo in any_root()
​af6f451	Merge branch 't/21998/any_root___sometimes_fails_over_finite_fields' into t/21996/factorization_in_iterated_extensions_of_finite_fields
​3a43d57	fix doctests for _isomorphic_ring
​1a3cb94	extend _isomorphic_ring to handle number fields

[git]

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

​ca050d3	Refine quotient ring category to Fields()
​f9e393b	Improve categories of quotient ring morphisms
​80a0e1f	Refine category of quotient rings isomorphic to number fields
​1c9f1c6	Make quotient ring morphisms inherit from the correct category type

[Julian Rüth]

I added some __make_element_class__ around the SetMorphism. They make no difference because SetMorphism is an extension type, but morally they should be there (if it were not an extension type) so that the result inherits the right methods from the category.

[git]

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

​b2dfab4

Do not pass in category explicitly

[git]

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

​725ad0f

Merge branch 'develop' into u/saraedum/factorization_in_iterated_extensions_of_finite_fields

[Jean-Pierre Flori]

I'll have a closer look soon but right now this looks like a good addition. The only thing that I find disturbing is the method name _isomorphic_ring. Maybe it's not descriptive enough?

[Jean-Pierre Flori]

You've got this simple model stuff for function fields.

[git]

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

​87b2f65

Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

[Julian Rüth]

Jens Bauch reported that the factorization does not work here:

K = GF(3)
R.<x> = K[]
L.<x> = K.extension(x^2 + x + 1)
R.<y> = L[]
M.<y> = L.extension(y^2 + y + x)
R.<T> = M[]
(T^2 + T + x).factor()

[git]

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

​0b44d33

Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

[Julian Rüth]

New commits:

​0b44d33

Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

---

New commits:

​0b44d33

Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

[erousseau]

If the fix is OK, then I think it is ready for positive review.

Edouard

---

New commits:

​5608932

Fixed a bug in polynomial factorisation

[Volker Braun]

$ sage -t --long --warn-long 68.9 src/sage/rings/polynomial/polynomial_quotient_ring.py  # 4 doctests failed
Running doctests with ID 2017-06-10-00-08-57-0afdacb4.
Git branch: develop
Using --optional=mpir,python2,sage
Doctesting 1 file.
sage -t --long --warn-long 68.9 src/sage/rings/polynomial/polynomial_quotient_ring.py
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 267, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic
Failed example:
    isinstance(Q.an_element(),Q.element_class)
Expected:
    True
Got:
    False
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 269, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic
Failed example:
    [s for s in dir(Q.category().element_class) if not s.startswith('_')]
Expected:
    ['cartesian_product', 'is_idempotent', 'is_one', 'is_unit', 'lift', 'powers']
Got:
    ['cartesian_product',
     'euclidean_degree',
     'factor',
     'gcd',
     'is_idempotent',
     'is_one',
     'is_unit',
     'lcm',
     'lift',
     'powers',
     'quo_rem',
     'xgcd']
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 281, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic
Failed example:
    first_class == Q.__class__
Expected:
    False
Got:
    True
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 834, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.is_field
Failed example:
    F2.is_field()
Expected:
    Traceback (most recent call last):
    ...
    NotImplementedError
Got:
    False
**********************************************************************
2 items had failures:
   3 of  29 in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic
   1 of  13 in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.is_field
    [410 tests, 4 failures, 2.37 s]
----------------------------------------------------------------------
sage -t --long --warn-long 68.9 src/sage/rings/polynomial/polynomial_quotient_ring.py  # 4 doctests failed
----------------------------------------------------------------------
Total time for all tests: 2.5 seconds
    cpu time: 2.2 seconds
    cumulative wall time: 2.4 seconds

[Jean-Pierre Flori]

New commits:

​9ccb592	Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields
​439b9af	The test suite of quotient refines the category

[Alyson Deines]

Should the following example work with this branch? It does not for me. I get a not implemented error.

All examples in ticket have fields with cardinality a power of 2.

Replying to saraedum:

Jens Bauch reported that the factorization does not work here:

K = GF(3)
R.<x> = K[]
L.<x> = K.extension(x^2 + x + 1)
R.<y> = L[]
M.<y> = L.extension(y^2 + y + x)
R.<T> = M[]
(T^2 + T + x).factor()

[Julian Rüth]

Replying to aly.deines:

Should the following example work with this branch? It does not for me. I get a not implemented error.

All examples in ticket have fields with cardinality a power of 2.

Replying to saraedum:

Jens Bauch reported that the factorization does not work here:

K = GF(3)
R.<x> = K[]
L.<x> = K.extension(x^2 + x + 1)
R.<y> = L[]
M.<y> = L.extension(y^2 + y + x)
R.<T> = M[]
(T^2 + T + x).factor()

That's expected. L is not a field in this example.

[git]

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

​d585fdb

Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields