Opened 8 years ago

Last modified 8 years ago

#11036 closed enhancement

improve solve_mod performance — at Initial Version

Reported by: dsm Owned by: burcin
Priority: minor Milestone: sage-4.7.2
Component: symbolics Keywords: modular arithmetic, sd32
Cc: kcrisman Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

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

Change History (0)

Note: See TracTickets for help on using tickets.