On Jul 18, 2008, at 1:05 PM, Stefano Maggiolo wrote: > I'd like to solve some systems of linear equation with coefficients > and unknown in the integers modulo Z_n. I'm aware of solve_mod, but: > 1. it's slow; > 2. returns a list of solutions and not a list of generators/relations > for the solutions. > > Is there anything better suited for me?
Yes, there's certainly faster ways about going about this, though they might take a bit more work. I'm not sure what the equations you're trying to solve look like, but I would try using linear algebra over Z_p for each p dividing n, and then use Chinese Remainder and Hensel lifting. to lift to solutions mod n. For example, to solve the following mod 1147 = 31*37 5x + y = 1 x + 4y = 2 sage: M = matrix(2, 2, [5,1,1,4]); M [5 1] [1 4] sage: M.change_ring(GF(31)) \ vector([1,2]) (5, 7) sage: M.change_ring(GF(37)) \ vector([1,2]) (4, 18) sage: crt(5, 4, 31, 37) % 1147 966 sage: crt(7, 18, 31, 37) % 1147 906 gives the solution x=996, y=906. If M were singular for any of the divisors of your n, then you would get a lift of each solution. - Robert --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
