В одной из предыдущих статей я рассказал о математических алгоритмах, позволяющих проверить простоту очень большого числа. Но в основе всех тех алгоритмов лежит одна базовая операция — перемножение двух больших чисел. Именно операции длинного умножения занимают 99,9% времени выполнения любого теста простоты. Как же умножение реализуется на практике? Говорят, что при помощи быстрого преобразования Фурье. Но беглое прочтение Википедии вызывает недоумение. Какое отношение преобразование Фурье имеет к умножению целых чисел? Давайте разбираться.
