__________________
FFT/DFT/NTT
Write a program that implements the Discrete Fourier Transform. It should have functions that:
-set the size N of the input signal (which will be a list of floats or pairs of floats (if complex numbers are desired)
-compute the DFT matrix M using a primitive Nth root of 1, w=e^(2*PI*i/N).
-compute sample input signals
-set a user-defined input signal
-compute the DFT of a signal (matrix multiplication)
-display a graph of the input and output (show modulus (length) and argument (angle))
-compute the character of the associated representation of the integers mod N:
-normalize M to a matrix A by dividing by the determinant
-compute the matrix powers A, A^2, A^3, ...
-compute the trace (the sum of the diagonal entries) of these powers
The trace of the NxN DFT matrix is 1 + w + w^4 + w^9 +...+w^(N-1)(N-1), the sum of the first N square powers of a
primitive Nth root of 1. Compute the traces of the first N powers of the NxN DFT matrix for N=1,2,3...20, and
plot them in the complex plane.
-Is there a pattern?
-Is the case of N prime special?
-Read about Gauss sums on the internet. Can you find a relation to your findings?
__________________
RSA
Write a program that implements the RSA public-key enryption and decryption scheme. It should have functions that:
-set the private key primes p and q and the public exponent a
-compute the private exponent b
-break up an ASCII string using small blocks (e.g., 256-bit or 512-bit numbers)
-encode integers using the public key
-decode integers using the private key
-(optional) create keys using a prime-generation algorithm
__________________
Linear codes
Write a program that implements the error-correction scheme described in class. It should have functions that:
-set the coding function, the "generator" matrix (I,L) with n columns and m rows
-encode m-bit words as n-bit words using the coding function
-determine the number of bits of error in the transmission of a word using L that can be detected
-determine the number of bits of error in the transmission of a word using L that can be corrected
-compute the parity matrix H
-compute the syndromes of n-bit words
-compute the coset decoding table (the list of error-correction vectors for the different cosets)
-corrects a string of coded n-bit words to codewords (compute the syndrome, add the corresponding error vector)