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:  sage7.5 
Component:  finite rings  Keywords:  factorization, finite field, sd86.5, sd87 
Cc:  JeanPierre 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: 
Description (last modified by )
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
Description:  modified (diff) 

comment:2 Changed 6 years ago by
Dependencies:  → #21998 

comment:3 Changed 6 years ago by
Branch:  → u/saraedum/factorization_in_iterated_extensions_of_finite_fields 

comment:4 Changed 6 years ago by
Commit:  → 1a3cb94b126040085044a697d368b9c1950c9c21 

comment:5 Changed 6 years ago by
Status:  new → needs_review 

comment:6 Changed 6 years ago by
Commit:  1a3cb94b126040085044a697d368b9c1950c9c21 → 1c9f1c62cf964998e7e97776e4fca478091bc9c4 

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

comment:7 Changed 6 years ago by
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
Dependencies:  #21998 → #21998, #22001 

comment:9 Changed 6 years ago by
Commit:  1c9f1c62cf964998e7e97776e4fca478091bc9c4 → b2dfab45249f3e6c02d179c37ed71b5d4ba38321 

Branch pushed to git repo; I updated commit sha1. New commits:
b2dfab4  Do not pass in category explicitly

comment:10 Changed 6 years ago by
Commit:  b2dfab45249f3e6c02d179c37ed71b5d4ba38321 → 725ad0f73a793c5e9c8386f3289498ceef914073 

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

comment:11 Changed 6 years ago by
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:13 Changed 6 years ago by
Commit:  725ad0f73a793c5e9c8386f3289498ceef914073 → 87b2f6581cacee954d81a9b89ff97732308da3e4 

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

comment:14 followup: 28 Changed 6 years ago by
Status:  needs_review → needs_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 6 years ago by
Work issues:  → merge conflicts, factorization incorrect 

comment:16 Changed 5 years ago by
Keywords:  sd86.5 added 

comment:17 Changed 5 years ago by
Commit:  87b2f6581cacee954d81a9b89ff97732308da3e4 → 0b44d334b44240d21681c6cb34c178f41f8ee81a 

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

comment:18 Changed 5 years ago by
Work issues:  merge conflicts, factorization incorrect → factorization incorrect 

comment:19 Changed 5 years ago by
Branch:  u/saraedum/factorization_in_iterated_extensions_of_finite_fields → u/erousseau/factorization_in_iterated_extensions_of_finite_fields 

comment:20 Changed 5 years ago by
Authors:  Julian Rüth → Julian Rüth, Hanson Smith, Edouard Rousseau 

Commit:  0b44d334b44240d21681c6cb34c178f41f8ee81a → 560893257955242d9367f360b142e4b9b9181d4e 
Reviewers:  → Hanson Smith, Edouard Rousseau 
Status:  needs_work → needs_review 
If the fix is OK, then I think it is ready for positive review.
Edouard
New commits:
5608932  Fixed a bug in polynomial factorisation

comment:21 Changed 5 years ago by
Status:  needs_review → positive_review 

comment:22 Changed 5 years ago by
Status:  positive_review → needs_work 

$ sage t long warnlong 68.9 src/sage/rings/polynomial/polynomial_quotient_ring.py # 4 doctests failed Running doctests with ID 201706100008570afdacb4. Git branch: develop Using optional=mpir,python2,sage Doctesting 1 file. sage t long warnlong 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 warnlong 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
Branch:  u/erousseau/factorization_in_iterated_extensions_of_finite_fields → u/saraedum/factorization_in_iterated_extensions_of_finite_fields 

comment:24 Changed 5 years ago by
Branch:  u/saraedum/factorization_in_iterated_extensions_of_finite_fields → u/erousseau/factorization_in_iterated_extensions_of_finite_fields 

Status:  needs_work → needs_review 
comment:25 Changed 5 years ago by
Branch:  u/erousseau/factorization_in_iterated_extensions_of_finite_fields → u/saraedum/factorization_in_iterated_extensions_of_finite_fields 

comment:26 Changed 5 years ago by
Cc:  JeanPierre Flori added 

Commit:  560893257955242d9367f360b142e4b9b9181d4e → 439b9afd3eb061983342f9ae235522b1f5b5d65f 
comment:27 Changed 5 years ago by
Keywords:  sd87 added 

comment:28 followup: 29 Changed 5 years ago by
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()
comment:29 Changed 5 years ago by
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
Work issues:  factorization incorrect 

comment:31 Changed 5 years ago by
Commit:  439b9afd3eb061983342f9ae235522b1f5b5d65f → d585fdbe3fb82c88546c1aa4344715d01bc31839 

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

comment:32 Changed 5 years ago by
Reviewers:  Hanson Smith, Edouard Rousseau → Hanson Smith, Edouard Rousseau, Aly Deines 

Status:  needs_review → positive_review 
comment:33 Changed 5 years ago by
Branch:  u/saraedum/factorization_in_iterated_extensions_of_finite_fields → d585fdbe3fb82c88546c1aa4344715d01bc31839 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
fix typo in any_root()
Merge branch 't/21998/any_root___sometimes_fails_over_finite_fields' into t/21996/factorization_in_iterated_extensions_of_finite_fields
fix doctests for _isomorphic_ring
extend _isomorphic_ring to handle number fields