MathematicsMATH 28 Introduction to Computational Number Theory

Prime numbers, congruences, Euclid's algorithm. The theorems of Fermat and Lagrange. The reduction of arithmetic calculations to the case of prime-power modulus. The use of quadratic residues. Computational aspects of primality testing, and factorization techniques. Students cannot receive credit for this course and course 18. High school algebra is recommended; knowledge of a computer language is useful.