18.310 Assignment 8: Factoring Due Monday November 8 -- Wednesday November 10, 2004



  1. Factor the number 94404047 by the function iteration or tortoise and hare method on a spreadsheet. How many steps do you expect before the hare catches the tortoise? (rough guess) How many steps does the tortoise actually take before you find a factor?


  1. Digest the quadratic sieve method and then sit down and describe it in your own words. Write down an explanation of it that you think would make sense to someone who never heard of it but is reasonably intelligent.


  1. Write down an equation in x and y that defines an elliptic curve for which y = 1, x = 1 is a solution. If we call this solution A, find the solution which is A squared mod 94404047. Call this solution. B. Then find the solution which is A-1 and also A B (by which we mean find the reflection about the x axis of the third solution on the line joining A and B.)