Введение
Алгоритм умножения
Алгоритм Шёнгаге — Страссена — это асимптотически быстрый алгоритм умножения для больших целых чисел, опубликованный Арнольдом Шёнгаге и Волкером Страссеном в 1971 году. Он работает путём рекурсивного применения быстрого преобразования Фурье (БПФ) над целыми числами по модулю 2n+1. Временная сложность алгоритма для умножения двух n-значных чисел выражается в нотации «большое O». Алгоритм Шёнгаге — Страссена был самым быстрым известным методом умножения с 1971 по 2007 год. Он асимптотически быстрее, чем более ранние методы, такие как умножение Карацубы и Тоома — Кука, и начинает превосходить их на практике для чисел, содержащих более 10 000–100 000 десятичных цифр. В 2007 году Мартин Фюрер опубликовал алгоритм с более высокой асимптотической сложностью. В 2019 году Дэвид Харви и Жорис ван дер Ховен показали, что умножение многозначных чисел имеет теоретическую сложность; однако их алгоритм имеет постоянные факторы, которые делают его неприменимо медленным для любой практически значимой задачи (см. галактический алгоритм). Области применения алгоритма Шёнгаге — Страссена включают масштабные вычисления, выполняемые ради самих вычислений, такие как Great Internet Mersenne Prime Search и приближения числа π, а также практические приложения, такие как факторизация эллиптических кривых Ленстры с помощью замены Кронекера, которая сводит умножение многочленов к умножению целых чисел.
Описание
В этом разделе представлена упрощенная версия алгоритма, показывающая, как вычислить произведение двух натуральных чисел, по модулю числа вида , где – некоторое фиксированное число. Целые числа следует разделить на блоков по битов, поэтому в практических реализациях важно найти оптимальный баланс между параметрами . В любом случае, этот алгоритм предоставит способ умножить два положительных целых числа, при условии, что выбрано таким образом, чтобы .
Let be the number of bits in the signals and , where is a power of two. Divide the signals and into blocks of bits each, storing the resulting blocks as arrays (whose entries we shall consider for simplicity as arbitrary precision integers). We now select a modulus for the Fourier transform, as follows. Let be such that Also put , and regard the elements of the arrays as (arbitrary precision) integers modulo Observe that since , the modulus is large enough to accommodate any carries that can result from multiplying and Thus, the product (modulo ) can be calculated by evaluating the convolution of Also, with , we have , and so is a primitive th root of unity modulo
We now take the discrete Fourier transform of the arrays in the ring , using the root of unity for the Fourier basis, giving the transformed arrays Because is a power of two, this can be achieved in logarithmic time using a fast Fourier transform. Let (pointwise product), and compute the inverse transform of the array , again using the root of unity The array is now the convolution of the arrays Finally, the product is given by evaluating
This basic algorithm can be improved in several ways. Firstly, it is not necessary to store the digits of to arbitrary precision, but rather only up to bits, which gives a more efficient machine representation of the arrays Secondly, it is clear that the multiplications in the forward transforms are simple bit shifts. With some care, it is also possible to compute the inverse transform using only shifts. Taking care, it is thus possible to eliminate any true multiplications from the algorithm except for where the pointwise product is evaluated. It is therefore advantageous to select the parameters so that this pointwise product can be performed efficiently, either because it is a single machine word or using some optimized algorithm for multiplying integers of a (ideally small) number of words. Selecting the parameters is thus an important area for further optimization of the method.
Пусть – количество бит в сигналах и , где – степень двойки. Разделим сигналы и на блоков по битов каждый, сохраняя полученные блоки в виде массивов (элементы которых для простоты будем считать целыми числами произвольной точности). Теперь выберем модуль для преобразования Фурье следующим образом. Пусть также будет , и рассматриваем элементы массивов как (целые числа произвольной точности) по модулю . Заметим, что поскольку , модуль достаточно велик, чтобы вместить любые переносы, которые могут возникнуть при умножении и . Таким образом, произведение (по модулю ) можно вычислить, оценив свертку . Кроме того, при , у нас есть , и, следовательно, – примитивный корень степени из единицы по модулю .
Let be the number of bits in the signals and , where is a power of two. Divide the signals and into blocks of bits each, storing the resulting blocks as arrays (whose entries we shall consider for simplicity as arbitrary precision integers). We now select a modulus for the Fourier transform, as follows. Let be such that Also put , and regard the elements of the arrays as (arbitrary precision) integers modulo Observe that since , the modulus is large enough to accommodate any carries that can result from multiplying and Thus, the product (modulo ) can be calculated by evaluating the convolution of Also, with , we have , and so is a primitive th root of unity modulo
We now take the discrete Fourier transform of the arrays in the ring , using the root of unity for the Fourier basis, giving the transformed arrays Because is a power of two, this can be achieved in logarithmic time using a fast Fourier transform. Let (pointwise product), and compute the inverse transform of the array , again using the root of unity The array is now the convolution of the arrays Finally, the product is given by evaluating
This basic algorithm can be improved in several ways. Firstly, it is not necessary to store the digits of to arbitrary precision, but rather only up to bits, which gives a more efficient machine representation of the arrays Secondly, it is clear that the multiplications in the forward transforms are simple bit shifts. With some care, it is also possible to compute the inverse transform using only shifts. Taking care, it is thus possible to eliminate any true multiplications from the algorithm except for where the pointwise product is evaluated. It is therefore advantageous to select the parameters so that this pointwise product can be performed efficiently, either because it is a single machine word or using some optimized algorithm for multiplying integers of a (ideally small) number of words. Selecting the parameters is thus an important area for further optimization of the method.
Теперь применим дискретное преобразование Фурье к массивам в кольце , используя корень из единицы в качестве базиса Фурье, получив преобразованные массивы . Поскольку – степень двойки, это можно выполнить за логарифмическое время с помощью быстрого преобразования Фурье. Пусть (поэлементное произведение), и вычислим обратное преобразование массива , снова используя корень из единицы . Массив теперь является сверткой массивов . Наконец, произведение вычисляется путем оценки .
Let be the number of bits in the signals and , where is a power of two. Divide the signals and into blocks of bits each, storing the resulting blocks as arrays (whose entries we shall consider for simplicity as arbitrary precision integers). We now select a modulus for the Fourier transform, as follows. Let be such that Also put , and regard the elements of the arrays as (arbitrary precision) integers modulo Observe that since , the modulus is large enough to accommodate any carries that can result from multiplying and Thus, the product (modulo ) can be calculated by evaluating the convolution of Also, with , we have , and so is a primitive th root of unity modulo
We now take the discrete Fourier transform of the arrays in the ring , using the root of unity for the Fourier basis, giving the transformed arrays Because is a power of two, this can be achieved in logarithmic time using a fast Fourier transform. Let (pointwise product), and compute the inverse transform of the array , again using the root of unity The array is now the convolution of the arrays Finally, the product is given by evaluating
This basic algorithm can be improved in several ways. Firstly, it is not necessary to store the digits of to arbitrary precision, but rather only up to bits, which gives a more efficient machine representation of the arrays Secondly, it is clear that the multiplications in the forward transforms are simple bit shifts. With some care, it is also possible to compute the inverse transform using only shifts. Taking care, it is thus possible to eliminate any true multiplications from the algorithm except for where the pointwise product is evaluated. It is therefore advantageous to select the parameters so that this pointwise product can be performed efficiently, either because it is a single machine word or using some optimized algorithm for multiplying integers of a (ideally small) number of words. Selecting the parameters is thus an important area for further optimization of the method.
Этот базовый алгоритм можно улучшить несколькими способами. Во-первых, нет необходимости хранить цифры до произвольной точности, достаточно хранить их до битов, что обеспечивает более эффективное машинное представление массивов . Во-вторых, очевидно, что умножения в прямом преобразовании – это простые битовые сдвиги. При некоторой осторожности также можно вычислить обратное преобразование, используя только сдвиги. Таким образом, при соблюдении осторожности можно исключить любые настоящие умножения из алгоритма, за исключением поэлементного произведения . Поэтому выгодно выбирать параметры так, чтобы это поэлементное произведение можно было выполнить эффективно, либо потому, что оно представляет собой одно машинное слово, либо с использованием оптимизированного алгоритма для умножения целых чисел (в идеале небольшого количества слов). Таким образом, выбор параметров является важной областью для дальнейшей оптимизации метода.
Let be the number of bits in the signals and , where is a power of two. Divide the signals and into blocks of bits each, storing the resulting blocks as arrays (whose entries we shall consider for simplicity as arbitrary precision integers). We now select a modulus for the Fourier transform, as follows. Let be such that Also put , and regard the elements of the arrays as (arbitrary precision) integers modulo Observe that since , the modulus is large enough to accommodate any carries that can result from multiplying and Thus, the product (modulo ) can be calculated by evaluating the convolution of Also, with , we have , and so is a primitive th root of unity modulo
We now take the discrete Fourier transform of the arrays in the ring , using the root of unity for the Fourier basis, giving the transformed arrays Because is a power of two, this can be achieved in logarithmic time using a fast Fourier transform. Let (pointwise product), and compute the inverse transform of the array , again using the root of unity The array is now the convolution of the arrays Finally, the product is given by evaluating
This basic algorithm can be improved in several ways. Firstly, it is not necessary to store the digits of to arbitrary precision, but rather only up to bits, which gives a more efficient machine representation of the arrays Secondly, it is clear that the multiplications in the forward transforms are simple bit shifts. With some care, it is also possible to compute the inverse transform using only shifts. Taking care, it is thus possible to eliminate any true multiplications from the algorithm except for where the pointwise product is evaluated. It is therefore advantageous to select the parameters so that this pointwise product can be performed efficiently, either because it is a single machine word or using some optimized algorithm for multiplying integers of a (ideally small) number of words. Selecting the parameters is thus an important area for further optimization of the method.
Дальнейшее изучение
Подробности реализации можно найти в книге "Prime Numbers: A Computational Perspective" (Первочисленные числа: вычислительная перспектива). Этот вариант несколько отличается от первоначального метода Шёнхаге тем, что он использует дискретное взвешенное преобразование для более эффективного выполнения негациклических сверток. Дополнительную подробную информацию можно найти в книге Кнута "Искусство программирования".
Оптимизация
В этом разделе описываются несколько важных практических оптимизаций при реализации алгоритма Шёнхаге — Штрассена.
Использование других алгоритмов умножения, внутри алгоритмов
Ниже определенного порогового значения эффективнее использовать другие алгоритмы умножения, такие как умножение Тума — Кука.
Корень из 2 трюк
Идея заключается в использовании в качестве корня из единицы порядка в конечном поле (является решением уравнения ), при взвешивании значений в подходе NTT (число-теоретическое преобразование). Было показано, что это позволяет сократить время целочисленного умножения на 10%.