#13825: roots over IntegerModRing is horribly slow
-----------------------------------+----------------------------------------
Reporter: zimmerma | Owner: malb
Type: enhancement | Status: new
Priority: minor | Milestone: sage-5.6
Component: commutative algebra | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
-----------------------------------+----------------------------------------
Consider the following:
{{{
----------------------------------------------------------------------
| Sage Version 5.1, Release Date: 2012-07-09 |
| Type "notebook()" for the browser-based notebook interface. |
| Type "help()" for help. |
----------------------------------------------------------------------
sage: R.<x> = IntegerModRing(20000009)[]
sage: eq = x^6+x-17
sage: time eq.roots(multiplicities=False)
[3109038, 17207405]
Time: CPU 202.93 s, Wall: 203.65 s
}}}
A faster method would be (when the modulus is not too large) to factor it,
solve modulo the prime factors, and reconstruct using CRT:
{{{
sage: R.<x> = IntegerModRing(61)[]
sage: eq = x^6+x-17
sage: time eq.roots(multiplicities=False)
[51, 37]
Time: CPU 0.00 s, Wall: 0.00 s
sage: R.<x> = IntegerModRing(327869)[]
sage: eq = x^6+x-17
sage: time eq.roots(multiplicities=False)
[158217]
Time: CPU 0.00 s, Wall: 0.00 s
sage: crt([51,158217],[61,327869])
3109038
sage: crt([37,158217],[61,327869])
17207405
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13825>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
