18.310 Exam 2: Due Wednesday November 24 -- open book take home



1.  Use a set up for taking fft’s based on 16th roots of unity to multiply a 32 decimal digit number by a 36 decimal digit number.

How? Do the computation four times mod each of 4 different primes, namely 257, 97 193 and 577, which each have 16th roots of unity.

Also break each number into blocks of four decimal digits each, and use them as your coefficients.

So first find primitive 16th roots of unity mod each, find the transforms, of the products of the transforms for each prime, divide by 16 mod each, and then put all the results together.
perform the carrying necessary to make the answer in standard form; (you can do this as with one decimal digit coefficients but doing it  mod 10000 instead of mod 10.)

hint: the setup you used for homework should work here, you need to use different primes and different roots however,

hint 2: you put results together by using the following rule:

If x is congruent to A mod C and to B mod D for relatively prime C and
D, with C<D, then x is congruent to (A + (B-A)*C*(the inverse of Cmod D)) mod  

Do it for the numbers 25987654321098765432109876543210  and 123456987654321098765432109876543210.


2. Your option: either

Factor the number 93333323, or explain in your own words the elliptic curve method of factoring.


3. Create an RSA code and a decoder and encoder that work on a spreadsheet using N=1201*77713.


4. Prove that the order of a subgroup of a finite group G is a factor of the order of. G. also prove Euler’s formula: that the number of edges, E, vertices, V,  and regions, R, and connected components C  in a drawing of a graph in the plane without crossing edges obeys R+V = E + C + 1.


5. Solve the following linear program on a spreadsheet:


Maximize: x1 + x2 + x3 + x4


Subject to the constraints:


3x1 – 2x2 + x3 – x4 <= 2

x1 + 2x2 – x3 + x4 <=7

x1 – x2 – x3 <= 1

x3 + x4 <= 2


all x’s are positive. Give the optimal objective function and the values of the x/s that achieve it. State the dual problem and give its solution as well.