[McGill] [Math.Mcgill] [Back]

USRA Summer Seminar

Suggested Topics




The following gives a list of possible topics for your summer project. You are also free to come up with your own choice as well.

You should fix yourself on a topic, and let me know what it is, as soon as possible. To avoid duplications, I will post your choices on this site, as soon as they are made. Project topics will be assigned on a first-come, first serve basis: I expect that some of the more popular topics will be chosen first, so it is in your interest to make a fast decision!


Primality testing: Given a large integer N, (of a hundered or so digits, say) how can one determine that it is prime? The naive approach, trial division, requires about N or the square root of N operations, which is very expensive. Remarkably, there are algorithms that decide whether N is prime in a power of log(N) operations, which is much better. Give a presentation of some of the best known algorithms: the algorithm of Miller and Rabin, and the more recent algorithm of Agrawal et. al. which is the first prvably polynomial-time algorthm for primality testing.

References:
Miller, Gary L. Riemann's hypothesis and tests for primality. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). J. Comput. System Sci. 13 (1976), no. 3, 300--317.
Carl Pomerance, Recent developments in primality testing, Mathematical Intelligencer 3, no. 3 (1981) 97-105.
Manindra Agrawal et. al. Primes is in P. Can be downloaded at
http://www.cse.iitk.ac.in/users/manindra/primality.ps.


Lenstra's factorization algorithm based on elliptic curves over finite fields.

Reference:
Lenstra, H. W., Jr. Factoring integers with elliptic curves. Ann. of Math. (2) 126 (1987), no. 3, 649--673.


Elliptic curve cryptosystems.
Reference.
Koblitz, Neal. A course in number theory and cryptography. Second edition. Graduate Texts in Mathematics, 114. Springer-Verlag, New York, 1994.


Shor's factorization algorithm based on "quantum computers". Recently a probabilistic algorithm was discovered for factoring integers in polynomial time on a quantum computer, a computing device which uses elementary particles to store information and exploits the peculiar properties of these particles (as described by quantum mechanics) to achieve a fast factorization algorithm. This discovery has caused alot of excitement among number theorists, theoretical computer scientists, and physicists, and represents a remarkable confluence of the three subjects. This would be a good topic for someone who already has some background in physics (and the rudiments of quantum mechanics in particular).

Reference:
Peter Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing Volume 26, Number 5 pp. 1484-1509.


Dirichlet's Theorem on primes in arithmetic progressions.
Reference.
Serre, J.-P. A course in arithmetic. Translated from the French. Graduate Texts in Mathematics, No. 7. Springer-Verlag, New York-Heidelberg, 1973.


The prime number theorem.
Reference.
Davenport, Harold. Multiplicative number theory. Second edition. Revised by Hugh L. Montgomery. Graduate Texts in Mathematics, 74. Springer-Verlag, New York-Berlin, 1980.


Continued fractions and ergodic theory.
Reference.
Khintchine, A. Ya. Continued fractions. Translated by Peter Wynn. P. Noordhoff, Ltd.,


Euler's calculation of zeta(2k) and its developments.
Reference
Dunham, William. Journey through genius. The great theorems of mathematics. Penguin Books, New York, 1991.

Koblitz, Neal. p-adic numbers, p-adic analysis, and zeta-functions. Second edition. Graduate Texts in Mathematics, 58. Springer-Verlag, New York-Berlin, 1984.

Iwasawa, Kenkichi. Lectures on p-adic L-functions. Annals of Mathematics Studies, No. 74. Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1972.


The irrationality of zeta(3).
Reference.
van der Poorten, Alfred. A proof that Euler missed... Apery's proof of the irrationality of zeta(3). An informal report. Math. Intelligencer 1 (1978/79), no. 4, 195--203. Groningen 1963.


The theory of partitions.
Reference.
Andrews, George E. The theory of partitions. Reprint of the 1976 original. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1998.



Schoof's algorithm for counting the number of points on an elliptic curve over a finite field.
Reference.
Schoof, Rene. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp. 44 (1985), no. 170, 483--494.


Computing the zeroes of the Riemann zeta-function.
Reference.
Turing, Alan. M. Some calculations of the Riemann zeta-function. Proc. London Math. Soc. (3) 3, (1953). 99--117.

Odlyzko, Andrew M. Analytic computations in number theory. Mathematics of Computation 1943--1993: a half-century of computational mathematics (Vancouver, BC, 1993), 451--463, Proc. Sympos. Appl. Math., 48, Amer. Math. Soc., Providence, RI, 1994.


p-adic numbers.
References.
Koblitz, Neal p-adic numbers, p-adic analysis, and zeta-functions. Second edition. Graduate Texts in Mathematics, 58. Springer-Verlag, New York-Berlin, 1984.

Gouvea, Fernando Q. p-adic numbers. An introduction. Second edition. Universitext. Springer-Verlag, Berlin, 1997.


Cubic and biquadratic reciprocity.
References.
Ireland, Kenneth; Rosen, Michael. A classical introduction to modern number theory. Second edition. Graduate Texts in Mathematics, 84. Springer-Verlag, New York, 1990.