Fast Polynomial Multiplication with DFT/FFT implementation, RSA Encryption, Image compression (20 Marks) THE FOLLOWING ASPECTS WERE TO BE COVERED WHILE EXECUTING THE PROJECT
1]Implement 1-D DFT on coefficient vectors of two polynomials A(x), B(x) by multiplication by Vandermonde Matrix O(n2)-Complexity {Done}
2] Implement 1-D FFT on the same vectors of A(x) and B(x). Ensure above two steps produce same results O(n log n)-Complexity{Done}
3] Pointwise multiply results of Step (ii) to produce C(x) in P-V form {Done}
4] RSA encrypt (128-bit, 256-bit and 512-bit), with public key, the C(x) in PV form, for transmission security and decrypt with a private key and verify. {Done}
5] Implement 1-D Inverse FFT (I-FFT) on C(x), in PV form (Interpolation) to get C(x) in Coefficient form (CR) Polynomial. {Done}
6] Verify correctness of C(x), by comparing with the coefficients generated by an Elementary “Convolution for Loop” on the Coefficients of A(x) and B(x) {Done}
7] Implement a 2-D FFT and 2-D I-FFT module using your 1-D version (This just means, applying FFT on the Rows First and Columns Next on M x N matrix of numbers !!) {Done}
8] Verify you of Step (vii) correctness on a Grayscale matrix (which has random integer values in the range 0-255; 255 → White & 0 → Black)) {Done}
9] Apply your 2D-FFT on TIFF/JPG (lossless) Grayscale image and drop Fourier coefficients below some specified magnitude and save the 2D- image to a new file. {Done}
10] Apply 2D I-FFT, on the Quantized Grayscale image and render it to observe Image Quality. {Done}