Avalg homework 1 fall 2002

This homework is due November 19 at 10.15. It can be delivered to Stefan or Isaac personally at their offices or put in their mail slot at the department. It can also be given to Stefan in connection with one of the lectures. Solutions handed in late are not accepted and will not be graded.

Some forms of collaboration are allowed and required. The size of a group of collaboration should be two people. The group should hand in only one solution and for each problem it should be clearly marked which of the members have contributed.

The homework will be returned on Thursday and Friday November 21-22. There will be a list outside of Stefan's office where you can book a time. All members of the group must be present when the homework is returned.

I do not consider the set of problems below easy. Thus a performance of getting half the total score on this set is at least equivalent to the grade 4 on this subset of the course. Credit may be given for partially solved problems.

1. Multiplication (60p)
Your task is to implement multiplication algorithms for large integers. You should implement both the schoolbook algorithm and Karatsuba's algorithm. The multiplication algorithms should be implemented from scratch using either C or Java. However, you may use standard libraries, such as Java's BigInteger, for reading and converting numbers from and to decimal form. Compare the running times of the algorithms experimentally. (Optionally, compare the running time of your algorithms with the algorithm based on FFT in the textbook by Goodrich and Tamassia.)

  • The code should follow Java Code Conventions (or similar C conventions). IndexTreeList.java is intended to be a good example.
  • Your code should be well documented and easy to use. The documentation could be generated using javadoc.
  • The API should be easy to understand and use. Only include necessary methods and carefully design your data types.
  • The code should be robust. Erroneous parameters and function calls should be handled gracefully.
  • The code should be efficient.
  • The code must, of course, be correct. Include code for testing all functions. I highly recommend the following article. You don't have to use the software tool described in the article but the ideas are still very useful.

2. Discreet Fourier transform (20p)
Compute the discrete Fourier transform of the vector [5, 4, 3, 2] using arithmetic modulo 17 = 24 + 1. Use the fact that 5 is a generator of Z*17.

3. Prime numbers (20p)
Let p be a prime such that p = 1 mod 8. Find, and prove, a formula for the number of solutions to xd = ±1 mod p where d = (p - 1)/8, (p - 1)/4, and (p - 1)/2.

4. Detect a cycle in a linked list (20p)
How can you detect a cycle in a linked list? The list is in read-only memory, you cannot mark elements, and you may only use a constant amount of extra memory. It's enough to giva a high level description of your algorithms.

a) Try to find an algorithm which uses as little extra memory as possible.

b) Try to find an algorithm which is as fast as possible.

5.Lemma 4.2 (20p)
Prove Lemma 4.2.

6. Cracking RSA (30p+30p)

a) Using any free software, write a program to crack RSA. You may use at most 5 minutes of user time on a work station and you must be able to convincingly demonstrate that your program is working. The bigger the keys you manage to crack, the more points are awarded.

b) Is it possible to crack RSA without factoring? What if you have no extra information except the public key and the encrypted message? What if you have some extra information?

Stefan Nilsson