ถ้าผมเข้าใจไม่ผิดการใช้ FFT ในการหาค่า
p หรือเลขอื่นๆที่มีจำนวนหลักเยอะๆนั้น
มีจุดประสงค์เพื่อเร่งความเร็วในการคูณเป็นสำคัญครับ การคูณเลข n bits 2 ตัวเข้าด้วยกัน
แบบธรรมดา (long multiplication) จะมี complexity เป็น O(n
2) แต่ถ้าใช้
FFT multiplication จะลดเหลือเพียง O(nlog(n)loglog(n)) (มั้ง
) ครับ