System of (linear) equations with values in a specific ring/field.

[Stefano Maggiolo]

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?

Thanks,
Stefano Maggiolo

[Robert Bradshaw]

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

[Stefano Maggiolo]

Thanks for the answer. Sadly some of my "n" have a prime decomposition
with multiplicity. Moreover I have other requirements (some of the
unknowns should be treated as parameters) so I think I'll go for a
custom solution. If anyone is interested I could post it here when
I've reached a working state.

Stefano

[William Stein]

One can reduce solving A*x = b over ZZ/p^m by solving A*x' = b' mod (p)
for m different choices of b'. See "Dixon's p-adic lifting" algorithm for this
sort of thing... It's usually applied to solving A*x = b over QQ, but could
also be used to just solve over ZZ/p^m. This is not directly available in
Sage, unfortunately. I wish it were.

-- William