алгоритм Фюрера

Алгоритм Фюрера (англ. Fürer’s algorithm) — быстрый больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его предшественник, алгоритм Шёнхаге — Штрассена, опубликованный в 1971 году. Задача быстрого умножения больших чисел представляет большой интерес в области криптографии с открытым ключом. Предшественник алгоритма Фюрера, алгоритм Шёнхаге — Штрассена, использовал быстрое преобразование Фурье для умножения больших чисел за время , однако его авторы, (нем. Arnold Schönhage) и Фолькер Штрассен, сделали предположение о существовании алгоритма, способного решить проблему перемножения больших чисел за . Алгоритм Фюрера заполнил промежуток между этими границами: он может быть использован, чтобы перемножить числа за время , где — итерированный логарифм числа n. Однако разница по времени между алгоритмами становится заметной при очень больших перемножаемых числах (больше 10 000 000 000 000 значащих цифр). В 2008 году Аниндая Де, Шэнден Саха, Пьюш Курур и Рампрасад Саптхариши построили похожий алгоритм, основанный на модульной, а не комплексной арифметике, достигнув при этом такого же времени работы.