up previous next
determine coprime factor base for a set of integers or ring elements
CoprimeFactorBasis(L: LIST of INT): LIST of INT
CoprimeFactorBasis(L: LIST of RINGELEM): LIST of RINGELEM
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.
/**/ CoprimeFactorBasis([factorial(20), factorial(10)]);
[46189, 4, 14175]
/**/ use QQ[x,y];
/**/ CoprimeFactorBasis([x^2*y^4, x^3*y^6]);