up previous next
CoprimeFactorBasis    --    determine coprime factor base for a set of integers or ring elements


Syntax
CoprimeFactorBasis(L: LIST of INT): LIST of INT
CoprimeFactorBasis(L: LIST of RINGELEM): LIST of RINGELEM

Description
This function returns a coprime factor base for a set of integers or ring elements from a (true) GCD domain.

Given a set N = [ N_1,...N_k ] we seek a factor base G = [ G_1,...,G_s ] of pairwise coprime values such that each N_i is a product of powers of the G_j.

In general there are many different such sets G for a given set N. Such sets are sometimes called "GCD-free bases" for N.

The factor base produced by these functions may not be of least cardinality. A least cardinality base can be obtained by performing all possible GCD and exact division operations iteratively.

Example
/**/  CoprimeFactorBasis([factorial(20), factorial(10)]);
[46189, 4, 14175]
/**/  use QQ[x,y];
/**/  CoprimeFactorBasis([x^2*y^4, x^3*y^6]);
[x*y^2]

See Also