You may turn these problems in electronically to the drop boxes or on paper. If you do your problems electronically, please use a proper equation editor rather than trying to fake the mathematical symbols!

Drop box submissions are due at midnight on the due date. Paper submissions are due in class or in the box outside my office by 5:00 p.m.

Show your work on all problems.

I will give some partial credit, especially on multi-part problems.

 

1. [4 points.] If n is an odd integer, prove that there is a one-to-one correspondence between factorizations n=ab and expressions n=s²-t².
2. [1 point.] Factor 5459 using the Fermat factorization method.
3. [2 point.] Factoring hn by the Fermat factorization method, where h is a small positive integer, is sometimes easier than factoring n by this method. (This is part of the idea of the quadratic sieve method. Factor both 901 and 3 * 901 = 2703 by the Fermat factorization method and compare the number of steps.
4. [2 points.] In the quadratic sieve we used numbers of the form x²mod n. The best way to do this is in fact to compute

Q(a) = (floor(sqrt(n))+a)²-n

for x=floor(sqrt(n))+a.  Show that if a is "small", then Q(a) is the same as x²mod n  (Including that 0<=Q(a)<n.)
 
5. [4 points.]  Using the notation of the previous problem, show that if m divides Q(a), then m divides Q(a+km) for every integer k.  We used this fact in the quadratic sieve also.
   
   
   

The following problems are from the "Handout to accompany RSA".
6. [2 points.] Question 13.
7. [4 points.] Question 14.
8. [6 points.] Question 16.
9. [2 points.] Question 18.
10. [2 points.] Question 19.
11. [2 points.] Question 20.

The following problems are from your textbook.
12. [2 points.] Problem 8.8.
13. [4 points.] Problem 8.9. You really can do this without a computer if you are clever!
14. [6 points.] Problem 9.13. Be very specific.