Introduction to Computational Number Theory and Algebra
G22.3033012 Fall 2003
Instructor: Victor Shoup

Phone: (212) 9983511

Office: 511 WWH

email: shoup AT cs DOT nyu DOT edu
Lectures: Tuesdays and Thursdays, 1:152:45pm, room 513 WWH
Text: A Computational Introduction to Number Theory and Algebra,
by
the instructor.
Available on line.
Printed versions are available for purchase at Unique Copy,
at 252 Greene Street.
Grading:
There will be a few problem sets.
Course description:
We shall study algorithms for computing with integers, polynomials,
and other algebraic objects.
These algorithms play an essential role in the technologies
underlying modern systems for storing and transmitting data,
especially in the areas of error correcting codes and cryptography,
and we shall study some of these applications as well.
As for mathematical prerequisites, the lectures
should be easily accessible to students who have had
undergraduate courses in abstract algebra, linear algebra,
and probability theory;
however, the textbook for the course develops all
of the necessary mathematics from scratch,
and so students with some gaps in their mathematical background
can fill any such gaps by reading the textbook.
As for computer science prerequisites, all that is
assumed is a basic understanding of programming, as well as some
experience in algorithm analysis, roughly at the level
of an undergraduate course on algorithms and data structures.
Course Outline (tentative)

Arithmetic with large integers and applications

Basic arithmetic

Fast exponentiation

Euclid's algorithm

Chinese remaindering

Rational reconstruction (including Chinese remaindering with errors)

The distribution of primes

Chebyshev's theorem

Bertrand's postulate

Mertens' theorem

The prime number theorem

Probabilistic algorithms for generating prime numbers and
random factored numbers

Probabilistic primality testing

Generators and discrete logarithms

Finding generators mod p

Simple algorithm for discrete logarithms mod p

Quadratic residues and quadratic reciprocity

The Legendre and Jacobi symbols

Quadratic reciprocity

Computing square roots mod p

Subexponentialtime algorithms for discrete logarithms and factoring

Smooth numbers

Simple subexponentialtime discrete logarithms

Simple subexponentialtime factoring

Practical improvements (the quadratic sieve)

Polynomial arithmetic and applications

Basic arithmetic

Fast exponentiation

Euclid's algorithm

Chinese remaindering/polynomial interpolation

Secret sharing

Rational reconstruction (including polynomial interpolation with errors
and linearly generated sequences)

Algorithms for finite fields

Constructing irreducible polynomials

Factoring polynomials

Deterministic primality testing

The new AKS primality test