Метод множення Шенхаге - Штрассена
Алгоритм Шенхаге - Штрассена- асимптотично швидкий алгоритм множення великих чисел. Він був розроблений Арнольдом Шенхаге і Фолькером Штрассеном в 1971. Складність алгоритму в нотації "Про - великого" становить O(NlogNlog logN). Алгоритм рекурсивно використовує швидке перетворення Фур'є над кільцем з 2 2n+ 1 елементів, спеціальний тип дискретного перетворення Фур'є - теоретико-числове перетворення.
Алгоритм Шенхаге - Штрассена був найшвидшим асимптотично відомим методом множення з 1971 до 2007, коли Фюрер був запропонований швидший метод. Однак алгоритм Фюрера в даний час має перевагу тільки для астрономічно великих чисел і не використовується на практиці.
На практиці алгоритм Шенхаге - Штрассена починає перевершувати у швидкості старі методи, такі як алгоритм Карацуби та алгоритм Тоома-Кука для чисел між 2 2 15 та 2 2 17 (від 10,000 до 40,000 десяткових розрядів).
Додатки алгоритму Шенхаге - Штрассена включають як чисто математичні завдання, такі як пошук простих чисел Мерсенна і обчислення цифр числаπ, так і практичні, такі як обчислення підстановки Кронекера, в якій множення багаточленів з цілими коефіцієнтами можна ефективно замінити множенням великих чисел; це використовується на практиці GMP-ECM для факторизації цілих чисел методом еліптичних кривих Ленстри.
Зміст
Припустимо, що ми перемножуємо числа 123 і 456 «у стовпчик», проте виконання перенесення. Результат виглядатиме так:
| 1 | 2 | 3 | ||
| × | 4 | 5 | 6 | |
| 6 | 12 | 18 | ||
| 5 | 10 | 15 | ||
| 4 | 8 | 12 | ||
| 4 | 13 | 28 | 27 | 18 |
Ця послідовність (4, 13, 28, 27, 18) називаєтьсяациклічноюаболінійною згорткоювід послідовностей (1,2,3) та (4,5,6). Знаючи ациклічну згортку двох послідовностей, розрахувати твір нескладно: достатньо виконати перенесення (наприклад, у правому стовпці, ми залишаємо 8 і додаємо 1 до стовпця, що містить 27). У прикладі це призводить до результату 56088.
Є й інші типи згорток, які можуть бути корисними. Припустимо, що вхідні послідовності містятьnелементів (у прикладі - 3). Тоді результуюча лінійна згортка міститьn+n− 1 елементів; якщо ми візьмемо найправіший стовпецьnелементів і додамо найлівіший стовпецьn− 1 ', в результаті ми отримаємо циклічну згортку:
| 28 | 27 | 18 |
| + | 4 | 13 |
| 28 | 31 | 31 |
Якщо ми зробимо перенесення при циклічному згортанні, результат буде той самий, що і при добутку чисел за модулем Bn− 1 (у даному прикладі це 10 3 − 1 = 999). Виконаємо перенесення (28, 31, 31) і отримаємо 3141, при цьому 3141 ≡ 56088 (mod 999).
Навпаки, якщо ми візьмемо найправіший стовпецьnелементів івіднімемонайлівіший стовпецьn−1 елементів, то в результаті ми отримаємо зворотну згортку:
| 28 | 27 | 18 |
| − | 4 | 13 |
| 28 | 23 | 5 |
Якщо ми зробимо перенесення при зворотному зсіданні, то результат буде той же, що і при добутку чисел за модулем Bn+ 1. У даномуприкладі, 10 3 + 1 = 1001, виконаємо перенесення (28, 23, 5) і отримаємо 3035, при цьому 3035 ≡ 56088 (mod 1001). Зворотна згортка може містити негативні числа, які можуть бути прибрані під час перенесення, використовуючи ту ж техніку, що і при довгих відніманнях.
Теорема про згортку
Як і інші методи, засновані на швидкому перетворенні Фур'є, алгоритм Шенхаге - Штрассена докорінно залежить від теореми про згортку, яка забезпечує ефективний спосіб порахувати циклічну згортку двох послідовностей. Її ідея полягає в наступному:
Циклічна згортка двох векторів може бути знайдена через дискретне перетворення Фур'є (ДПФ) кожного з них шляхом твору результуючих векторів елемент за елементом, з подальшим зворотним перетворенням Фур'є (ОДПФ).
Або через формули:
CyclicConvolution(X, Y) = IDFT(DFT(X) · DFT(Y)), де: CyclicConvolution -циклічна згортка, DFT -дискретне перетворення Фур'є, IDFT -зворотне дискретне перетворення Фур'є.
Якщо ми порахуємо ДПФ та ОДПФ, використовуючи швидке перетворення Фур'є, і викличемо наш алгоритм перемноження рекурсивно, щоб перемножити входи(?) перетворених векторів DFT(X) та DFT(Y), то в результаті ми отримаємо ефективний алгоритм розрахунку циклічної згортки.
У цьому алгоритмі, набагато ефективніше вважати зворотну циклічну згортку; виявляється, трохи модифікована версія теореми про згортку може дозволити і це. Припустимо, що вектори X і Y мають довжинуnіa— примітивний корінь порядку 2n(це означає, щоa2n= 1 і менше ступеняaне рівні 1). Таким чином ми можемо визначити третій векторA, званийвектор ваги, що має наступні властивості:
Тепер ми можемо записати:
NegacyclicConvolution(X,Y) =A−1 · IDFT(DFT(A·X) · DFT(A·Y)), де NegacyclicConvolution -Зворотна циклічна згортка, DFT -дискретне перетворення Фур'є, IDFT -зворотне дискретне перетворення Фур'є.
Іншими словами, це те саме за винятком того, що вхідні вектори помножені наA, а результат помножений наA−1 .
Вибір кільця
Дискретне перетворення Фур'є - абстрактна операція, яка може бути виконана в будь-якому кільці алгебри; зазвичай воно береться з поля комплексних чисел, але фактично використовувати комплексну арифметику з достатньою точністю, щоб забезпечити точні результати, повільно та неефективно. Натомість ми можемо використовувати теоретико-числове перетворення, яке здійснює перетворення в полі цілих чисел за модулем N для деякого цілого N.
Так само як є примітивне коріння одиниці будь-якого порядку на комплексній площині, за будь-якого заданогоnми можемо вибрати відповідне N таке, щоb— примітивний корінь одиниці порядкуnу полі цілих чисел за модулем N (іншими словами,bn≡ 1 (mod N), і всі менші ступеніbне дорівнюють 1 mod N).
Алгоритм витрачає більшість часу на рекурсивне виконання добутку менших чисел; у простому варіанті алгоритму це відбувається у ряді місць:
- Усередині алгоритму швидкого перетворення Фур'є примітивний корінь одиниці неодноразово зводиться в ступінь і множиться на інші числа.
- При зведенні в ступінь примітивного кореня одиниціaдля отримання вектора ваги A з подальшим множенням векторів A або A −1 інші вектора.
- При виконанніпослідовного перемноження перетворених векторів
Ключовий момент - вибрати N, модуль, що дорівнює 2n+ 1 для деякого цілогоn. Цей спосіб має ряд переваг у ряді стандартних систем, у яких великі цілі числа представлені в двійковому вигляді:
- Будь-яке число може бути швидко зменшено за модулем 2n+ 1 використовуючи тільки зсув і додавання.
- Будь-яке примітивне коріння одиниці в цьому кільці можуть бути записані у формі 2k; відповідно ми можемо множити чи ділити будь-яке число на корінь із одиниці використовуючи зсув.
- Поелементне рекурсивне перемноження перетворених векторів може бути виконане, використовуючи зворотну згортку, яка працює швидше, ніж ациклічна згортка, і в якій вже є зменшення результату
за модулем 2n+ 1.
Наступний приклад ілюструє роботу алгоритму. Покладемо задано два числа: X та Y, кожне довжиною 8 біт. Потрібно знайти значення RES = (X * Y) mod 2 N +1 Візьмемо для певності X = Y = 12910 = 1000 00012. Виберемо N = 8 + 8 = 16.
- Етап 1. Розбиття чисел на K = 4 слів довжини M = 4 біти:
- Доповнимо числа нулями до довжини N = 16 і розіб'ємо на слова. Отримаємо дві послідовності (у цьому прикладі ідентичні): . Або в десятковому вигляді: (слова розташовані в порядку від молодших біт до старших). Всі операції далі виконуються по модулю 2 n +1, де n вибирається з умови n = 2 * M + log2 (K) і є ступенем двійки, тобто в нашому випадку n = 2 * 4 + 2 = 10, n = 16.
- Етап 2. Обчислення згортки двох послідовностей:
- Етап 2.1 Збільшення послідовностей на вагові коефіцієнти. 2K-ий корінь з одиниці в кільці з 2 n +1 елементів дорівнює 2 2n/2K = 2 4 =16. Результат множення на вектор вагових коефіцієнтів у десятковому вигляді: .
- Етап 2.2 Пряме перетворення Фур'є над кільцем із 2 n елементів. K-ий корінь з одиниці в кільці відрахувань за модулем 2 n +1 дорівнює 2 2n/2K = 2 4 = 256. Формула перетворення: , - К-тий корінь з одиниці в кільці відрахувань за модулем 2 n +1. Результат: .
- Етап 2.3 Покомпонентний добуток послідовностей у кільці з 2 n елементів. Результат: .
- Етап 2.4 Зворотне перетворення Фур'є над кільцем із 2 n елементів. Формула зворотного перетворення: , - Зворотний до по модулю 2 n +1. Результат: .
- Етап 2.5 Збільшення послідовностей на коефіцієнти, зворотні до використовуваних у 2.1. Результат: .