1. The Sieve of Eratosthenes is a method used to compute all primes less than N. We begin by making a table of integers 2 to N. We ?nd the smallest integer, i, that is not crossed out, print i, and cross out i, 2i, 3i, .... When i > √N, the algorithm terminates. What is the running time of this algorithm?
2. Show that X62 can be computed with only eight multiplications.
3. Write the fast exponentiation routine without recursion.
4. Give a precise count on the number of multiplications used by the fast exponentiation routine. (Hint: Consider the binary representation of N.)