18.310 Exam 2: Due
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.
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