MA-522 Computer Algebra
Fall 2012
SAS 2102, Tue&Thu 11h55-13h10

Syllabus People Maple Projects Homeworks Reading Grading Academics

Current Announcements

  • NEW Your presentation are 20-25 minutes with an extra 5 minutes for questions during 9am-12noon on Thursday, Dec 13. If you want a specific time slot in the period, please email me the request, first come-first served.
  • NEW Your term paper is 3-5 single spaced typed pages on the material you read and presented. LaTeX article class in 12pt is acceptable. Please include a brief review/critique of what your read.
  • Some useful Maple code for Problem 2 of Homework 2: subresultant.mpl , subresultant.mws
  • On Tuesday, November 6, there is NO class.
  • Homework 2 is due on Thursday, November 15.
  • The Galois group construction of x4 - 2 tower_of_fields2.mws
  • Homework 2 is posted.
  • The rational function recovery worksheet from class BW_rat_fun.mws (corrected, so that it works).
  • Homework 1 is posted.
  • The course web sites for Fall 2009.
Old Announcements see below.

Peoples' home pages: Erich Kaltofen, Classlist

Maple programs for the course (Maple hints).

Homeworks

  • Homework 1 due Thurs Sep 27, 16h59, in my mailbox in SAS 3151.
  • Homework 2 due Thurs Nov 15, 16h59, in my mailbox in SAS 3151.
  • Homework 3, a 3-5 page term paper on your presentation.

Projects

Computer Help Resources

Syllabus

Course Outline*

Lecture Topic(s) Notes Book(s)
1. Aug 16 Administrative meeting. First algorithms: modulo n arithmetic.

GG §4.3, GG §20
2. Aug 21 Repeated squaring, RSA
3.mws
GG §4.3, GG §20
3. Aug 23 Extended Euclidean algorithm; Chinese remaindering theorem/algorithm
4.mws
GG §2; §3; §5.4
4. Aug 28 Hermite elimination; analysis of Euclid; Newton and Lagrange interpolation;

GG §3.3; §4.5; §5.2
5. Aug 30 Distribution of primes; use of interpolation/CRA.
[Kaltofen and Villard 2004, p. 112]

6. Sep 4 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
7. Sep 6 Pollard rho; birthday paradox
Pollard rho code: pollard_rho.mpl, pollard_rho.mws
GG §19.4
8. Sep 11 Primitive elements modulo p; computing discrete logs via baby-steps/giant steps method and Pollard rho
Teske's paper

9. Sep 13 Maple experiments of Pollard rho; Diffie/Hellman key exchange, el Gamal crypto system
discrete_log.mpl
GG §20.3 and §20.4
10. Sep 18 Fraction-free Gaussian elimination


11. Sep 20 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
12. Sep 25 Fundamental theorem on subresultants

GG §6.10 and §11.2
13. Sep 27 Unique factorization domains


14. Oct 2 Algebraic extension fields; construction of a splitting field.


Thurs-Fri, Oct 4-5 Fall Break, no class
15. Oct 9 Isomorphism of splitting fields; Galois group; separable and inseparable extensions


16. Oct 11 The Berlekamp/Massey algorithm


Mon, Oct 15, 23h59 Last day to drop the course
17. Oct 16 Norms and traces; the fundamental theorem on symmetric functions
tower_of_fields.mws, tower_of_fields.txt.

18. Oct 18 The ring of algebraic integers


19. Oct 23 Cyclotomic extensions; the infrastructure of finite fields
See ASCM 2012

20. Oct 25 Factoring polynomials over finite fields: the Berlekamp polynomial factoring algorithm; Camion's large primes method


21. Oct 30 Factoring polynomials over finite fields cont.: the distinct degree and Cantor-Zassenhaus algorithm


22. Nov 1 CanZas continued
factmodp.mws
GG §14
23. Nov 6 TBA


24. Nov 8 TBA

GG §14.8
Tues, Nov 13 ;-) Topic for class presentation must be declared at 17h
25. Nov 13 Polynomial ideals; term orders; reduction


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

GG §21
Mon, Nov 19 Approvals of topics for term papers by me are posted
27. Nov 20 Buchberger's algorithm continued
groebner.mws

Wednesday-Friday, Nov 21-23 Thanksgiving, no class
28. Nov 27 Critical pair/completion paradigm: GCD-free basis construction
[Kaltofen 85, Section 3]

29. Nov 29 Wrap-up; possible presentation


Thurs Dec 13, 9am-12:00, SAS 2102. Presentations
Requested/assigned times:
* This is a projected list and subject to amendment.

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 Erich Kaltofen. Permission to use provided that copyright notice is not removed.