Opened 6 years ago

Closed 5 years ago

#21996 closed enhancement (fixed)

Factorization in iterated extensions of finite fields

Reported by: Julian Rüth Owned by:
Priority: major Milestone: sage-7.5
Component: finite rings Keywords: factorization, finite field, sd86.5, sd87
Cc: Jean-Pierre Flori Merged in:
Authors: Julian Rüth, Hanson Smith, Edouard Rousseau Reviewers: Hanson Smith, Edouard Rousseau, Aly Deines
Report Upstream: N/A Work issues:
Branch: d585fdb (Commits, GitHub, GitLab) Commit: d585fdbe3fb82c88546c1aa4344715d01bc31839
Dependencies: #21998, #22001 Stopgaps:

Status badges

Description (last modified by 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.

Change History (33)

comment:1 Changed 6 years ago by Julian Rüth

Description: modified (diff)

comment:2 Changed 6 years ago by Julian Rüth

Dependencies: #21998

comment:3 Changed 6 years ago by Julian Rüth

Branch: u/saraedum/factorization_in_iterated_extensions_of_finite_fields

comment:4 Changed 6 years ago by git

Commit: 1a3cb94b126040085044a697d368b9c1950c9c21

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

ec1b78bfix typo in any_root()
af6f451Merge branch 't/21998/any_root___sometimes_fails_over_finite_fields' into t/21996/factorization_in_iterated_extensions_of_finite_fields
3a43d57fix doctests for _isomorphic_ring
1a3cb94extend _isomorphic_ring to handle number fields

comment:5 Changed 6 years ago by Julian Rüth

Status: newneeds_review

comment:6 Changed 6 years ago by git

Commit: 1a3cb94b126040085044a697d368b9c1950c9c211c9f1c62cf964998e7e97776e4fca478091bc9c4

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

ca050d3Refine quotient ring category to Fields()
f9e393bImprove categories of quotient ring morphisms
80a0e1fRefine category of quotient rings isomorphic to number fields
1c9f1c6Make quotient ring morphisms inherit from the correct category type

comment:7 Changed 6 years ago by 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.

comment:8 Changed 6 years ago by Julian Rüth

Dependencies: #21998#21998, #22001

comment:9 Changed 6 years ago by git

Commit: 1c9f1c62cf964998e7e97776e4fca478091bc9c4b2dfab45249f3e6c02d179c37ed71b5d4ba38321

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

b2dfab4Do not pass in category explicitly

comment:10 Changed 6 years ago by git

Commit: b2dfab45249f3e6c02d179c37ed71b5d4ba38321725ad0f73a793c5e9c8386f3289498ceef914073

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

725ad0fMerge branch 'develop' into u/saraedum/factorization_in_iterated_extensions_of_finite_fields

comment:11 Changed 6 years ago by 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?

comment:12 Changed 6 years ago by Jean-Pierre Flori

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

comment:13 Changed 5 years ago by git

Commit: 725ad0f73a793c5e9c8386f3289498ceef91407387b2f6581cacee954d81a9b89ff97732308da3e4

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

87b2f65Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

comment:14 Changed 5 years ago by Julian Rüth

Status: needs_reviewneeds_work

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

comment:15 Changed 5 years ago by Julian Rüth

Work issues: merge conflicts, factorization incorrect

comment:16 Changed 5 years ago by Julian Rüth

Keywords: sd86.5 added

comment:17 Changed 5 years ago by git

Commit: 87b2f6581cacee954d81a9b89ff97732308da3e40b44d334b44240d21681c6cb34c178f41f8ee81a

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

0b44d33Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

comment:18 Changed 5 years ago by Julian Rüth

Work issues: merge conflicts, factorization incorrectfactorization incorrect

New commits:

0b44d33Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

New commits:

0b44d33Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

comment:19 Changed 5 years ago by erousseau

Branch: u/saraedum/factorization_in_iterated_extensions_of_finite_fieldsu/erousseau/factorization_in_iterated_extensions_of_finite_fields

comment:20 Changed 5 years ago by erousseau

Authors: Julian RüthJulian Rüth, Hanson Smith, Edouard Rousseau
Commit: 0b44d334b44240d21681c6cb34c178f41f8ee81a560893257955242d9367f360b142e4b9b9181d4e
Reviewers: Hanson Smith, Edouard Rousseau
Status: needs_workneeds_review

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

Edouard


New commits:

5608932Fixed a bug in polynomial factorisation

comment:21 Changed 5 years ago by Julian Rüth

Status: needs_reviewpositive_review

comment:22 Changed 5 years ago by Volker Braun

Status: positive_reviewneeds_work
$ 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

comment:23 Changed 5 years ago by Julian Rüth

Branch: u/erousseau/factorization_in_iterated_extensions_of_finite_fieldsu/saraedum/factorization_in_iterated_extensions_of_finite_fields

comment:24 Changed 5 years ago by Julian Rüth

Branch: u/saraedum/factorization_in_iterated_extensions_of_finite_fieldsu/erousseau/factorization_in_iterated_extensions_of_finite_fields
Status: needs_workneeds_review

comment:25 Changed 5 years ago by Julian Rüth

Branch: u/erousseau/factorization_in_iterated_extensions_of_finite_fieldsu/saraedum/factorization_in_iterated_extensions_of_finite_fields

comment:26 Changed 5 years ago by Jean-Pierre Flori

Cc: Jean-Pierre Flori added
Commit: 560893257955242d9367f360b142e4b9b9181d4e439b9afd3eb061983342f9ae235522b1f5b5d65f

New commits:

9ccb592Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields
439b9afThe test suite of quotient refines the category

comment:27 Changed 5 years ago by David Roe

Keywords: sd87 added

comment:28 in reply to:  14 ; Changed 5 years ago by Alyson Deines

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

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()
Version 0, edited 5 years ago by Alyson Deines (next)

comment:29 in reply to:  28 Changed 5 years ago by 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.

comment:30 Changed 5 years ago by Julian Rüth

Work issues: factorization incorrect

comment:31 Changed 5 years ago by git

Commit: 439b9afd3eb061983342f9ae235522b1f5b5d65fd585fdbe3fb82c88546c1aa4344715d01bc31839

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

d585fdbMerge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

comment:32 Changed 5 years ago by Alyson Deines

Reviewers: Hanson Smith, Edouard RousseauHanson Smith, Edouard Rousseau, Aly Deines
Status: needs_reviewpositive_review

comment:33 Changed 5 years ago by Volker Braun

Branch: u/saraedum/factorization_in_iterated_extensions_of_finite_fieldsd585fdbe3fb82c88546c1aa4344715d01bc31839
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.