Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Đại Học Và Sau Đại Học/College Playground > Lý Thuyết Số/Number Theory

News & Announcements

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é !

* Nội quy MathScope.Org

* Một số quy định chung !

* 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

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 30-04-2011, 02:49 AM   #1
luugu
+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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
"What I cannot create, I do not understand". - Richard Feynman.
luugu is offline   Trả Lời Với Trích Dẫn
Old 30-04-2011, 04:28 PM   #2
Galois_vn
+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:
Nguyên văn bởi luugu View Post
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.
Mình thấy có một ứng dụng trong việc tìm nghiệm đa thức (không biết có nhớ nhầm không, sơ đồ phân nhánh) và nhân nhanh các đa thức.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Galois_vn is offline   Trả Lời Với Trích Dẫn
Old 30-04-2011, 08:51 PM   #3
Mr Stoke
+Thành Viên Danh Dự+
 
Mr Stoke's Avatar
 
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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Mr Stoke is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to Mr Stoke For This Useful Post:
Galois_vn (01-05-2011)
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 07:20 PM.


Powered by: vBulletin Copyright ©2000-2018, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 47.45 k/52.49 k (9.59%)]