Die Funktion CHINREM
CHINREM steht für CHINese REMainder (Chinesischer Restesatz). Die in
diesem Befehl kodierte Operation löst ein System von Kongruenten unter
Anwendung des Chinesischen Restesatz-Theorems . Dieser Befehl kann mit
Polynomen (wie auch mit Integer-Zahlen, Funktion ICHINREM) verwendet
werden. Die Eingabe besteht aus zwei Vektoren [expression_1, modulo_1]
und [expression_2, modulo_2]. Die Ausgabe ist ein Vektor [expression_3,
modulo_3], wobei modulo_3 aus dem Produkt (modulo_1)⋅(modulo_2)
ermittelt wird. Beispiel: CHINREM(['X+1', 'X^2-1'],['X+1','X^2']) = ['X+1',-
(X^4-X^2)]
Ansatz für das Chinesische Restsatz-Theorem für Integer-Zahlen
Wenn m
, m
,...,m
paarweise teilerfremde natürliche Zahlen und a
1
2
r
a
beliebige Integer-Zahlen sind, dann gibt es genau eine Integer-Zahl x,
r
welche gleichzeitig die folgenden Kongruenzen erfüllt: x ≡ a
), ..., x ≡ a
(mod m
(mod m
2
r
sind alle anderen Lösungen kongruent und gleich dem Produkt von m
m
.
r
Die Funktion EGCD
EGCD steht für Extended Greatest Common Divisor. Für zwei Polynome A(X)
und B(X) erzeugt die Funktion EGCD die Polynome C(X), U(X), and V(X),
sodass gilt C(X) = U(X)*A(X) + V(X)*B(X). So z. B. für A(X) = X^2+1, B(X) =
X^2-1, EGCD(A(X),B(X)) = {2, 1, -1}, d. h., 2 = 1*( X^2+1')-1*( X^2-1).
Auch EGCD('X^3-2*X+5','X') = { 5, '-(X^2-2)', 1}, d. h. 5 = – (X^2-2)*X +
1*(X^3-2*X+5).
Die Funktion GCD
Die Funktion GCD (Greatest Common Denominator – größter gemeinsamer
Nenner) dient zur Ermittlung des größten gemeinsamen Nenners zweier
Polynome oder zweier Listen von Polynomen der selben Länge. Bevor Sie die
Funktion GCD anwenden, müssen die beiden Polynome oder Listen von
Polynomen in Stack-Ebene 2 und 1 verschoben werden. Das Ergebnis ist ein
Polynom oder eine Liste, die den größten gemeinsamen Nenner der beiden
). Zusätzlich, wenn x = a eine Lösung ist, dann
r
, a
, ...,
1
2
), x ≡ a
(mod m
1
1
2
⋅m
⋅ ...
1
2
Seite 5-21