[sbi]

Two notes: factoring polynomials over finite fields isn't hard (look up the Berlekamp algorithm or Cantor-Zassenhaus for starters). Second, I believe the system you've described doesn't satisfy your property (b). Quantities such as M[1]C[0] - C[1]M[0] + M[0]^2 and C[1]M[2] - C[2]M[1] + M[1]^2 - M[0]M[2] are congruent to 0 mod p; compute them over the integers and then take the gcd. By computing enough of these you should recover the prime p. Once you have p, recovering z is very easy (e.g., take the gcd of C and C'-M, where C' is the derivative of C).