crt_basis(X,
xgcd=None)
Compute and return a Chinese Remainder Theorem basis for the list
X of coprime integers.
INPUT:
X -- a list of Integers that are coprime in pairs
OUTPUT:
E -- a list of Integers such that E[i] = 1 (mod X[i])
and E[i] = 0 (mod X[j]) for all j!=i.
The E[i] have the property that if A is a list of objects, e.g.,
integers, vectors, matrices, etc., where A[i] is moduli X[i], then
a CRT lift of A is simply
sum E[i] * A[i].
ALGORITHM:
To compute E[i], compute integers s and t such that
s * X[i] + t * (prod over i!=j of X[j]) = 1. (*)
Then E[i] = t * (prod over i!=j of X[j]). Notice that equation
(*) implies that E[i] is congruent to 1 modulo X[i] and to 0
modulo the other X[j] for j!=i.
COMPLEXITY: We compute len(X) extended GCD's.
-
|