# solve_mod() takes long time and no result return when computing big numbers

when I use solve_mod to solve equations like slove_mod([3x + 2y == 5,6 * x + 5 * y ==11],13),it will return a result quickly . However,when i use it like solve_mod([9677035x + 7162589 *y == 4477085 ,5302728x + 8472081*y == 11061226],14282531),it takes long time but no result return, i was wondering whether solve_mod()'s alogrithm is horrible when big numbers are computed.Is there a faster way to solve big numbers equation?

edit retag close merge delete

Sort by » oldest newest most voted

Solution via linear algebra modulo 14282531:

M = Matrix( Zmod(14282531), [[9677035, 7162589], [5302728, 8472081]])
print( M.solve_right( vector([4477085, 11061226]) ) )
more

The algorithm is horrible ! From the documentation :

Warning

The current implementation splits the modulus into prime powers, then naively enumerates all possible solutions (starting modulo primes and then working up through prime powers), and finally combines the solution using the Chinese Remainder Theorem. The interface is good, but the algorithm is very inefficient if the modulus has some larger prime factors! Sage does have the ability to do something much faster in certain cases at least by using Groebner basis, linear algebra techniques, etc. But for a lot of toy problems this function as is might be useful. At least it establishes an interface.

And, in the ticket documenting its initial implementation, William Stein confesses its youthful sin :

WARNING:
Currently this naively enumerates all possible solutions.
The interface is good, but the algorithm is horrible if the
modulus is at all large!   Sage *does* have the ability to do
something much faster in certain cases at least by using
the Chinese Remainder Theorem, Groebner basis, linear algebra
techniques, etc.  But for a lot of toy problems this function
as is might be useful.  At least it establishes an interface.

Indeed, trying to reproduce your problem on a moderatly fast laptop, I haven't got an answer in 20 minutes...

EDIT : in fact, this ended up in a crash :

sage: %time Sol = solve_mod([9677035*u + 7162589*v == 4477085 ,5302728*u + 8472081*v == 11061226], 14282531)
Killed

Process Sage exited abnormally with code 137

Since

sage: p = 14282531 ; p.is_prime()
True

a better solution is to work directly in the ring of polynomials of the finite field GF(p) :

sage: R.<x, y> = GF(p)[]
sage: J = R.ideal(9677035*x + 7162589*y - 4477085 ,5302728*x + 8472081*y - 11061226)
sage: J.dimension()
0

Your problem has a finite number of solutions ; they are

sage: %time J.variety()
CPU times: user 38.7 ms, sys: 23.7 ms, total: 62.4 ms
Wall time: 87.9 ms
[{y: 3263554, x: 5754431}]

in fact a unique solution (obtained in a reasonable time...).

HTH,

EDIT :

Following @Max Alekseyev's hint, one can indeed use Pari/GP. The problem is to get Pari/GP's column vectors. Sage doesn't really have row and column vectors, just vectors (which, IMHO, is mathematically sounder that "row" and "column" vectors, which are a figment of programmer's imaginations...). In Sage, a n-dimensional "column" vector is but a (n, 1) matrix .. which is not accepted by Pari nor GP as a "column" vector.

The best I can come up with is the following horror :

sage: %time PSol= pari("matsolvemod(%s,%s~, %s~)"%(M._pari_init_(), vector([p]*2)._pari_init_(), B._pari_init_())) ; PSol
CPU times: user 244 µs, sys: 25 µs, total: 269 µs
Wall time: 273 µs
[5754431, 3263554]~
sage: PSol.sage()
[5754431, 3263554]

which is indeed faster (and more general) than the GF(p) solution (nor all moduli ahave to be equal), and the unicity can be checked with :

sage: %time pari("matsolvemod(%s,%s~, %s~, flag=1)"%(M._pari_init_(), vector([p]*2)._pari_init_(), B._pari_init_()))
CPU times: user 271 µs, sys: 0 ns, total: 271 µs
Wall time: 276 µs
[[5754431, 3263554]~, [14282531, 0; 0, 14282531]]

Don't ask me what is the last part of this answer... ;-).

HTH,

more

Btw GP provides a function gp.matsolvemod

( 2022-10-27 22:35:25 +0100 )edit

@Max Alekseyev : I can't find a way to use this function from Sage. Could you illustrate ? And possibly turn this illustration to an answer for the benefit of future ask.sagemath.org (per)users ?

( 2022-10-28 10:39:20 +0100 )edit

OK,i have found the method,using matrix to solve this question.

more

@charleyhoot : You should post your solution, for the benefit of future ask.sageath.org (per)users...

( 2022-10-27 22:35:38 +0100 )edit