SSA代表Schönhage–Strassen algorithm，是一種非常高效的二進制大數乘法算法。一般用於將數萬至數萬億位二進制數相乘，是許多高精度計算算法的底層核心。
SSA由 Arnold Schönhage 與 Volker Strassen 在1971年開發，通過在整數模環中疊代使用快速數論變換，可以在 O(n logn loglogn) 的時間複雜度內將兩個 n bit 的二進制大數相乘。
基本介紹
- 外文名：Schönhage–Strassen algorithm
我們首先考慮如何計算兩個大數 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取得足夠大，使積一定小於即可。
限於篇幅，以上僅為此算法的概要，若有興趣，詳情請參照。
