MAT 333 — Number Theory, Pseudorandomness and Cryptography
6 — 10 March 2006
Old Main 403 Canisius College: 5:00 — 8:00 pm Daily
| Instructor: |
Willem Fouché |
To download Dr. Fouché's lecture notes, click here. (.pdf)
Course Abstract: The application of ideas from number theory to the theory of error-correction codes, cryptography and the design of efficient algorithms which are based on discrete patterns which are “pseudorandom”, rank among the deepest aspects of the information sciences. The efficient simulation of randomness have incredibly interesting applications, not only to the design of information systems but also to the understanding of the intrinsic time complexity of algorithms. On the other hand, the security of information systems are frequently brought about by the apparent algorithmic time complexity of some elementary arithmetical processes. The underlying mathematics is very deep and makes substantial use, among other things, of the validity of the Riemann hypothesis over finite fields. However, the results are very accessible (in the sense of being easily understood) and it is is possible to see the power of these results for information processing even at a relatively elementary level. And, so, this will be the aim of these lectures: To discuss and analyze a number of interesting applications of number theory to information processing.
Lecture Breakdown: Five lectures of length three hours each, covering the following topics, in summary.
Lecture One:
- Basic graph theoretic terminology
- Expander graphs and their applications to coding theory and complexity
- Basic number theory: Euclidean algorithm, modular arithmetic, prime number theorem
- Structure of units modulo prime powers, primitive roots
- Cayley graphs of cyclic groups
- Pseudorandomness
- Euler’s function, Mobius inversion
- Quadratic reciprocity law, computation of Jacobi symbols
- Random constructions: Paradoxical tournaments, graphs with large girth
- Explicit constructions based on quadratic residues modulo primes
- Probabilistic algorithms: Monte Carlo versus Las Vegas
- Efficient computation of Jacobi symbols
- Principles underlying the random generation of prime numbers
- Applications to public key cryptography
- Discrete Fourier transforms
- The Weil estimate for trigonometric sums
- Applications of efficient prime number generation to public key cryptography
- Design of independent pseudorandom sequences
- Constructions of expander graphs (An overview)
- Minimally; a good background in calculus together with some exposure to linear algebra and/or discrete mathematics.
Biographical Information: Willem Fouché started off his mathematical career by studying number theory. His interest shifted to the understanding of the complexity theoretic aspects of number theory which culminated in his linking the algorithmic complexity of Diophantine equations with the descriptive complexity of a Brownian motion. In addition, he studied the recursive aspects of Ramsey theory which soon led to an interest in the role of symmetry in Ramsey theory. This turned out to have applications to topological dynamics and the conceptual aspects of pseudorandomness.
Willem Fouché’s work has been published in leading journals, such as Advances in Mathematics, Journal of the London Mathematical Society, The Journal of Symbolic Logic and Journal of Number Theory. At the moment he is putting the final touches to an invited monograph on the Wiener process for Springer. Among his former PhD students, six are active researchers in mathematics and its applications, including in computer science. The distinguished international gatherings that he has been invited to address include the 1999-2000 winter meeting of the Association for Symbolic Logic in Washington DC (January 2000) and the Prague Midsummer Combinatorial Workshop XII in July 2005. During the World Mathematical Year 2000 Fouché received a gold medal from the South African Mathematical Society (SAMS) for his achievements. He was awarded the Chancellor’s Prize for research at the University of South Africa in 2005 where he is currently the researcher holding the highest rating by the National Research Foundation of South Africa. Willem Fouchés hobbies include music, hiking and the poetry of the I Ching. He has a keen interest in ancient philosophies and how mathematics may be a reflection of human consciousness.
You may need to download the Adobe Acrobat Reader from the Adobe website if you wish to view the applications in Adobe format (.pdf).
If you have any questions regarding this process please feel free to e-mail us: webmaster@canisius.edu.