Introduction to Computational Number Theory and Algebra
G22.3033002 Spring 2006
Instructor: Victor Shoup

Phone: (212) 9983511

Office: 511 WWH

email: shoup@cs.nyu.edu
Mailing List

It is important that you subscribe to the class mailing list,
in order to receive announcements.

To subscribe to the list, follow
these instructions.
Lectures: Thursdays, 56:50pm, room 513 WWH
Text: A Computational Introduction to Number Theory and Algebra,
by
Victor Shoup.
Available on line,
or you can buy a hardcover copy
from an
online book retailer.
Additional Material
Grading:
There will be some problem sets.
Problem sets:

Problem Set 1 (Due Feb. 9):
 Chapter 1: 8
 Supplement to Chapter 2 (above): 1, 2, 3
 Chapter 3: 26, 27, 28, 29, 30

Problem Set 2 (Due Feb. 23):

Chapter 4: 1, 2, 5, 7.

Chapter 5: 1, 2.

Problem Set 3 (Due March 23):

Chapter 8: 22, 25, 26, 27.

Chapter 9: 6, 10, 22, 23, 28, 29, 30, 31, 32, 33, 43.

Problem Set 4 (Due April 6):

Chapter 6: 27.

Chapter 7: 26.

Chapter 10: 6, 14.

Chapter 11: 59 (these form one big problem), and 10.

Problem Set 5 (Due April 27):

Chapter 13: 2, 4, 7, 8.

Chapter 15: 14.

Chapter 16: 1, 4.

Extra Credit (Due April 27):

Chapter 17: 28, 29, 30, 31, 32, 33, 34, 35.
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.
I'd like to spend most class time focusing
on number theory and algorithms.
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.
It is also assumed that students have
some basic background in algorithm design and analysis.
Course Outline (tentative)

Some basic number theory

Fundamental theorem of arithmetic

Congruences

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

Algebra Review

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

Linear Algebra Review

Modules and vector spaces

Matrices

Subexponentialtime algorithms for discrete logarithms and factoring

Smooth numbers

Simple subexponentialtime discrete logarithms

Simple subexponentialtime factoring

Practical improvements (the quadratic sieve)

Algebra Review: More Rings

Polynomial arithmetic and applications

Basic arithmetic

Fast exponentiation

Euclid's algorithm

Chinese remaindering/polynomial interpolation

Secret sharing

Linearly generated sequences

Finite Fields

Algorithms for finite fields

Constructing irreducible polynomials

Factoring polynomials

Deterministic primality testing

The new AKS primality test