Ms thấy câu hỏi này rất thú vị, hy vọng có bạn sẽ cung cấp những hiểu biết sâu hơn. Có lần MS cũng đã lướt qua đọc vì được các thầy cô bên Tin nhờ dạy cho đội Tin ít số học. Thật ra việc biến đổi Fourier liên quan đến Number Theory hay như bạn trên nói việc nhân hai đa thức là rất tự nhiên. Ta biết một trong những tính chất rất hay của FT đó là việc biến phép toán tích chập thành phép toán nhân. Đối với việc nhân hai số nguyên rất lớn, ta biểu diễn các số ấy ở một cơ số nào đó, thường là cơ số nguyên tố. Khi đó việc nhân hai số được xác đinh theo modulo p của tích mà giống như việc xác định các hệ số của nhân hai đa thức hay chuỗi lũy thừa. Tích các hệ số ấy, nếu viết ở dạng véc tơ lại chính là tích chập của hai véc tơ. Bỏ qua những kĩ thuật tinh xảo đòi hỏi phải sử dụng cách xác định số nguyên tố hay cách biểu diễn đa thức (bằng nội suy, hoặc biểu diễn dạng vécto, ...) thì mô hình chung mà FT áp dụng vào sẽ là thế này:
1) Để tính tích của hai số nguyên rất lớn A và B, ta biểu diễn chúng ở một cơ số p nguyên tố nào đó $A= a_0+a_1p+\cdots+a_np^n $, $B= b_0+b_1p+\cdots+b_np^n $
2) Kí hiêu C là tích chập của hai vécto $a=(a_0,...,a_n) $, $b=(b_0,...,b_n) $. Sử dụng FT ta tính Fa, Fb. Sau đó tính Fa. Fb.
3) Dùng FT ngược để nhận được $c= F^{-1}(Fa.Fb) $
Bạn nào nghiên cứu về Số học thuật toán hoặc Tin chắc sẽ rất rõ phần này, giải thích câu hỏi trên sẽ tốt hơn.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]