dft_cyclic_polynomial.py

import cmath

def dft(x):
    """
    Computes the Discrete Fourier Transform (DFT) of the input sequence x.

    Parameters:
    x (list): Input sequence for DFT computation.

    Returns:
    list: DFT coefficients for the input sequence x.
    """
    n = len(x)
    result = []
    for k in range(n):
        sum_val = 0
        for t in range(n):
            sum_val += x[t] * cmath.exp(-2j * cmath.pi * t * k / n)
        result.append(sum_val)
    return result

def cyclic_polynomial_multiplication(a, b):
    """
    Performs cyclic polynomial multiplication of two polynomials a and b using DFT.

    Parameters:
    a (list): Coefficients of the first polynomial.
    b (list): Coefficients of the second polynomial.

    Returns:
    list: Coefficients of the resulting polynomial after cyclic polynomial multiplication.
    """
    n = len(a) + len(b) - 1
    a += [0] * (n - len(a))
    b += [0] * (n - len(b))
    A = dft(a)
    B = dft(b)
    result = [A[i] * B[i] for i in range(n)]
    result = [sum(dft_inv(result)) / n for dft_inv in [cmath.polar, cmath.rect][0]]
    return result

# Example usage
if __name__ == '__main__':
    a = [3, 2, 5, 4]
    b = [1, 2, 1, 2]
    result = cyclic_polynomial_multiplication(a, b)
    print("Cyclic polynomial multiplication result:", result)