Некоторые методы умножения длинных чисел:

• Классическая длинная арифметика. 1 Число хранится в виде массива его цифр. 1 Операции над числами производятся с помощью «школьных» алгоритмов сложения, вычитания, умножения, деления столбиком. 1
• Алгоритм Карацубы. 23 Позволяет сократить необходимое число умножений. 2 Например, чтобы перемножить два четырёхзначных числа, вместо необходимых 16 перемножений метод Карацубы позволяет обойтись всего девятью. 2
• Быстрое преобразование Фурье (FFT). 2 Немецкие математики Арнольд Шёнхаге и Фолькер Штрассен показали, как можно использовать FFT для перемножения огромных многозначных чисел. 2 Сегодня их метод повсеместно используется для обработки чисел длиной в миллиарды знаков. 2