#11036: improve solve_mod performance
------------------------------------------+---------------------------------
Reporter: dsm | Owner: burcin
Type: enhancement | Status: positive_review
Priority: minor | Milestone: sage-4.7.2
Component: symbolics | Keywords: modular
arithmetic, sd32
Work_issues: | Upstream: N/A
Reviewer: John Cremona, Simon Spicer | Author: Douglas McNiel,
Maarten Derickx
Merged: | Dependencies:
------------------------------------------+---------------------------------
Description changed by leif:
Old description:
> Currently `solve_mod(x^2==41, 100)` breaks this down into solving modulus
> `2^2 and 5^2`, but it doesn't do further reductions, so it actually loops
> over 4 and 25 possibilities directly. This works well for small
> exponents:
>
> {{{
> sage: time solve_mod(x^2 == 41, 10^2)
> CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s
> [(29,), (21,), (79,), (71,)]
> }}}
>
> but performs poorly on larger ones, even if the primes involved are
> small:
>
> {{{
> sage: time solve_mod(x^2 == 41, 10^6)
> CPU times: user 0.86 s, sys: 0.01 s, total: 0.87 s Wall time: 0.99 s
> [(703821,), (452429,), (47571,), (796179,), (203821,), (952429,),
> (547571,), (296179,)]
> }}}
New description:
Currently `solve_mod(x^2==41, 100)` breaks this down into solving modulus
`2^2 and 5^2`, but it doesn't do further reductions, so it actually loops
over 4 and 25 possibilities directly. This works well for small
exponents:
{{{
sage: time solve_mod(x^2 == 41, 10^2)
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s
[(29,), (21,), (79,), (71,)]
}}}
but performs poorly on larger ones, even if the primes involved are small:
{{{
sage: time solve_mod(x^2 == 41, 10^6)
CPU times: user 0.86 s, sys: 0.01 s, total: 0.87 s Wall time: 0.99 s
[(703821,), (452429,), (47571,), (796179,), (203821,), (952429,),
(547571,), (296179,)]
}}}
----
Apply only [attachment:trac_11036-solve-mod.patch] to the Sage library.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11036#comment:10>
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.
