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,,,,,