了解Schönhage-Strassen算法(巨大整数乘法)

Question

我需要在Python中尽可能高效地乘以几个1000位数的长整数.从文件中读取数字.

我正在尝试使用Schönhage-Strassen算法进行整数乘法,但我仍然坚持理解它背后的定义和数学,特别是快速傅里叶变换.

任何帮助理解这个算法,如实际例子或一些伪代码将受到高度赞赏.

Answer 1

Knuth 的TAOCP 的第 4.3.3 章对其进行了描述，并且在其他章节中还有一些 FFT 伪代码可用于此目的。