|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
30-04-2011, 02:49 AM | #1 |
+Thành Viên+ Tham gia ngày: Apr 2011 Bài gởi: 2 Thanks: 2 Thanked 0 Times in 0 Posts | Biến đổi Fourier nhanh (FFT) và ứng dụng trong lý thuyết số? Mình có đọc qua về FFT (Fast Fourier Transform) và thấy ở Wiki người ta có nhắc đến ứng dụng của nó trong lý thuyết số (number theory). Mình không phải dân toán nên không biết nhiều về cái gọi là number theory, bác nào có nghiên cứu phần này có thể đả thông cho mình về FFT trong number theory được không? Cám ơn rất nhiều. __________________ "What I cannot create, I do not understand". - Richard Feynman. |
30-04-2011, 04:28 PM | #2 | |
+Thành Viên+ Tham gia ngày: Nov 2007 Đến từ: Konoha Bài gởi: 899 Thanks: 372 Thanked 362 Times in 269 Posts | Trích:
| |
30-04-2011, 08:51 PM | #3 |
+Thành Viên Danh Dự+ Tham gia ngày: Dec 2007 Bài gởi: 252 Thanks: 40 Thanked 455 Times in 95 Posts | 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. |
The Following User Says Thank You to Mr Stoke For This Useful Post: | Galois_vn (01-05-2011) |
Bookmarks |
Ðiều Chỉnh | |
Xếp Bài | |
|
|