ModularAlgebraicGcdOperations(MP, MPT, MD)¶

This category specifies operations needed by ModularAlgebraicGcd package. Since we have multiple implementations we specify interface here and put implementations in separate packages. Most operations are done using special purpose abstract representation. Appropriate types are passed as parameters: MPT is type of modular polynomials in one variable with coefficients in some algebraic extension. MD is type of modulus. Final results are converted to packed representation, with coefficients (from prime field) stored in one array and exponents (in main variable and in auxiliary variables representing generators of algebrac extension) stored in parallel array.

canonicalIfCan: (MPT, MD) -> Union(MPT, failed)

canonicalIfCan(x, m) tries to divide x by its leading coefficient modulo m.

degree: MPT -> Integer

degree(x) gives degree of x.

MPtoMPT: (MP, Symbol, List Symbol, MD) -> Union(MPT, failed)

MPtoMPT(p, s, ls, m) converts p to packed representation.

pack_exps: (Integer, Integer, MD) -> SortedExponentVector

pack_exps(d, s, m) produces vector of exponents up to degree d. s is size (degree) of algebraic extension. Use together with repack1.

pack_modulus: (List MP, List Symbol, Integer) -> Union(MD, failed)

pack_modulus(lp, ls, p) converts lp, ls and prime p which together describe algebraic extension to packed representation.

pseudoRem: (MPT, MPT, MD) -> MPT

pseudoRem(x, y, m) computes pseudoremainder of x by y modulo m.

repack1: (MPT, U32Vector, Integer, MD) -> Void

repack1(x, a, d, m) stores coefficients of x in a. d is degree of x. Corresponding exponents are given by pack_exps.

zero?: MPT -> Boolean

zero?(x) checks if x is zero.