MA 479 / CSSE 479: Cryptography
Homework 6 problems inspired by Computer Science

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

• Use any language and environment you wish. Please check with me if you have any questions about what features of the language or environment you may use. In particular, please do not use pre-packaged matrix calculation routines.
• The user interface is up to you.
• Turn in the source and object code of the program, and any supporting materials, to these drop boxes.
• Make sure you include clear instructions on how the code is to be run! Most of the points will be determined based on whether the program performs correctly on test cases.

The non-programming problems you may turn in to the drop boxes or on paper.

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.

1. [4 points.] Write a computer program that implements fast exponentiation (successive squaring) modulo n.

2. [4 points.] Write a computer program that implements the Miller-Rabin algorithm for a user-specified n. The program should allow the user two choices: (1) specify a possible witness a to test using the Witness subroutine, or (2) specify a number s of random witnesses for the Miller-Rabin test to check.

   The RSA cryptosystem needs a pair of large primes. The algorithm acquires them by:

   1. Choose a large number randomly.
   2. See if it is prime. If so, done. If not, return to Step 1.

   This is an effective approach because:

   • Testing for primality can be done quickly, if we are willing to admit a small possibility of error.
   • There are so many primes that the random choices will stumble upon one quickly.
   This first problem below investigates the former claim; the second problem investigates the latter claim.

3. [16 points.] Miller-Rabin is correct and fast because:
   • The Witness function returns true if and only if n is not prime.
   • If Witness(n, a) returns true, we say that a is a witness for the non-primality of n.
   • For any odd non-prime n, there are at least 3(n-1)/4 witnesses to its non-primality.
   • If n is prime, then Miller-Rabin will definitely say prime.
   • If n is not prime, then Miller-Rabin will erroneously say prime with probability less than ( ¼ ) ^s.

   Provide empirical evidence for the truth of each of the above claims by using a procedure that is something like this:

   • Consider many integers n (as many as you can with a reasonable amount of computing time).
   • For each n, determine whether or not it is prime, by using any deterministic prime-testing algorithm you wish.
   • Apply Miller-Rabin to n.

4. [16 points.] Provide empirical evidence for the truth of the Prime Number Theorem by computing P(n) for each integer n from 2 to ... (Go as far as you can in a reasonable amount of computing time.)

   Display your results by graphing both

   P(n) n

   and

   1 log n

   on the same graph.

   You may use any algorithm you wish for primality-testing (deterministic or randomized).

5. [4 points.] Write a computer program that implements the Sieve of Eratosthenes.

6. [4 points.] Write a computer program that implements Fermat factorization. The program should report the two factors that it finds (you do not need to test to see if the numbers are prime) and the values of s and t that led to the factorization.

7. [8 points.] Write a computer program that implements Lehman's method. The program should report the two factors that it finds (you do not need to test to see if the numbers are prime) and the values of all relevant parameters that led to the factorization. (Contact me if you need a cleaner copy of the description of the algorithm.)