up previous next
CRTPoly

Chinese Remainder Theorem on polynomial coefficients

Syntax
CRTPoly(f1: RINGELEM, M1: INT, f2: RINGELEM, M2: INT): RECORD

Description
This function combines residue-modulus pairs (f1,M1) and (f2,M2) using the Chinese Remainder Theorem to produce a single residue-modulus pair (f,M) such that f is a polynomial (with coefficients in QQ ), f = f1 mod M1 and f = f2 mod M2 , and all coefficients of f are smaller than M . The moduli M1 and M2 must be coprime (hence M = M1*M2 ).

Example
/**/ use QQ[x,y];
/**/  CRTPoly(x-y, 331, x+y, 10093);
record[modulus := 3340783, residue := x +676232*y]
/**/ mod(676232, 331);
330
/**/ mod(676232, 10093);
1

See Also