MA 479 / CSSE 490: Cryptography
Homework 5 problems inspired by Mathematics

Rose-Hulman Institute of Technology
A joint effort of the
Department of Mathematics
and the Department of Computer Science & Software Engineering
Spring term, 2002-2003

All these problems are paper-and-pencil problems, except as indicated.You will probably not find a computer program helpful on these problems. Show all steps of your work. I will give some partial credit, esepcially on multi-part problems.
  1. [1 point.] Problem 1 from this page of RSA Homework. You may use Maple as directed.
  2. [8 points.] Problem 2 from this page of RSA Homework. You may use Maple (or any similar package) as directed.
  3. [2 points.] Prove that there is a one-to-one correspondence between factorizations n=ab and expressions n=s2-t2.
  4. [1 point.] Factor 5459 using the Fermat factorization method.
  5. [1 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.
  6. [2 points.] In the quadratic sieve we used numbers of the form x2mod n. The best way to do this is in fact to compute
    7. Q(a) = (floor(sqrt(n))+a)2-n
    for x=floor(sqrt(n))+a.  Show that if a is "small", then Q(a) is the same as x2mod n  (Including that 0<=Q(a)<n.)
     
  7. [2 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 is the quadratic sieve also.



    8. The following problems are from your textbook.
  8. [4 points.] Problem 8.1.
  9. [2 points.] Problem 8.8.
  10. [2 points.] Problem 8.9. You may use Maple, but show all of your steps.
  11. [4 points.] Problem 9.1.
  12. [1 point.] Problem 9.2(a and e). Do not use Maple, but do use any tricks you can.
  13. [1 point.] Problem 9.3.
  14. [1 point.] Problem 9.4.
  15. [2 points.] Problem 9.6.
  16. [6 points.] Problem 9.7. 1 point for a yes or no answer. 5 more points for a detailed explanation of how to crack the new key.
  17. [2 points.] Problem 9.8.
  18. [1 point.] Problem 9.9.
  19. [2 points.] Problem 9.10.
  20. [4 points.] Problem 9.13. Be very specific.

  21. (Added April 28) [2 points.] Problem 3 from this page of RSA Homework. You may use Maple as directed.