function solve_modp(A, v, p)
   // Given a nonsingular A and a vector v both defined over Q, find the vector 
   // w mod p such that w*A = v (mod p).  (Returns true, w if possible, otherwise
   // returns false, v.)
   assert Type(A) eq AlgMatElt;
   assert Type(v) eq ModTupFldElt;
   assert BaseField(Parent(v)) cmpeq RationalField();
   assert BaseRing(Parent(A)) cmpeq RationalField();
   assert Degree(v) eq Degree(Parent(A));
   assert Type(p) eq RngIntElt and IsPrime(p);

   d := Degree(v);
   Fp := GF(p);

   Amodp := MatrixAlgebra(Fp,d)!A;
   vmodp := VectorSpace(Fp,d)!v;
   
   if IsSingular(Amodp) then
      print "WARNING: System is singular modulo", p;
      return false, VectorSpace(Fp,d)!0;
   end if;

   B := Amodp^(-1);
   return true, vmodp*B;
   
end function;


function CRT_vec(list)
   // input is a list of vectors of the same degree modulo various primes
   assert Type(list) eq List;
   assert #list gt 0;
   d := Degree(Parent(list[1]));
   assert d gt 0;
   M := [Characteristic(Parent(v[1])) : v in list];
   return RSpace(Integers(LCM(M)),d)!
              [ CRT([Integers()!v[i] : v in list], M) : i in [1..d] ];
end function;


function solve_mod_primes(A, v, primes)
   // like solve_modp but gives an answer modulo the LCM(primes)

   list := [* *];
   for p in primes do
      t, w := solve_modp(A,v,p);
      if t then
         Append(~list, w);
      end if;
   end for;
   return CRT_vec(list);

end function;

function solve_mod_primes_retry(A, v, w, primes)
   // w should be correct modulo a collection of prime numbers not in primes.

   list := [* w *];
   for p in primes do
      t, w := solve_modp(A,v,p);
      if t then
         Append(~list, w);
      end if;
   end for;
   return CRT_vec(list);
end function;

function RR(v)
//   assert Type(v) eq ModTupRngElt;
   lift := [];
   for x in Eltseq(v) do
      t, lift_of_x := RationalReconstruction(x);
      if not t then
         return false;
      end if;
      Append(~lift, lift_of_x);
   end for;
   return VectorSpace(RationalField(), #lift)!lift;
end function;
