CS 6104 : Algorithmic Number Theory

Homework Assignment 5

June 19, 1998

Each problem in this assignment is worth 50 points. The assignment is due by 9:30AM on June 25, 1998. Prepare your solutions in LaTeX, preferably using this file as a starting point. You may submit your solutions in printed form or by email to cs6104@ei.cs.vt.edu. Explain your solution to each problem, including references to the appropriate theorems in the textbook.

Help is available by email as well as during my office hours. It is especially helpful to request clarification or hints by email to cs6104@ei.cs.vt.edu, so I can send the response to everyone.

The person assigned to present the solution to a problem is noted at the beginning of the problem.

Problem 1. [Hussein]

Completely factor the polynomial

over using both the Berlekamp and Cantor-Zassenhaus algorithms. You may use Mathematicato do the calculations at each intermediate step, but show the results of all the steps.

Problem 2. [Scott]

Consider the following instance of the Merkle-Hellman public-key encryption scheme:

Do the following.

1. Implement the algorithm for solving low density SUBSET SUM problems in Mathematica. Note that the lattice basis reduction algorithm is built into Mathematicaas the function LatticeReduce.
2. Show how to use the algorithm to decrypt the message

   

3. Bonus subproblem: Recover the hidden keys c and d and the superincreasing sequence

   

   used to construct the above scheme. THIS SUBPROBLEM IS OPTIONAL!