Homework | Algorithms | Mathematica Notes| Pari GP Notes| Author's Errata| Comments & Additional Errata | Feedback form | Links
Instructor: W. Dale Brownawell
Contact info: 328 McAllister Building, telephone: 865-7104, email: wdb@math.psu.edu
Office hours: W 11-11:45, Th 10-11, and by appointment
Textbook: Factorization and Primality Testing, by David M. Bressoud, Springer-Verlag, 1989, ISBN 0-387-97040-1. (See also the author's errata.)
Supplemental Textbooks, not
required:
Cryptanalysis
of Number Theoretic Ciphers. by Samuel S.
Wagstaff, Jr, Chapman & Hall/CRC, 2003, ISBN 1-58488-153-4.
Primality Testing and Integer Factorization in Public-Key Cryptography, by Song Y. Yan, Kluwer Acad. Pub., 2004, ISBN 1-4020-7649-5
Course objectives: The purpose of this course is to introduce students to an active interface between number theory and computer science.
We will see how the seemingly simple, and certainly basic, notion of decomposition of integers into products plays a vital role in some important modern computer security schemes. We will investigate the relationship between the reliability of these schemes and the ease with which factorization can be carried out.
That will lead us to consider powerful factorization techniques which are only a generation or two behind the present state of the art (which itself is beyond the level of this course, but builds on what we will be doing in an absolutely essential way).
Prerequisites: Math 311W or CSE 260.
Programming: Students will be required to develop the ability to program in Mathematica or the wonderful open-source program Pari. Other programming languages may be acceptable, if you can carry out arithmetic with integers of arbitrary length in them and they are structured. (We will be building programs recursively, so you need to be able to call previously defined functions. Check with me before deciding to work with another language. I have to be able to both understand and run your code.)
Pari: There is a lot of information on the internet. Here is a Guide to Installation and here is a quick introduction to Pari usage from a couple of years ago by Siman Wong.
Homework & Quizzes: Except for the first week, we will have homework assigned on Friday and due the next Friday. The homework will consist partly of proofs and partly of machine implementation of algorithms, which must be amply explained. I will give (easy) 5 point quizzes on the days after the last homework is due to count in place of homework for the material presented on that day. In that way, students who attend class and pay attention will be rewarded.
Grading: The homework will be worth 100 points, the midterms will be worth 100 points each, and a final factorization project will be worth 100 points.
Course topics:
Unique Factorization, Euclidean Algorithm, and Sieving
Perfect Numbers and Euler's Generalization of Fermat's Theorem
RSA Public Key Crypto-System
Preliminary Factorization Techniques
Strong Pseudoprimes, Quadratic Residues, and Quadratic Reciprocity
The Quadratic Sieve
Primality Testing
Groups and Elliptic Curves
Elliptic Curves, Factorization, and Primality Testing
These topics correspond roughly to chapters 1 through 9 and 13, 14 in Bressoud's book, which continues to offer the best selection of topics for this course. Unfortunately, Bressoud seems to have decided not to keep his book up-to-date. We will simply not get to some of more advanced topics of Wagstaff's book. which does offer the advantage of giving a more complete and more modern overview of the area.
All Penn State policies regarding ethics and
honorable behavior, in particular
http://www.psu.edu/ufs/policies/47-00.html#49-20
and
http://www.science.psu.edu/academic/Integrity/index.html,
apply to this course.
Last modified 16 August, 2013 by W.D. Brownawell, wdb@math.psu.edu