Course Handouts
Course handouts will be posted after or
in advance of classes. These will be approximately what are
presented in class, though there may be material presented in
class which is not here and vice versa.
 Script 1: Introduction and basic polynomial arithmetic. script01.mws (Maple worksheet).
 Save the maple worksheet and open it under Maple (available on
student.cs machines)
 Script 2: Basic algebraic operations. PDF.
 Readings (from text): Chapter 2
 Script 3: Evaluation, Interpolation and Multiplication of Polynomials. PDF.
 Readings (from text): Chapter 8.1
 Code for Patterson & Stockmeyer's algorithm (patstock.mpl) and worksheet to drive it (patstockeval.mw)
 Script 4: The Discrete Fourier Transform. PDF.
 Readings (from text): Chapter 8.2
 Code for FFT (fft.mpl), FFT Benchmark (fftbench.mpl), FFT polynomial muliplication with timing (fftmul.mpl), FFT polynomial multiplication worksheet (fftmul.mw).
 Script 5: Polynomial division and algebraic Newton interation. PDF.
 Readings (from text): Chapter 9.1
 Script 6: Chinese remainder algorithm. PDF.
 Readings (from text): Chapter 5
 Script 7: Fast evaluation and interpolation. PDF.
 Readings (from text): Chapter 10
 Script 8: Integer matrix determinant and nonsingular rational system solving. PDF.
 Readings (from text): 5.5
 Script 9: The resultant and a modular gcd algorithm in Z[x].
PDF.
 Readings (from text): 6.16.4
 Script 10: Factoring polynomials over finite fields. PDF.
