University of Toronto Spring 1997

**CSC478S/2412S: Computer Algebra**

**Assignment dates updated February 5, 1997**
**Instructor**: Daniel Panario, daniel@cdf (preferable), daniel@cs

**Office hours**: T 10-11 in SF 2304A, or by appointment.

**Lectures**: TR 2 in MP 118, and F 2 in LM 157.

**Tutor**: David Neto, at478net@cdf

**Text**: K. O. Geddes, S. R. Czapor and G. Labahn,
ALGORITHMS FOR COMPUTER ALGEBRA, Kluwer, 1992.

**Language**: MAPLE, a system for symbolic
mathematical computation. Optional for project: C++.

**Prerequisities**: mathematical maturity is recommended.
Although not required, at least one undergraduate abstract
algebra course may be useful. Undergraduate courses in
discrete mathematics and in data structures could be helpful.

**Marking scheme**:

Work Handout Due Value date date A1 Jan 14 Jan 28 5 % A2 Jan 28 Feb 14 15 % A3 Feb 14 Mar 7 15 % A4 Mar 7 Mar 28 15 % A5 Mar 21 Apr 11 15 % Proj Feb 11 Apr 11 35 % ----- 100 %

**Plagiarism**: assignments and project have to be your
own work. Plagiarism
is a serious academic offense.

**Web page**:

http://www.eecg.utoronto.ca/~neto/teaching/478/index.html

**Newsgroup**: ut.cdf.csc478h

**Course goals**: This course is an introduction to basic
algebraic algorithms that are useful for computer algebra
systems. More specifically, operations like multiplication,
division, greatest common divisors and factorization are
studied over several domains including the ring of integers,
finite fields, polynomial rings, and quotient rings. The
basic tools considered include modular arithmetic, discrete
Fourier transform, Chinese remainder theorem, Newton iteration,
and Hensel techniques. Grobner bases and their applications
are taken into account. An overview of the structural
properties of finite fields covering some applications
in detail is considered.

**Course outline (some of these topics will be covered)**:

- Introduction: computer algebra systems; relation with numerical analysis; overview of MAPLE.
- Algebraic structures: groups, rings, integral domains, Euclidean domains, quotient fields, finite fields (each structure introduced when needed).
- Normal forms and data structures: the need for simplification; normal forms for polynomials; data structures for integers, rational numbers and polynomials.
- GCD algorithms: extended Euclidean algorithm and applications; Chinese remainder theorem; modular arithmetic; subresultants; generalization of the Euclidean algorithm for multivariate polynomials.
- Arithmetic: classical methods for multiplication and division of integers and polynomials; Karatsuba and Ofman's algorithm; the fast Fourier transform and fast arithmetic; Newton's iteration; arithmetic on matrices, rational functions and power series.
- Factorization of polynomials: deterministic and probabilistic algorithms over finite fields; Berlekamp's algorithm; Hensel lifting; Lenstra, Lenstra and Lovász' algorithm.
- Grobner basis: term ordering and reduction; Buchberger's algorithm; applications.
- Applications and other topics: primality testing; public key cryptography; solutions of linear equations and systems of sparse linear equations; error-correcting codes; symbolic summation and integration; etc.

**Special dates**:

Feb 17-21 reading week (no classes)Mar 7 last day to drop without penalty

Mar 28 Good Friday (University closed)

Apr 11 last lecture

Fri Jan 17 17:20:00 EST 1997