(old) fft.py

# N multiply
# I {"version": "1.0", "typing": ["List", "Sequence"]}
def multiply(a: Sequence[int], b: Sequence[int], bit: int = 64) -> List[int]:
    """Returns the multiplication of two polynomials."""
    f = f'0{bit}b'
    a_long = int(''.join(format(x, f) for x in a), 2)
    b_long = int(''.join(format(x, f) for x in b), 2)
    c_long = a_long * b_long
    total_bit = bit * (len(a) + len(b) - 1)
    c = format(c_long, f'0{total_bit}b')
    return [int(c[i:i + bit], 2) for i in range(0, total_bit, bit)]