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).