We present space and time efficient algorithms for univariate polynomial arithmetic operations over Z mod n where the modulus n does not necessarily fit into is not a machine word. These algorithms provide the key tools for the efficient implementation of polynomial resultant gcd and factorization computation over Z, without having to write large amounts of code in a systems implementation language.