MA-522 Computer Algebra
Fall 2018
Dabney 220, Mon&Wed 1:30pm-2:45pm

Current Announcements

Old Announcements see below.

Peoples' home pages: Erich Kaltofen, Classlist

Maple programs for the course (Maple hints).


  • Homework 1 due Wed Oct 3, 16:59pm in my mailbox in SAS 3151.
  • Homework 2, Problems 1 and 2 due Mon Nov 19, 16:59pm in my mailbox in SAS 3151.
  • Homework 3, a 3-5 page term paper on your presentation.


Computer Help Resources


Course Outline*

Lecture Topic(s) Notes Book(s)
1. Aug 22 Administrative meeting. Algorithm Defined.

Robert McNaughton, Elementary Computability, Formal Languages, and Automata, Section 1.1.
2. Aug 24 First algorithms: Freivalds's matrix multiplication verification by randomization, integer and modulo n arithmetic.
Algebraic Random Access Machine (RAM) model of computation, bit complexity
KA89_slpfac.pdf, Section 3.
GG §4.3, GG §20
3. Aug 27 Repeated squaring, RSA
GG §4.3, GG §20
4. Aug 29 Extended Euclidean algorithm; Chinese remaindering theorem/algorithm
4.mws, chrem.mws
GG §2; §3; §5.4
Mon, Sep 3 Labor Day, no class
5. Sep 5 Hermite elimination; analysis of Euclid; Newton and Lagrange interpolation;
hermite.mws, lagrange.mws
GG §3.3; §4.5; §5.2
6. Sep 10 Distribution of primes; use of interpolation/CRA.
[Kaltofen and Villard 2004, p. 112]

7. Sep 12 Rational number recovery; continued fraction approximations of a rational number
[Kaltofen and Rolletschek 1989, Theorem 5.1], KR_ratrec.mpl, KR_ratrec.mws, 4.mws
GG §5.10, §5.11
Mon Sep 17, Wed Sep 19 No class (I am at ICERM)
8. Sep 24 More certificates in linear algebra: characteristic polynomial via crypto

9. Sep 26 Linearly recurrent sequences

GG §12.3
10. Oct 1 Sparse interpolation by the Prony-BCH decoding algorithm

11. Oct 3 Catch-up; Reed-Solomon decoding by rational function recovery
GG §5.8
12. Oct 8 Pollard rho; birthday paradox
Pollard rho code: new_pollard_rho.mpl, new_pollard_rho.mws
GG §19.4
13. Oct 10 Primitive elements modulo p; computing discrete logs via Shanks's baby-steps/giant steps method and Pollard rho
Teske's paper

Thurs-Fri, Oct 4-5 Fall Break, no class
14. Oct 15 Maple experiments of Pollard rho; Diffie/Hellman/Merkle key exchange, el Gamal crypto system; catch-up
GG §20.3 and §20.4
15. Oct 17 Definition of intergral domain, field of quotients; Euclidean algorithm for polynomials over a field; Sylvester resultants
sylvester.mws, sylvester.txt.
GG §25.2, §25.3 and §6.3
16. Oct 22 Fraction-free Gaussian elimination

17. Oct 24 Fundamental theorem on subresultants

GG §6.10 and §11.2
Fri, Oct 19, 23h59 Last day to drop the course
18. Oct 29 Unique factorization domains

19. Oct 31 🎃 Algebraic extension fields; construction of a splitting field.

20. Nov 5 Isomorphism of splitting fields; Galois group; separable and inseparable extensions

21. Nov 7 Norms and traces; the fundamental theorem on symmetric functions; the ring of algebraic integers

tower_of_fields.mws, tower_of_fields.txt.
22. Nov 12 Cyclotomic extensions; the infrastructure of finite fields

23. Nov 14 Factoring polynomials over finite fields: the Berlekamp polynomial factoring algorithm; Camion's large primes method

GG §14
Fri, Nov 16 Topic for class presentation must be declared at 17h
24. Nov 19 Factoring polynomials over finite fields cont.: the distinct degree and Cantor-Zassenhaus algorithm
GG §14.8
Tue, Nov 20 Approvals of topics for term papers by me are posted
Wednesday-Friday, Nov 21-23 Thanksgiving, no class
25. Nov 26 Polynomial ideals; term orders; reduction

26. Nov 28 Gröbner bases; Buchberger's algorithm

GG §21
27. Dec 3 Buchberger's algorithm continued

28. Dec 5 Critical pair/completion paradigm: GCD-free basis construction
[Kaltofen 85, Section 3]

29. Dec 7 Wrap-up; possible presentation

Friday, Dec 14, 13pm-16pm, Dabney 220 Presentations
Requested/assigned times:
* This is a previous list and I plan to rearrange it shortly, adding sparse interpolation

Textbook and Notes

I will be closely following whose sections are marked in the above syllabus by GG.

On-line information: All information on courses that I teach (except individual grades) is now accessible via html browsers, which includes this syllabus. Click on my courses' page of my resume. You can also find information on courses that I have taught in the past.

Grading and General Information

Grading will be done with plus/minus refinement.

There will be three homework assignments of approximately equal weight and one Maple programming projects. At the end of the course, each student will give a 30 minute presentation on material from the book not covered by me. A choice of topics will be provided by me. Class attendance will not be monitored in any way. If you need assistance in any way, please let me know (see also the University's policy).

Academic Standards

Late submissions: All homeworks and projects must be submitted on time. The following penalties are given for (unexcused) late submissions:

If you need assistance in any way, please let me know (see also the University's policy).

Old Announcements

©2009, 2012, 2016, 2018 Erich Kaltofen. Permission to use provided that copyright notice is not removed.