18.310 Assignment 8: Factoring Due
Monday November 8 -- Wednesday November 10, 2004
- 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?
- 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.
- 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.)