Inhoudsopgave
Advertenties
rekenkundige ring voor polynomen met een gegeven polynoom als modulus
definiëren. We kunnen bijvoorbeeld een bepaalde polynoom P(X) als P(X) = X
2
(mod X
) schrijven of een andere polynoom Q(X) = X + 1 (mod X-2).
Een polynoom P(X) behoort tot een eindige rekenkundige ring van
polynoommodulus M(X) als er een derde polynoom Q(X) bestaat, zodat
(P(X) – Q(X)) een meervoud is van M(X). Dan zouden wij schrijven: P(X) ≡ Q(X)
(mod M(X)). De laatste uitdrukking kan gelezen worden als "P(X) is congruent
aan Q(X), modulo M(X)".
De functie CHINREM
CHINREM betekent CHINese REMainder. De bewerking die bij dit commando
hoort, lost een systeem opvan twee congruenten met de Chinese Remainder
Theorie. Dit commando kan worden toegepast op polynomen en ook op hele
getallen
(functie
ICHINREM).
[uitdrukking_1, modulus_1] en [uitdrukking_2, modulus_2]. De uitvoer is een
vector met [uitdrukking_3, modulus_3], waar modulus_3 verbonden is met het
product van (modulus_1)⋅(modulus_2). Voorbeeld: CHINREM(['X+1', 'X^2-
1'],['X+1','X^2']) = ['X+1',-(X^4-X^2)]
Uitleg van de Chinese Remainder Theorie voor hele getallen
Als m
, m
,...,m
natuurlijke getallen zijn waarvan elk paar relatief priem is en
1
2
r
a
, a
, ..., a
allemaal hele getallen zijn, dan is er een heel getal x dat
1
2
r
gelijktijdig voldoet aan de congruenten: x ≡ a
x ≡ a
). Als bovendien x = a elke willekeurige oplossing is, dan zijn
(mod m
r
r
alle oplossingen congruent aan een modulus die gelijk is aan het product
m
⋅m
⋅ ... m
1
2
r.
De functie EGCD
EGCD staat voor Extended Greatest Common Divisor. Bij twee gegeven
polynomen, A(X) en B(X), produceert de functie EGCD de polynomen C(X),
U(X) en V(X), zodat C(X) = U(X)*A(X) + V(X)*B(X). Bijvoorbeeld: bij A(X) =
X^2+1, B(X) = X^2-1, EGCD(A(X),B(X)) = {2, 1, -1}. d.w.z. 2 = 1*( X^2+1')-
1*( X^2-1). Ook: EGCD('X^3-2*X+5','X') = { 5, '-(X^2-2)', 1}, d.w.z. 5 = –
(X^2-2)*X + 1*(X^3-2*X+5).
De
invoer
bestaat
), x ≡ a
(mod m
1
1
uit
twee
vectoren
(mod m
), ...,
2
2
Blz. 5-20
Advertenties
Inhoudsopgave
