El algoritmo de Fürer es un algoritmo para la multiplicación de números enteros muy grandes. Fue publicado en 2007 por el matemático suizo Martin Fürer de la Universidad Estatal de Pensilvania . Este algoritmo asintóticamente tiene una de las complejidades más bajas entre los algoritmos de multiplicación y, por lo tanto, es mejor que el algoritmo de Schönhage-Strassen . Su régimen asintótico solo se alcanza para números enteros muy grandes.
Antes del algoritmo de Fürer, el algoritmo de Schönage-Strassen, que data de 1971, permitía multiplicar dos enteros en el tiempo . Arnold Schönhage y Volker Strassen también conjeturaron que la complejidad mínima del producto rápido es , donde n es el número de bits utilizados en la escritura binaria de los dos enteros de entrada.
El algoritmo de Fürer tiene una complejidad en , donde denota el logaritmo iterado . La diferencia entre los términos y es asintóticamente en beneficio del algoritmo de Fürer, pero el régimen asintótico solo se alcanza para números muy grandes.
Un artículo escrito en 2014 por Harvey, van der Hoeven y Lecerf permite mostrar que el algoritmo optimizado de Fürer requiere operaciones y entrega un algoritmo que solo requiere operaciones, así como un tercer algoritmo en el tiempo pero cuya validez se basa en una conjetura. sobre los números de Mersenne . Estos algoritmos a veces se agrupan bajo el término algoritmo de Harvey-van der Hoeven-Lecerf.
En 2019, Harvey y van der Hoeven lograron una complejidad algorítmica de multiplicación, superando la complejidad del algoritmo de Fürer. Sin embargo, el régimen asintótico se alcanza para números de un tamaño superior a .