Random and Prime: A Computational Exploration of Number Theory
This course is a journey analogous to space exploration. Our infinite cosmos will be the set of natural numbers. Our exploratory rocket ships will be computer programs of our own design. The planets possibly bearing alien life forms are different classes of prime numbers.
More literally, this course is a research driven introduction to elementary number theory and its application to computer-network security. We will write a series of computer programs of increasing sophistication whose aim will be to identify patterns among prime numbers. In some cases we will search for empirical evidence in support of well established theories (for example, the Prime Number Theorem), in other cases we will be analyzing and interpreting data in an effort to discover new theorems and their applications (for example, regarding "safe primes").
We will pose philosophical questions regarding the nature of modern mathematics (and, therefore, computer science). For instance, to what extent can a computer be used to prove theorems? Is there a fundamental difference between theorems that seems to require "insight" for their proof (for example, using a non-constructive proof by contradiction to establish the infinitude of primes) as opposed to those that correspond to more algorithmic arguments?
We will investigate what it means to be random. Can randomness be generated by an algorithmic process? We will see examples of how some problems that appear the be very difficult may be solved quickly using random numbers with the caveat that the answer we get is only "probably" true. We discuss the philosophical and practical implications of this approach. In particular, we will contrast on the one hand, the ease with which random numbers can be harnessed to discover primes, and on the other, the challenge of finding divisors of composite numbers. We will also consider the Web-shaking implications if the latter problem turns out to be less difficult than it appears.
Topics in elementary number-theory include: unique factorization, modular arithmetic, Euler's phi function, Fermat's Little Theorem, primitive roots, quadratic residues and Gauss' Law of Quadratic Reciprocity. Cryptology topics include: Diffie-Hellman key exchange, RSA encryption, El Gamal signatures, pseudorandom number generators, zero-knowledge proofs, and applications of these to electronic voting and digital currency. Algorithmic topics include: modular exponentiation, probabilistic prime testing, factorization and discrete logarithms, and the theory of NP-completeness.
There is no one single prerequisite for this course, but students should have either at least one semester of programming experience (preferably in Python; but C, C++, or Java should be fine) or some experience with mathematical proof (for example, one semester of college-level mathematics such as Discrete Mathematics). Cross listed with Mathematics. Intermediate, permission of instructor required.