Package sage :: Package rings :: Module integer_ring
[show private | hide private]
[frames | no frames]

Module sage.rings.integer_ring

The ring of rational integers
Classes
IntegerRing The ring of integers.

Function Summary
  crt_basis(X, xgcd)
Compute and return a Chinese Remainder Theorem basis for the list X of coprime integers.
  factor(n)

Variable Summary
IntegerRing Z = Integer Ring

Function Details

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.

Variable Details

Z

Type:
IntegerRing
Value:
Integer Ring                                                           

Generated by Epydoc 2.1 on Mon Jun 20 15:43:22 2005 http://epydoc.sf.net