18.310 Assignment 9 Due
Monday November 15 -- Wednesday November 17, 2004
1. Set up an n=16 FFT performer on a spreadsheet mod N for any N, and
16th root of unity mod N. Get it to work.
2. Find 16th roots of unity mod 17 and mod 257. Write the
number 12345678 as a polynomial of degree 7 in the variable 10, and do the
same for 987654321. Use N=17 and also use N=257 and appropriate 16th
roots of unity to apply your calculation for each.
3. Insert the products of the resulting evaluations as inputs to another
transform, and read off the product polynomial from this (you have to reverse
things and divide the results by 16).
4. Set up a spreadsheet that does the carrying necessary to retrieve
the product from the polynomial product.
5. Set up a spreadsheet that multiplies 2 by 2 matrices by the Strassen
method.
Extra credit: do the same for 4 by 4 matrices.
Extra credit:
6. Combine the results mod 17 and mod 257 above to find the
product of the two polynomials mod(17*257).