MATH3502 course
Syllabus (pdf file)
Wilf's Algorithms and Complexity (1st edition)
(1.1Mb pdf file)
Python programs to calculate extended GCDs . (Both binary gcd and Euclid.)
Examples of
calculating extended GCDs (using both extended binary gcd and extended Euclid algorithms)
Rene Schoof's paper on
primality
tests, including proof that the MillerRabin test returns "composite"
for threequarters of the bases with gcd(b,n)=1 and a proof of the
AgrawalKayalSaxena theorem that PRIME is in P. (Both for
interest  neither of these examinable.)
Martin Fürer's paper on
Fast Multiplication
using Fast Fourier transform, with a good overview of the FFT method.
Example sheet 1
Example sheet 2
Example sheet 3
Example sheet 4
Example sheet 5
Example sheet 6
Example sheet 7
Answers to Homework 1
Answers to Homework 2
Answers to Homework 3
Answers to Homework 4
Answers to Homework 5
Answers to Homework 6
Answer to Homework 6.5
Answer to Homework 6.6
Answers to Homework 7

