E-Book Overview
These notes record seven lectures given in the computer algebra course in the fall of 2004. The theory of suhrcsultants is not required for the final схаш due to its complicated constructions.
E-Book Content
Lecture Notes on Computer Algebra Ziming Li
Abstract These notes record seven lectures given in the computer algebra course in the fall of 2004. The theory of subresultants is not required for the final exam due to its complicated constructions.
1
Chinese remainder algorithm
1.1
Modular arithmetic
Let m be a positive integer greater than one. We discuss basic operations in Z/(m). The elements in Z/(m) can be represented in two ways: • {0, 1, . . . , m − 1} (nonnegative representation); •
a ∈ Z | −m 2 0 over F . Let r be a residue in F [x]/(M ). For a given k ∈ {0, . . . , n}, compute a, b ∈ F [x] such that a ≡ b r mod M, gcd(b, M ) = 1, deg a < k,="" deg="" b="" ≤="" n="" −="">
(6)
The condition gcd(b, M ) = 1 implies that the polynomial b is invertible in F [x]/(M ), so that ab−1 ≡ r mod M . Recall some properties of the extended Euclidean algorithm. For two polynomials A1 , A2 ∈ F [x] with deg A1 ≥ deg A2 > 0. Applying the extended Euclidean algorithm to A1 , A2 , we get the following four sequences 1. Remainder sequence: A1 , A2 , A3 , · · · , As with Ai = rem(Ai−2 , Ai−1 ), for i = 3, 4, . . . , s, and rem(As−1 , As ) = 0. 2. Quotient sequence: Q3 , . . . , Qs with Ai−2 = Qi Ai−1 + Ai . 3. The first co-sequence: U1 = 1, U2 = 0, U3 , . . . , Us , and the second co-sequence: V1 = 0, V2 = 0, V1 , . . . , Vs , with Ui A1 + Vi A2 = Ai
6
for i = 1, . . . , s.
Let deg Ai = di for i = 1, . . . , s. We have the following degree sequences: deg Qi = di−2 − di−1 , deg Ui = d2 − deg Ai−1 and Vi = d1 − deg Ai−1 , where i = 3, . . . , n. In addition gcd(Ui , Vi )