| Let A ∈ Q [z]nxn be a matrix of polynomials and b ∈ Q [z]n be a vector of polynomials. Let m(z) = phi k[z] be the kth cyclotomic polynomial. We want to find the solution vector x ∈ Q [z]n such that the equation Ax = b mod m( z) holds. One may obtain x using Gaussian elimination, however, it is inefficient because of the large rational numbers that appear in the coefficients of the polynomials in the matrix during the elimination. In this thesis, we present two modular algorithms namely, Chinese remaindering and linear p-adic lifting. We have implemented both algorithms in Maple and have determined the time complexity of both algorithms. We present timing comparison tables on two sets of data, firstly, systems with random generated coefficients and secondly real systems given to us by Vahid Dabbaghian which arise from computational group theory. The results show that both of our algorithms are much faster than Gaussian elimination.;Keywords: modular algorithm; cyclotomic field; Chinese remaindering; p-adic lifting; rational reconstruction. |
