Opened 9 years ago

Closed 9 years ago

#10047 closed defect (fixed)

ZeroDivisionError in crt method of IntegerMod

Reported by: roed Owned by: AlexGhitza
Priority: minor Milestone: sage-4.6
Component: algebra Keywords:
Cc: robertwb Merged in: sage-4.6.1.alpha0
Authors: David Roe Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

mod(0,1).crt(mod(a, n)) raises a ZeroDivisionError if and only if n >= 2^31-1.

sage: mod(0,1).crt(mod(4,2^31-2)) 
4
sage: mod(0,1).crt(mod(4,2^31-1)) 
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)

Attachments (2)

7931_crt.patch (1.5 KB) - added by roed 9 years ago.
10047.patch (1.5 KB) - added by jdemeyer 9 years ago.
Fixed commit message

Download all attachments as: .zip

Change History (13)

comment:1 Changed 9 years ago by roed

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by zimmerma

  • Cc robertwb added
  • Reviewers set to Paul Zimmermann

David, I'm not sure the proposed patch is optimal. Indeed, the problem only occurs when self is a small integer and other is a GMP integer. Since the small integer code seems to deal correctly with mod(0,1), a fix is only needed is the case self=mod(0,1) and other is a GMP integer, for example after the line

        if other.modulus() == 1:
            return self

Robert, since you wrote this code, can you comment on this?

Paul

comment:3 Changed 9 years ago by zimmerma

  • Status changed from needs_review to needs_work

by the way, the following doctest fails with this patch (with Sage 4.5.3):

The following tests failed:


        sage -t  "devel/sage-10047/sage/misc/trace.py"

The detailed error is:

[zimmerma@coing sage-4.5.3]$ sage -t  devel/sage-10047/sage/misc/trace.py 
sage -t  "devel/sage-10047/sage/misc/trace.py"              
**********************************************************************
File "/usr/local/sage-4.5.3/sage/devel/sage-10047/sage/misc/trace.py", line 61:
    sage: print s.before[s.before.find('-'):]
Expected:
    ---...
    ipdb> c
    2 * 5
Got:
    ----------------------------------------------------------------------
    | Sage Version 4.5.3, Release Date: 2010-09-04                       |
    | Type notebook() for the GUI, and license() for information.        |
    ----------------------------------------------------------------------
    trace('print factor(10)'); print 3+97
    s
    c
    Loading Sage library. Current Mercurial branch is: 
**********************************************************************
1 items had failures:
   1 of  10 in __main__.example_1
***Test Failed*** 1 failures.
For whitespace errors, see the file /home/zimmerma/.sage//tmp/.doctest_trace.py
         [4.5 s]

It works ok with vanilla 4.5.3.

Paul

comment:4 Changed 9 years ago by mhansen

Note that the above error is #9446.

comment:5 Changed 9 years ago by zimmerma

Note that the above error is #9446.

thus maybe we should wait that #9446 is fixed.

Paul

comment:6 Changed 9 years ago by mhansen

That issue is independent of this one.

comment:7 Changed 9 years ago by zimmerma

That issue is independent of this one.

anyway, the issue raised in comment 2 still holds. Robert, are you out there?

Paul

Changed 9 years ago by roed

comment:8 Changed 9 years ago by roed

  • Status changed from needs_work to needs_review

I've changed it so that it only tests for self==mod(0,1) when needed.

comment:9 Changed 9 years ago by zimmerma

  • Status changed from needs_review to positive_review

I've changed it so that it only tests for self==mod(0,1) when needed.

thanks, I am now satisfied with the patch.

Paul

comment:10 Changed 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Please change the commit message of the patch (use hg qrefresh -e for that) such that it contains a description of the patch and also the correct ticket number.

Changed 9 years ago by jdemeyer

Fixed commit message

comment:11 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.6.1.alpha0
  • Resolution set to fixed
  • Status changed from needs_work to closed
Note: See TracTickets for help on using tickets.