up previous next
|
CoprimeFactorBasis --
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 of values
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 also called "GCD-free bases".
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]);
[x*y^2]
|