Factorization in iterated extensions of finite fields #21996

saraedum · 2016-11-30T04:23:49Z

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.

Depends on #21998
Depends on #22001

CC: @jpflori

Component: finite rings

Keywords: factorization, finite field, sd86.5, sd87

Author: Julian Rüth, Hanson Smith, Edouard Rousseau

Branch/Commit: d585fdb

Reviewer: Hanson Smith, Edouard Rousseau, Aly Deines

Issue created by migration from https://trac.sagemath.org/ticket/21996

The text was updated successfully, but these errors were encountered:

saraedum · 2016-11-30T06:42:33Z

Dependencies: #21998

saraedum · 2016-11-30T07:15:46Z

Branch: u/saraedum/factorization_in_iterated_extensions_of_finite_fields

sagetrac-git · 2016-11-30T07:37:07Z

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`

sagetrac-git · 2016-11-30T07:37:07Z

Commit: 1a3cb94

sagetrac-git · 2016-11-30T18:34:27Z

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`

sagetrac-git · 2016-11-30T18:34:27Z

Changed commit from 1a3cb94 to 1c9f1c6

saraedum · 2016-11-30T18:41:55Z

comment:7

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.

saraedum · 2016-11-30T18:52:23Z

Changed dependencies from #21998 to #21998, #22001

sagetrac-git · 2016-11-30T18:54:41Z

Changed commit from 1c9f1c6 to b2dfab4

sagetrac-git · 2016-11-30T18:54:41Z

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

`b2dfab4`	`Do not pass in category explicitly`

sagetrac-git · 2017-01-24T20:59:34Z

Changed commit from b2dfab4 to 725ad0f

sagetrac-git · 2017-01-24T20:59:34Z

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`

jpflori · 2017-01-31T10:45:23Z

comment:11

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?

jpflori · 2017-01-31T10:49:05Z

comment:12

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

sagetrac-git · 2017-04-18T09:31:14Z

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`

sagetrac-git · 2017-04-18T09:31:14Z

Changed commit from 725ad0f to 87b2f65

saraedum · 2017-05-27T05:30:46Z

comment:14

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

saraedum · 2017-05-27T05:31:21Z

Work Issues: merge conflicts, factorization incorrect

saraedum · 2017-06-06T03:33:31Z

Changed keywords from factorization, finite field to factorization, finite field, sd86.5

sagetrac-git · 2017-06-06T03:41:50Z

Changed commit from 87b2f65 to 0b44d33

sagetrac-git · 2017-06-06T03:41:50Z

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`

saraedum · 2017-06-06T03:42:15Z

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`

sagetrac-erousseau · 2017-06-09T00:12:05Z

Changed commit from 0b44d33 to 5608932

sagetrac-erousseau · 2017-06-09T00:12:05Z

comment:20

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

Edouard

New commits:

`5608932`	`Fixed a bug in polynomial factorisation`

sagetrac-erousseau · 2017-06-09T00:12:05Z

Reviewer: Hanson Smith, Edouard Rousseau

vbraun · 2017-06-09T22:15:01Z

comment:22

$ 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

saraedum · 2017-06-12T01:20:03Z

Changed branch from u/erousseau/factorization_in_iterated_extensions_of_finite_fields to u/saraedum/factorization_in_iterated_extensions_of_finite_fields

saraedum · 2017-06-12T01:20:22Z

Changed branch from u/saraedum/factorization_in_iterated_extensions_of_finite_fields to u/erousseau/factorization_in_iterated_extensions_of_finite_fields

saraedum · 2017-06-12T01:20:38Z

Changed branch from u/erousseau/factorization_in_iterated_extensions_of_finite_fields to u/saraedum/factorization_in_iterated_extensions_of_finite_fields

jpflori · 2017-06-22T09:53:16Z

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`

jpflori · 2017-06-22T09:53:16Z

Changed commit from 5608932 to 439b9af

roed314 · 2017-07-17T17:45:39Z

Changed keywords from factorization, finite field, sd86.5 to factorization, finite field, sd86.5, sd87

adeines · 2017-07-18T20:41:34Z

comment:28

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

saraedum · 2017-07-19T01:20:40Z

comment:29

Replying to @adeines:

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.

saraedum · 2017-07-19T01:20:56Z

Changed work issues from factorization incorrect to none

sagetrac-git · 2017-07-20T18:13:37Z

Changed commit from 439b9af to d585fdb

sagetrac-git · 2017-07-20T18:13:37Z

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`

adeines · 2017-07-21T16:05:31Z

Changed reviewer from Hanson Smith, Edouard Rousseau to Hanson Smith, Edouard Rousseau, Aly Deines

vbraun · 2017-07-26T22:13:34Z

Changed branch from u/saraedum/factorization_in_iterated_extensions_of_finite_fields to d585fdb

saraedum added this to the sage-7.5 milestone Nov 30, 2016

saraedum added c: finite rings labels Nov 30, 2016

This comment has been minimized.

Sign in to view

saraedum added the s: needs review label Nov 30, 2016

saraedum added s: needs work and removed s: needs review labels May 27, 2017

sagetrac-erousseau mannequin added s: needs review and removed s: needs work labels Jun 9, 2017

saraedum added s: positive review and removed s: needs review labels Jun 9, 2017

vbraun added s: needs work and removed s: positive review labels Jun 9, 2017

saraedum added s: needs review and removed s: needs work labels Jun 12, 2017

adeines mannequin added s: positive review and removed s: needs review labels Jul 21, 2017

vbraun removed the s: positive review label Jul 26, 2017

vbraun closed this as completed in a3befda Jul 26, 2017

saraedum mentioned this issue Dec 22, 2018

A framework for discrete valuations in Sage #21869

Closed

Factorization in iterated extensions of finite fields #21996

Factorization in iterated extensions of finite fields #21996

Comments

saraedum commented Nov 30, 2016

This comment has been minimized.

saraedum commented Nov 30, 2016

saraedum commented Nov 30, 2016

sagetrac-git mannequin commented Nov 30, 2016

sagetrac-git mannequin commented Nov 30, 2016

sagetrac-git mannequin commented Nov 30, 2016

sagetrac-git mannequin commented Nov 30, 2016

saraedum commented Nov 30, 2016

saraedum commented Nov 30, 2016

sagetrac-git mannequin commented Nov 30, 2016

sagetrac-git mannequin commented Nov 30, 2016

sagetrac-git mannequin commented Jan 24, 2017

sagetrac-git mannequin commented Jan 24, 2017

jpflori commented Jan 31, 2017

jpflori commented Jan 31, 2017

sagetrac-git mannequin commented Apr 18, 2017

sagetrac-git mannequin commented Apr 18, 2017

saraedum commented May 27, 2017

saraedum commented May 27, 2017

saraedum commented Jun 6, 2017

sagetrac-git mannequin commented Jun 6, 2017

sagetrac-git mannequin commented Jun 6, 2017

saraedum commented Jun 6, 2017

sagetrac-erousseau mannequin commented Jun 9, 2017

sagetrac-erousseau mannequin commented Jun 9, 2017

sagetrac-erousseau mannequin commented Jun 9, 2017

vbraun commented Jun 9, 2017

saraedum commented Jun 12, 2017

saraedum commented Jun 12, 2017

saraedum commented Jun 12, 2017

jpflori commented Jun 22, 2017

jpflori commented Jun 22, 2017

roed314 commented Jul 17, 2017

adeines mannequin commented Jul 18, 2017

saraedum commented Jul 19, 2017

saraedum commented Jul 19, 2017

sagetrac-git mannequin commented Jul 20, 2017

sagetrac-git mannequin commented Jul 20, 2017

adeines mannequin commented Jul 21, 2017

vbraun commented Jul 26, 2017