퓌러 알고리즘

퓌러 알고리즘(Fürer's algorithm)은 스위스 수학자 마르틴 퓌러(Martin Fürer)가 발표한 정수를 빠르게 곱하는 알고리즘으로, $N$자리 정수 두 개를 $O\left(n\log n\ \cdot 2^{O(\log ^{*}n)}\right)$시간에 곱할 수 있다. 여기서 log*n은 반복 로그이다.

2007년에 만들어졌으며, $O(N\log N\log \log N)$시간에 두 정수를 곱할 수 있는 쇤하게-슈트라센 알고리즘을 훨씬 능가하였다. 그러나 $2^{2^{64}}$보다 큰 수에서 복잡도나 속도가 더 빨라지고, 2019년 3월에는 이 알고리즘보다 더 개선된 곱셈 알고리즘이 등장해 아주 큰 두 수를 $O(n\log n)$시간 안에 곱할 수 있게 되었다.