Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень
Ефективний шлях багаторазового зведення за модулем – використання методу Монтгомері, який було запропоновано в 1985 році. Цей метод особливо ефективний при апаратній реалізації алгоритмів. Дуже зручно відмовитися від операцій множення і ділення та замінити їх операціями додавання. Метод полягає в наступному.
Нехай – непарне число, потрібно помножити лишки.
Розглянемо алгоритм: R = 0;
for i = 0 until i < n do begin
if ai = 1 then R = R + B;
if R - непарне then R = R + N;
R = R / 2;
end
if R ³ N then R = R - N.
Суть даного алгоритму в тому, що в силу рівності
A =
множення числа В на число А зводиться до обчислення
AB =
зведення модуль многочлен множення
Воно виконується за кроків, на кожному з яких здійснюється додавання до поточного значення значення $IMAGE6$, $IMAGE7$ з наступним діленням на $IMAGE8$. Завдяки цьому діленню отримані значення завжди знаходяться в інтервалі $IMAGE9$. У результаті роботи даного алгоритму виходить число $IMAGE10$. Тепер для одержання числа $IMAGE11$ необхідно застосувати ще один раз даний алгоритм до чисел $IMAGE12$ і $IMAGE13$. Оскільки число $IMAGE12$ обчислюється за допомогою зрушень і відрахувань зі складністю $IMAGE15$ двійкових операцій (його можна обчислити заздалегідь і зберігати отримане значення), а алгоритм також виконується за $IMAGE15$ операцій, тo загальна трудомісткість обчислення добутку оцінюється величиною $IMAGE15$ двійкових операцій.
Наприклад:
А = 1´20 + 0´21 + 1´22 + 0´23 + 1´24 = 1 + 4 + 16 = 21 (10101) У = 18 N = 41
Зрозуміло, що АВ(mod N) = 21´18 (mod 41) = 9.
Обчислимо добуток цих чисел за допомогою вищезазначеного алгоритму.
R = 0 a0 = 1 R = R + B = 0 + 18 = 18;
R - парне;
R = R / 2 = 9.
2. a1 = 0;
R - непарне;
R = R + N = 9 + 41 = 50;
R = R / 2 = 25;
a2 = 1 R = R + B = 25 + 18 = 43;
R – непарне;
R = R + N = 43 + 41 = 84;
R = R / 2 = 42;
a3 = 0; R – непарне; R = R + N = 1 + 41 = 42;
R = R / 2 = 21;
a4 = 1 R = R + B = 21 + 18 = 39;
R - непарне;
R = R + N = 39 + 41 = 80;
R = R / 2 = 40.
Це ми одержали 2-n AB(mod N)
Тепер ми повинні ще раз скористатися цим алгоритмом для обчислення АВ (mod N).
A’ = 22n (mod N) = 22 ´5(mod N) = 1024(mod 41) = 40 = 0´20 + 0´21 + 0´22 + 1´23 + 0´24 + 1´25
B ’= 40;
N = 41.
R = 0 a0 = 0 R - парне;
R = R / 2 = 0.
a1 = 0; R - парне;
R = R / 2 = 0;
a2 = 0 R - парне;
R = R / 2 = 0;
a3 = 1; R = R + B = 0 + 40 = 40;
R - парне;
R = R / 2 = 20;
a4 = 0; R - парне;
R = R / 2 = 10;
6. a5 = 1; R = R + B = 10 + 40 = 50;
R = R - N = 50 - 41 = 9.
Звертання
Для заданого числа $IMAGE18$, $IMAGE19$, знаходимо за допомогою розширеного алгоритму Евкліда числа $IMAGE20$ і $IMAGE21$, що задовольняють рівності $IMAGE22$. Якщо $IMAGE23$, тo як зворотний можна взяти $IMAGE24$. Таким чином, звертання в кільці лишків можна виконати за $IMAGE25$ бітових операцій.
Ділення
Оскільки $IMAGE26$, то ділення у кільці лишків виконується зі складністю $IMAGE25$.
Обчислення з многочленами
Між обчисленнями в кільці многочленів над довільним кільцем і в кільці цілих чисел, записаних у будь-якої системи числення багато спільного. Вони виконуються за схожими формулами, а різниця лише в тому, що для чисел необхідно враховувати знаки переносу від молодших розрядів до старших, у той час як у випадку многочленів ніяких переносів при операціях з коефіцієнтами не виникає – і вихідні величини і значення лежать у кільці .
Складність операцій з многочленами, звичайно, оцінюють кількістю ариф-метичних операцій кільця , які виконуються над його коефіцієнтами. Якщо відомо бітову складність операцій у полі, то можна оцінити результуючу бітову складність операцій з многочленами. Щоб відрізняти арифметичну складність від бітової в оцінках ми використовуватимемо символи $IMAGE31$ і $IMAGE32$.
Обчислення значень многочленів.
Нехай – довільне кільце. Розглянемо добре відомий алгоритм Руфіні - Горнера для обчислення значень многочлена над кільцем у точці $IMAGE35$.
Останнє число $IMAGE36$, і буде шуканим значенням многочлена. Арифметична складність алгоритму, мабуть, дорівнює $IMAGE37$. Бітову складність у випадку, коли кільце розглядається як кільце цілих чисел, можна оцінити виразом $IMAGE39$, де через $IMAGE40$ позначений максимум із двох чисел: числа двійкових знаків у запису найбільшого з коефіцієнтів і числа $IMAGE41$ , а число $IMAGE42$ означає число двійкових знаків у запису найбільшого з чисел $IMAGE43$ . У такий спосіб виходить оцінка $IMAGE44$
Алгоритм Руфіні-Горнера дозволяє отримати не тільки значення $IMAGE45$. Як показує наступна теорема, величини $IMAGE46$ є в точності коефіцієнтами многочлена, що є лишком від ділення многочлена $IMAGE47$ на $IMAGE48$.
Теорема 1
Справедлива рівність
$IMAGE49$
Доведення
Маємо
$IMAGE50$
Методи множення
Для зручності ми думатимемо, що ми оперуємо із цілими числами, вираженими у двійковій системі числення. У нас є два $IMAGE51$-розрядних числа $IMAGE52$ і $IMAGE53$, то можна записати
$IMAGE54$
де $IMAGE55$ – ²найбільш значуща половина² числа $IMAGE56$, а $IMAGE57$ – ²найменш значуща половина²; подібним же чином $IMAGE58$, $IMAGE59$.
Ця формула зводить задачу множення $IMAGE51$- розрядних чисел до трьох операцій множення розрядних чисел: $IMAGE62$ плюс деякі прості операції зсуву і додавання. Цю формулу можна використовувати для множення з подвійною точністю, коли результат потрібно отримати із четверною точністю. За допомогою цієї формули можна визначити деякий рекурсивний процес для множення, значно більш швидкий, ніж уже знайомий нам метод, коли – велике та час виконання порядку $IMAGE64$.
Якщо $IMAGE65$– час, необхідне для виконання множення -розрядних чисел, то ми маємо
$IMAGE67$ для деякої константи $IMAGE68$, оскільки в правій частині співвідношення потрібно виконати тільки три операції множення плюс деякі операції додавання і зрушення. З останнього співвідношення за індукцією випливає, що
$IMAGE69$,
якщо вибрати $IMAGE68$– достатньо великим, для того, щоб ця нерівність виконувалася при $IMAGE71$, отримаємо
$IMAGE72$
Тобто час, затрачуваний на множення, можна скоротити з величини порядку $IMAGE64$ до величини порядку $IMAGE74$, і, звичайно, при великому цей алгоритм набагато швидше.
Схожий, але більш складний метод виконання множення із часом порядку $IMAGE76$ був уперше запропонований А. Карацубою.
Час виконання можна скоротити ще більше, якщо помітити, що тільки що розглянутий метод є окремим випадком (при $IMAGE77$) більш загального методу, що дає
$IMAGE78$
для будь-якого фіксованого $IMAGE79$. Цей більш загальний метод можна отримати в такий спосіб. Розіб'ємо
$IMAGE80$ і $IMAGE81$
на $IMAGE82$ частин:
$IMAGE83$ $IMAGE84$
де кожне $IMAGE85$ і кожне $IMAGE86$ є $IMAGE87$ розрядними числами. Розглянемо многочлени
$IMAGE88$, $IMAGE89$
і покладемо
$IMAGE90$.
Оскільки $IMAGE91$ і $IMAGE92$, то ми маємо $IMAGE93$, і тому, якщо знати коефіцієнти $IMAGE94$, можна легко обчислити $IMAGE95$. Завдання полягає в тому, щоб знайти гарний спосіб обчислення коефіцієнтів $IMAGE94$, виконуючи лише $IMAGE97$ операцій множення - розрядних чисел плюс деякі додаткові операції, для яких час виконання пропорційно .
Цього можна досягти, обчислюючи
$IMAGE100$.
Коефіцієнти будь-якого многочлена степені $IMAGE101$можна записати у вигляді лінійної комбінації значень цього многочлена в $IMAGE97$ різних точках. Час, необхідний для узяття такої комбінації, якнайбільше пропорційно . У дійсності добутком $IMAGE104$ є, точно кажучи, не добутками -розрядних чисел, а добутками чисел, розряд яких не перевищує $IMAGE106$, де $IMAGE107$– фіксована величина, що залежить від $IMAGE79$. Легко скласти програму множення для $IMAGE109$ – розрядних чисел, що вимагає виконання лише $IMAGE110$ операцій, тому що при фіксованому $IMAGE107$ два добутки $IMAGE107$-розрядних чисел на -розрядні можна одержати за $IMAGE114$ операцій. Можна показати, що для цього методу
$IMAGE115$.
Теорема 2
Для кожного $IMAGE116$ існує така постійна $IMAGE117$ і такий алгоритм множення, що число елементарних операцій $IMAGE65$, які необхідно виконати, щоб помножити два - розрядних числа, відповідає оцінці $IMAGE120$. Ця теорема ще не найкращий результат. Для практичних цілей великий недолік, що метод різко ускладнюється при $IMAGE121$ тобто $IMAGE122$. Ця теорема незадовільна й з теоретичної точки зору, тому що в ній не повною мірою використовується лежачий у її основі метод багаточленів.
Перш ніж розглянути алгоритм Тоома-Кука, розберемо один приклад. На цьому прикладі не можна побачити ефективність методу, оскільки ми маємо справу з невеликими числами. Але можна побачити деякі корисні спрощення, що застосовні в загальному випадку.
Приклад
Припустимо, нам потрібно помножити $IMAGE123$ на $IMAGE124$.
У двійковій системі числення $IMAGE125$ на $IMAGE126$.
Нехай $IMAGE127$.
Багаточлени $IMAGE128$ $IMAGE129$, $IMAGE130$.
Звідси знаходимо $IMAGE131$:
$IMAGE132$ (3.1)
Тепер, використовуючи п'ять останніх величин, знайдемо п'ять коефіцієнтів багаточлена $IMAGE94$.
Для перебування коефіцієнтів багаточлена
$IMAGE134$
при заданих значеннях $IMAGE135$ можна скористатися одним цікавим невеликим алгоритмом. Спочатку запишемо
$IMAGE136$,
$IMAGE137$
Позначаючи ліву частину виразу через $IMAGE138$ ми бачимо, що
$IMAGE139$
Отже, коефіцієнти $IMAGE140$ можна обчислити за допомогою дуже простого методу, якому можна продемонструвати для багаточлена $IMAGE94$, визначеного співвідношеннями (3.1):
$IMAGE142$
Крайній стовпчик складається із заданих значень $IMAGE143$; щоб одержати $IMAGE144$-ту колонку, потрібно обчислити різниці між сусідніми величинами попереднього стовпчика і розділити їх на $IMAGE144$. Коефіцієнти $IMAGE140$ розташовуються в колонках зверху; так, $IMAGE147$, тому ми маємо
$IMAGE148$
У загальному вигляді можна записати
$IMAGE149$
ця формула показує, яким чином з коефіцієнтів $IMAGE150$ можна отримати коефіцієнти $IMAGE151$:
$IMAGE152$
Послідовно виходять коефіцієнти багаточленів
$IMAGE153$
Відповідно до останньої таблиці ми маємо
$IMAGE154$
Отже, відповіддю до нашої вихідної задачі буде $IMAGE155$ де $IMAGE156$ виходить у результаті дій додавання і зрушення. Крім того, якщо коефіцієнти багаточлена $IMAGE94$ – ненегативні, то такими будуть і числа $IMAGE140$, а тоді всі проміжні результати, одержувані в процесі проведення обчислення, є ненегативними.