Chinese Remainder Theorem for univariate polynomials over a field #7595

rlmill · 2009-12-03T17:27:53Z

This wasn't hard to implement, since all the hard work was already done.

Component: algebra

Author: Robert Miller

Reviewer: Robert Bradshaw, John Cremona

Merged: sage-4.3.1.alpha2

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

nathanncohen · 2009-12-04T06:03:20Z

comment:2

Hello !! This is clearly not my field but I dare intrude : I see you are using functions "crt" and "CRT_list", and I wondered if you would find it sensible to rename them to chinese_remainer_theorem and chinese_remainder_theorem_list ? If this is too long, it may be possible to drop the "theorem" from the name, but the fact remains that if I had to use this function sometime ( which is not excluded, as it is a very famous result ), there is no way on earth I would have thought of trying the "crt" function if I had not seen it related to this ticket :-)

I am under the impression the english speakers would end this message with :

"Well, just my two cents" :-)

Nathann

rlmill · 2009-12-04T17:06:34Z

comment:3

Replying to @nathanncohen:

... I wondered if you would find it sensible to rename them to chinese_remainer_theorem ...

This is irrelevant to this ticket. You should bring it up on sage-devel instead.

robertwb · 2009-12-08T07:42:01Z

comment:4

Nice.

rlmill · 2009-12-15T22:30:04Z

Reviewer: Robert Bradshaw

rlmill · 2009-12-15T22:30:04Z

comment:5

This patch wasn't applying, so I've rebased it. No real changes though.

rlmill · 2009-12-15T23:16:07Z

rebased on 4.3.rc0

rlmill · 2009-12-15T23:16:31Z

comment:6

Attachment: trac_7595.patch.gz

Just caught a doctest failure in sage/rings/arith.py. Oops!

mwhansen · 2009-12-16T02:31:15Z

Work Issues: needs rebase

rlmill · 2009-12-16T02:32:28Z

comment:8

Which ticket is the patch conflicting with?

rlmill · 2009-12-18T22:38:03Z

comment:9

I've checked, and this merges with the current rc1.

JohnCremona · 2009-12-22T15:58:21Z

comment:10

The patch is fine, applies to 4.3.rc0 and all tests pass in sage/rings.

I have some problems with the CRT* functions though.

CRT_list does not check that the two lists have the same length; if the moduli list is shorter you get an IndexError, but it would be better to catch that and raise a more informative error.
CRT_basis is rather silly. It calls CRT_list n times with the same moduli, which must be wasteful. It would be better to call plain CRT n times with suitable moduli (exercise for the reader).

Of course, I don't think that these issues should delay the current patch, but deserve a ticket of their own to make sure they are tided up.

JohnCremona · 2009-12-22T15:58:21Z

Changed reviewer from Robert Bradshaw to Robert Bradshaw, John Cremona

JohnCremona · 2009-12-22T15:58:21Z

Changed work issues from needs rebase to none

mwhansen · 2010-01-03T21:38:39Z

Merged: sage-4.3.1.alpha0

mwhansen · 2010-01-03T21:38:39Z

comment:11

I've made #7836 for this.

mwhansen · 2010-01-04T01:17:30Z

Changed merged from sage-4.3.1.alpha0 to none

mwhansen · 2010-01-04T01:17:30Z

comment:12

This causes failures in the following file sage/quadratic_forms/quadratic_form__ternary_Tornaria.py:

**********************************************************************
File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/devel/sage-main/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 476:
    sage: map(Q1.xi_rec, [-1,2,3,5])
Exception raised:
    Traceback (most recent call last):
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_18[8]>", line 1, in <module>
        map(Q1.xi_rec, [-Integer(1),Integer(2),Integer(3),Integer(5)])###line 476:
    sage: map(Q1.xi_rec, [-1,2,3,5])
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 481, in xi_rec
        return self.reciprocal().xi(p)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 456, in xi
        return kronecker_symbol(p, self.basiclemma(2))
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 385, in basiclemma
        a=self(self.basiclemmavec(M))
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 416, in basiclemmavec
        return CRT_list(vec,mod)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/rings/arith.py", line 2522, in CRT_list
        return moduli[0].parent()(v[0])
      File "parent.pyx", line 538, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:4956)
      File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3142)
      File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3040)
      File "integer.pyx", line 653, in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:6803)
    TypeError: unable to coerce <type 'sage.modules.vector_integer_dense.Vector_integer_dense'> to an integer
**********************************************************************
File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/devel/sage-main/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 478:
    sage: map(Q2.xi_rec, [-1,2,3,5])
Exception raised:
    Traceback (most recent call last):
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_18[9]>", line 1, in <module>
        map(Q2.xi_rec, [-Integer(1),Integer(2),Integer(3),Integer(5)])###line 478:
    sage: map(Q2.xi_rec, [-1,2,3,5])
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 481, in xi_rec
        return self.reciprocal().xi(p)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 456, in xi
        return kronecker_symbol(p, self.basiclemma(2))
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 385, in basiclemma
        a=self(self.basiclemmavec(M))
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/quadratic_forms/quadratic_form__ternary_Tornaria.py", line 416, in basiclemmavec
        return CRT_list(vec,mod)
      File "/virtual/scratch/mhansen/release/4.3.1/alpha0/sage-4.3.1.alpha0/local/lib/python/site-packages/sage/rings/arith.py", line 2522, in CRT_list
        return moduli[0].parent()(v[0])
      File "parent.pyx", line 538, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:4956)
      File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3142)
      File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3040)
      File "integer.pyx", line 653, in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:6803)
    TypeError: unable to coerce <type 'sage.modules.vector_integer_dense.Vector_integer_dense'> to an integer

rlmill · 2010-01-04T15:37:39Z

Attachment: trac_7595-failures.patch.gz

Should fix the issues in quadratic_form__ternary_Tornaria.py

rlmill · 2010-01-04T15:38:29Z

comment:13

This patch should fix the issues mentioned above. I wasn't sure whether to make a new ticket, or just post it here (never seen a "needs_work" closed ticket...)

JohnCremona · 2010-01-04T16:22:42Z

comment:15

I changed the ticket to "needs review" and then gave it a positive review -- it works for me.

sagetrac-mvngu · 2010-01-07T00:22:32Z

comment:16

This ticket is rather messy. The patch trac_7595.patch is merged in Sage 4.3.1.alpha0 and it was then closed as being fixed in that version. Later on, the value in the field "Merged in:" was deleted. Now there is another patch trac_7595-failures.patch which hasn't been merged yet as of Sage 4.3.1.alpha1. And yet the ticket is declared as "fixed", but without a value for the field "Merged in:". I think the ticket's status should now be "open" not "fixed", until trac_7595-failures.patch is merged.

rlmill · 2010-01-07T04:30:47Z

comment:17

Replying to @sagetrac-mvngu:

The patch trac_7595.patch is merged in Sage 4.3.1.alpha0 ... Now there is another patch trac_7595-failures.patch which hasn't been merged yet as of Sage 4.3.1.alpha1.

The patch was rolled back-- neither is in Sage-4.3.1.alpha1

And yet the ticket is declared as "fixed"...

Apparently when the ticket was reopened, this did not revert. I don't know how to fix this, but the ticket is definitely open.

... until trac_7595-failures.patch is merged.

Repeat: as of sage-4.3.1.alpha1, both patches need to be merged.

rlmill · 2010-01-13T05:03:26Z

Merged: 4.3.1.alpha2

sagetrac-mvngu · 2010-01-13T19:51:12Z

Changed merged from 4.3.1.alpha2 to sage-4.3.1.alpha2

rlmill mannequin added this to the sage-4.3.1 milestone Dec 3, 2009

rlmill mannequin added c: algebra labels Dec 3, 2009

rlmill mannequin assigned aghitza Dec 3, 2009

rlmill mannequin changed the title ~~Chinese Remainder Theorem for polynomials over a field~~ Chinese Remainder Theorem for univariate polynomials over a field Dec 3, 2009

rlmill mannequin added the s: needs review label Dec 3, 2009

nathanncohen mannequin added s: needs info and removed s: needs review labels Dec 4, 2009

rlmill mannequin added s: needs review and removed s: needs info labels Dec 4, 2009

robertwb added s: positive review and removed s: needs review labels Dec 8, 2009

mwhansen added s: needs work and removed s: positive review labels Dec 16, 2009

rlmill mannequin added s: needs review and removed s: needs work labels Dec 18, 2009

JohnCremona added s: positive review and removed s: needs review labels Dec 22, 2009

mwhansen removed the s: positive review label Jan 3, 2010

mwhansen closed this as completed Jan 3, 2010

mwhansen added the s: needs work label Jan 4, 2010

mwhansen reopened this Jan 4, 2010

JohnCremona added s: needs review and removed s: needs work labels Jan 4, 2010

JohnCremona added s: positive review and removed s: needs review labels Jan 4, 2010

rlmill mannequin removed the s: positive review label Jan 13, 2010

rlmill mannequin closed this as completed Jan 13, 2010

JohnCremona mentioned this issue Jan 4, 2010

Clean up the CRT_* functions #7836

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Chinese Remainder Theorem for univariate polynomials over a field #7595

Chinese Remainder Theorem for univariate polynomials over a field #7595

rlmill mannequin commented Dec 3, 2009

nathanncohen mannequin commented Dec 4, 2009

rlmill mannequin commented Dec 4, 2009

robertwb commented Dec 8, 2009

rlmill mannequin commented Dec 15, 2009

rlmill mannequin commented Dec 15, 2009

rlmill mannequin commented Dec 15, 2009

rlmill mannequin commented Dec 15, 2009

mwhansen commented Dec 16, 2009

rlmill mannequin commented Dec 16, 2009

rlmill mannequin commented Dec 18, 2009

JohnCremona commented Dec 22, 2009

JohnCremona commented Dec 22, 2009

JohnCremona commented Dec 22, 2009

mwhansen commented Jan 3, 2010

mwhansen commented Jan 3, 2010

mwhansen commented Jan 4, 2010

mwhansen commented Jan 4, 2010

rlmill mannequin commented Jan 4, 2010

rlmill mannequin commented Jan 4, 2010

JohnCremona commented Jan 4, 2010

sagetrac-mvngu mannequin commented Jan 7, 2010

rlmill mannequin commented Jan 7, 2010

rlmill mannequin commented Jan 13, 2010

sagetrac-mvngu mannequin commented Jan 13, 2010

Chinese Remainder Theorem for univariate polynomials over a field #7595

Chinese Remainder Theorem for univariate polynomials over a field #7595

Comments

rlmill mannequin commented Dec 3, 2009

nathanncohen mannequin commented Dec 4, 2009

rlmill mannequin commented Dec 4, 2009

robertwb commented Dec 8, 2009

rlmill mannequin commented Dec 15, 2009

rlmill mannequin commented Dec 15, 2009

rlmill mannequin commented Dec 15, 2009

rlmill mannequin commented Dec 15, 2009

mwhansen commented Dec 16, 2009

rlmill mannequin commented Dec 16, 2009

rlmill mannequin commented Dec 18, 2009

JohnCremona commented Dec 22, 2009

JohnCremona commented Dec 22, 2009

JohnCremona commented Dec 22, 2009

mwhansen commented Jan 3, 2010

mwhansen commented Jan 3, 2010

mwhansen commented Jan 4, 2010

mwhansen commented Jan 4, 2010

rlmill mannequin commented Jan 4, 2010

rlmill mannequin commented Jan 4, 2010

JohnCremona commented Jan 4, 2010

sagetrac-mvngu mannequin commented Jan 7, 2010

rlmill mannequin commented Jan 7, 2010

rlmill mannequin commented Jan 13, 2010

sagetrac-mvngu mannequin commented Jan 13, 2010