Polynomial root finding over finite rings

The Roots function has been extended to work for a composite modulus . The roots are computed mod each prime factor of , lifted using p-adic lifting, and then combined by application of the Chinese remainder theorem. The result returned is a list of the roots and their multiplicities. Example: find the roots of the polynomial mod 72

    > Roots(x^2) mod 72;

             [[36, 2], [24, 1], [12, 1], [60, 1], [0, 2], [48, 1]]