Content

• Applications of the Fast Fourier Transform: fast integer multiplication the fast Euclidean algorithm.
• Sparse polynomial multiplication and division using geobuckets and heaps.
• Algebraic number fields: minimal polynomials, norms, cyclotomic fields. The Trager-Kronecker algorithm for factoring polynomials in Q(alpha)[x].
• Computing multivariate polynomial GCDs over the integers:
  - Brown's dense interpolation algorithm and
  - Zippel's sparse interpolation algorithm.
• Introduction to computational linear algebra:
  - The Bareiss fraction-free algorithm for solving Ax=b over an integral domain.
  - Rational number reconstruction and solving Ax=b over Q using p-adic lifting.