Opened 2 years ago

Closed 22 months 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 saraedum)

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 2 years ago by saraedum

  • Description modified (diff)

comment:2 Changed 2 years ago by saraedum

  • Dependencies set to #21998

comment:3 Changed 2 years ago by saraedum

  • Branch set to u/saraedum/factorization_in_iterated_extensions_of_finite_fields

comment:4 Changed 2 years ago by git

  • Commit set to 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 2 years ago by saraedum

  • Status changed from new to needs_review

comment:6 Changed 2 years ago by git

  • Commit changed from 1a3cb94b126040085044a697d368b9c1950c9c21 to 1c9f1c62cf964998e7e97776e4fca478091bc9c4

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 2 years ago by saraedum

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 2 years ago by saraedum

  • Dependencies changed from #21998 to #21998, #22001

comment:9 Changed 2 years ago by git

  • Commit changed from 1c9f1c62cf964998e7e97776e4fca478091bc9c4 to b2dfab45249f3e6c02d179c37ed71b5d4ba38321

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

b2dfab4Do not pass in category explicitly

comment:10 Changed 2 years ago by git

  • Commit changed from b2dfab45249f3e6c02d179c37ed71b5d4ba38321 to 725ad0f73a793c5e9c8386f3289498ceef914073

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 2 years ago by jpflori

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 2 years ago by jpflori

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

comment:13 Changed 2 years ago by git

  • Commit changed from 725ad0f73a793c5e9c8386f3289498ceef914073 to 87b2f6581cacee954d81a9b89ff97732308da3e4

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 follow-up: Changed 2 years ago by saraedum

  • 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 2 years ago by saraedum

  • Work issues set to merge conflicts, factorization incorrect

comment:16 Changed 2 years ago by saraedum

  • Keywords sd86.5 added

comment:17 Changed 2 years ago by git

  • Commit changed from 87b2f6581cacee954d81a9b89ff97732308da3e4 to 0b44d334b44240d21681c6cb34c178f41f8ee81a

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 2 years ago by saraedum

  • Work issues changed from merge conflicts, factorization incorrect to factorization 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 2 years ago by erousseau

  • 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 2 years ago by erousseau

  • Authors changed from Julian Rüth to Julian Rüth, Hanson Smith, Edouard Rousseau
  • 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:

5608932Fixed a bug in polynomial factorisation

comment:21 Changed 2 years ago by saraedum

  • Status changed from needs_review to positive_review

comment:22 Changed 2 years ago by vbraun

  • 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 2 years ago by saraedum

  • 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 2 years ago by saraedum

  • 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 2 years ago by saraedum

  • 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 2 years ago by jpflori

  • Cc jpflori added
  • Commit changed from 560893257955242d9367f360b142e4b9b9181d4e to 439b9afd3eb061983342f9ae235522b1f5b5d65f

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 22 months ago by roed

  • Keywords sd87 added

comment:28 in reply to: ↑ 14 ; follow-up: Changed 22 months ago by 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()
Last edited 22 months ago by aly.deines (previous) (diff)

comment:29 in reply to: ↑ 28 Changed 22 months ago by saraedum

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 22 months ago by saraedum

  • Work issues factorization incorrect deleted

comment:31 Changed 22 months ago by git

  • Commit changed from 439b9afd3eb061983342f9ae235522b1f5b5d65f to d585fdbe3fb82c88546c1aa4344715d01bc31839

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 22 months ago by aly.deines

  • 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 22 months ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.