Opened 4 years ago
Closed 4 years ago
#21996 closed enhancement (fixed)
Factorization in iterated extensions of finite fields
Reported by: | saraedum | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.5 |
Component: | finite rings | Keywords: | factorization, finite field, sd86.5, sd87 |
Cc: | jpflori | 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) | 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 4 years ago by
- Description modified (diff)
comment:2 Changed 4 years ago by
- Dependencies set to #21998
comment:3 Changed 4 years ago by
- Branch set to u/saraedum/factorization_in_iterated_extensions_of_finite_fields
comment:4 Changed 4 years ago by
- Commit set to 1a3cb94b126040085044a697d368b9c1950c9c21
comment:5 Changed 4 years ago by
- Status changed from new to needs_review
comment:6 Changed 4 years ago by
- Commit changed from 1a3cb94b126040085044a697d368b9c1950c9c21 to 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 4 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 4 years ago by
- Dependencies changed from #21998 to #21998, #22001
comment:9 Changed 4 years ago by
- Commit changed from 1c9f1c62cf964998e7e97776e4fca478091bc9c4 to b2dfab45249f3e6c02d179c37ed71b5d4ba38321
Branch pushed to git repo; I updated commit sha1. New commits:
b2dfab4 | Do not pass in category explicitly
|
comment:10 Changed 4 years ago by
- Commit changed from b2dfab45249f3e6c02d179c37ed71b5d4ba38321 to 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 4 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:12 Changed 4 years ago by
You've got this simple model stuff for function fields.
comment:13 Changed 4 years ago by
- Commit changed from 725ad0f73a793c5e9c8386f3289498ceef914073 to 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 follow-up: ↓ 28 Changed 4 years ago by
- Status changed from needs_review to 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 4 years ago by
- Work issues set to merge conflicts, factorization incorrect
comment:16 Changed 4 years ago by
- Keywords sd86.5 added
comment:17 Changed 4 years ago by
- Commit changed from 87b2f6581cacee954d81a9b89ff97732308da3e4 to 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 4 years ago by
- Work issues changed from merge conflicts, factorization incorrect to factorization incorrect
comment:19 Changed 4 years ago by
- Branch changed from u/saraedum/factorization_in_iterated_extensions_of_finite_fields to u/erousseau/factorization_in_iterated_extensions_of_finite_fields
comment:20 Changed 4 years ago by
- Commit changed from 0b44d334b44240d21681c6cb34c178f41f8ee81a to 560893257955242d9367f360b142e4b9b9181d4e
- Reviewers set to Hanson Smith, Edouard Rousseau
- Status changed from needs_work to 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 4 years ago by
- Status changed from needs_review to positive_review
comment:22 Changed 4 years ago by
- Status changed from positive_review to needs_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 4 years ago by
- Branch changed from u/erousseau/factorization_in_iterated_extensions_of_finite_fields to u/saraedum/factorization_in_iterated_extensions_of_finite_fields
comment:24 Changed 4 years ago by
- Branch changed from u/saraedum/factorization_in_iterated_extensions_of_finite_fields to u/erousseau/factorization_in_iterated_extensions_of_finite_fields
- Status changed from needs_work to needs_review
comment:25 Changed 4 years ago by
- Branch changed from u/erousseau/factorization_in_iterated_extensions_of_finite_fields to u/saraedum/factorization_in_iterated_extensions_of_finite_fields
comment:26 Changed 4 years ago by
- Cc jpflori added
- Commit changed from 560893257955242d9367f360b142e4b9b9181d4e to 439b9afd3eb061983342f9ae235522b1f5b5d65f
comment:27 Changed 4 years ago by
- Keywords sd87 added
comment:28 in reply to: ↑ 14 ; follow-up: ↓ 29 Changed 4 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 in reply to: ↑ 28 Changed 4 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 4 years ago by
- Work issues factorization incorrect deleted
comment:31 Changed 4 years ago by
- Commit changed from 439b9afd3eb061983342f9ae235522b1f5b5d65f to 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 4 years ago by
- Reviewers changed from Hanson Smith, Edouard Rousseau to Hanson Smith, Edouard Rousseau, Aly Deines
- Status changed from needs_review to positive_review
comment:33 Changed 4 years ago by
- Branch changed from u/saraedum/factorization_in_iterated_extensions_of_finite_fields to d585fdbe3fb82c88546c1aa4344715d01bc31839
- Resolution set to fixed
- Status changed from positive_review to 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