Assignment 1 (Corrected)

6104: Algorithmic Number Theory

Each problem in this assignment is worth 50 points. The assignment is due by 9:30AM on May 26, 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 (if anyone) is noted at the beginning of the problem.

Problem 1. [Qin]

Use the techniques in Chapter 2 to derive an asymptotic estimate for

where is an integer. For and , use Mathematicato compute h(x,k) precisely. Present these results in a table along with the values of your asymptotic estimates.

Problem 2. [Nick]

Let R be the ring , and consider the polynomial ring R[X]. Let be the polynomial

Finally, let

1. Prove that I is an ideal in R[X].
2. Let T=R[X]/I. How many elements does T have? What are they?
3. Give addition and multiplication tables for T.
4. Is T a field? Why or why not?

Problem 3. [Jeremy]

Chapter 3, Problem 8.

1. Give pseudocode for your algorithm to solve f(x)=n. Analyze its worst case time complexity.
2. Program your algorithm in Mathematicaor other symbolic computation system. Include the Mathematicacode in your solution.
3. Use your algorithm to determine whether a solution exists to

   

   where f(x) is this polynomial