쇤하게-슈트라센 알고리즘

쇤하게-슈트라센 알고리즘(Schönhage–Strassen algorithm)은 두 정수를 매우 빠르게 곱할 수 있는 알고리즘으로, $n$자리 정수 두 개를 $O(n\cdot \log n\cdot \log \log n)$시간에 곱할 수 있다. 이 알고리즘은 1971년에 등장하여 카라추바 알고리즘과 톰-쿡 알고리즘을 능가하였고, 2007년에 퓌러 알고리즘이 등장하기 전까지 두 개의 정수를 곱할 때 쓰이던 가장 빠른 알고리즘이었다. 고속 푸리에 변환을 재귀적으로 사용하며, 여기에 약간의 기술을 추가하여 두 수를 곱하는 알고리즘이다.