#11036: improve solve_mod performance
---------------------------+------------------------------------------------
Reporter: dsm | Owner: burcin
Type: enhancement | Status: new
Priority: minor | Milestone:
Component: symbolics | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
---------------------------+------------------------------------------------
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,)]
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11036>
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.
