SSA[一種高效的二進制乘法算法]:SSA代表Schönhage

我們首先考慮如何計算兩個大數 a 與 b 的積對的模，其中 a 與 b 都是小於的正數。

首先將 N 分解為 K 與 M 的積，其中 K 是2的冪次。

這樣，a與b就能寫成K位的進制的數，除了最高的一位因為 a 與 b 可以等於而可以等於，其它的位都將小於。計算a與b的積模，即是計算兩個長度為K的數列的負循環卷積。

為了讓負循環卷積可以正確完成，需要選取一個數字n，在模的環中計算卷積。這就需要卷積後的各位結果均在一個長度在的區間內，這樣我們計算結果模的值就夠了。

一般來說，選取即可。

負循環卷積可以通過有權重的快速傅立葉變換實現。對K位表示下的a與b的係數，權重是，其中是模環的2K次原根。而傅立葉變換需要的原根是K次，即。

注意到，所以2是一個2n次原根。如果n是K的倍數，那么將是2的冪，。這樣，傅立葉變換可以只通過加減法和移位運算完成。

對a與b進行傅立葉變換後，需要將它們變換後的係數逐點相乘。這個乘法是模的，可以遞歸地使用如上算法。直到n過小時，可以直接計算係數的積並對取模。

然後，對結果進行逆變換，去除權重即得最終結果。

若想得到兩個大數 a 與 b 的完整積，只需要在第一步將N取得足夠大，使積一定小於即可。

限於篇幅，以上僅為此算法的概要，若有興趣，詳情請參照。

SSA[一種高效的二進制乘法算法]