id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
11036 improve solve_mod performance dsm burcin "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.
" enhancement closed minor sage-4.7.2 symbolics fixed modular arithmetic, sd32 kcrisman sage-4.7.2.alpha3 Douglas McNeil, Maarten Derickx John Cremona, Simon Spicer N/A