Використаннямодульної арифметики. Обчислення з многочленами. Методи множення. Складністьобчислень
Ефективний шлях багаторазовогозведення за модулем – використання методу Монтгомері, який було запропоновано в1985 році. Цей метод особливо ефективний при апаратній реалізації алгоритмів.Дуже зручно відмовитися від операцій множення і ділення та замінити їхопераціями додавання. Метод полягає в наступному.
Нехай /> – непарне число, потрібно помножитилишки.
Розглянемо алгоритм: R = 0;
for i = 0 until i
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 = />
зведення модульмногочлен множення
Воно виконується за /> кроків, на кожному зяких здійснюється додавання до поточного значення /> значення />, /> з наступним діленням на />. Завдяки цьомуділенню отримані значення завжди знаходяться в інтервалі />. У результаті роботиданого алгоритму виходить число />. Тепер для одержання числа /> необхіднозастосувати ще один раз даний алгоритм до чисел /> і />. Оскільки число /> обчислюється задопомогою зрушень і відрахувань зі складністю /> двійкових операцій (його можнаобчислити заздалегідь і зберігати отримане значення), а алгоритм такожвиконується за /> операцій, тo загальнатрудомісткість обчислення добутку оцінюється величиною /> двійкових операцій.
Наприклад:
А = 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.
Звертання
Для заданого числа />, />, знаходимо за допомогоюрозширеного алгоритму Евкліда числа /> і />, що задовольняють рівності />. Якщо />, тo якзворотний можна взяти />. Таким чином, звертання в кільцілишків можна виконати за /> бітових операцій.
Ділення
Оскільки />, то ділення у кільці лишківвиконується зі складністю />.
Обчислення з многочленами
Між обчисленнями в кільцімногочленів над довільним кільцем /> і в кільці цілих чисел, записаниху будь-якої системи числення багато спільного. Вони виконуються за схожимиформулами, а різниця лише в тому, що для чисел необхідно враховувати знакипереносу від молодших розрядів до старших, у той час як у випадку многочленівніяких переносів при операціях з коефіцієнтами не виникає – і вихідні величиниі значення лежать у кільці />.
Складність операцій змногочленами, звичайно, оцінюють кількістю ариф-метичних операцій кільця />, яківиконуються над його коефіцієнтами. Якщо відомо бітову складність операцій у полі,то можна оцінити результуючу бітову складність операцій з многочленами. Щобвідрізняти арифметичну складність від бітової в оцінках ми використовуватимемосимволи /> і/>.
Обчислення значень многочленів.
Нехай /> – довільне кільце. Розглянемодобре відомий алгоритм Руфіні — Горнера для обчислення значень многочлена надкільцем /> уточці/>.
Останнє число />,і будешуканим значенням многочлена. Арифметична складність алгоритму, мабуть,дорівнює />.Бітову складність у випадку, коли кільце /> розглядається як кільце цілихчисел, можна оцінити виразом />, де через /> позначений максимум іздвох чисел: числа двійкових знаків у запису найбільшого з коефіцієнтів і числа /> , а число /> означає числодвійкових знаків у запису найбільшого з чисел /> . У такий спосіб виходить оцінка />
Алгоритм Руфіні-Горнера дозволяєотримати не тільки значення />. Як показує наступна теорема,величини /> єв точності коефіцієнтами многочлена, що є лишком від ділення многочлена /> на />.
Теорема 1
Справедлива рівність
/>
Доведення
Маємо
/>
Методи множення
Для зручності ми думатимемо, що миоперуємо із цілими числами, вираженими у двійковій системі числення. У нас єдва />-розряднихчисла /> і />, то можна записати
/>
де /> – ²найбільш значуща половина² числа />, а /> – ²найменш значуща половина²; подібним же чином />, />.
Ця формула зводить задачу множення/>-розрядних чисел до трьох операцій множення /> розрядних чисел: /> плюс деякі прості операції зсувуі додавання. Цю формулу можна використовувати для множення з подвійноюточністю, коли результат потрібно отримати із четверною точністю. За допомогоюцієї формули можна визначити деякий рекурсивний процес для множення, значнобільш швидкий, ніж уже знайомий нам метод, коли />– велике та час виконання порядку />.
Якщо />– час, необхідне для виконаннямноження />-розряднихчисел, то ми маємо
/> для деякої константи />, оскільки вправій частині співвідношення потрібно виконати тільки три операції множенняплюс деякі операції додавання і зрушення. З останнього співвідношення заіндукцією випливає, що
/>,
якщо вибрати />– достатньо великим, длятого, щоб ця нерівність виконувалася при />, отримаємо
/>
Тобто час, затрачуваний намноження, можна скоротити з величини порядку /> до величини порядку />, і, звичайно,при великому /> цей алгоритм набагато швидше.
Схожий, але більш складний методвиконання множення із часом порядку /> був уперше запропонований А.Карацубою.
Час виконання можна скоротити щебільше, якщо помітити, що тільки що розглянутий метод є окремим випадком (при />) більшзагального методу, що дає
/>
для будь-якого фіксованого />. Цей більшзагальний метод можна отримати в такий спосіб. Розіб'ємо
/> і />
на /> частин:
/> />
де кожне /> і кожне /> є /> розрядними числами. Розглянемомногочлени
/>, />
і покладемо
/>.
Оскільки /> і />, то ми маємо />, і тому, якщо знатикоефіцієнти />,можна легко обчислити />. Завдання полягає в тому, щобзнайти гарний спосіб обчислення коефіцієнтів />, виконуючи лише /> операцій множення /> — розряднихчисел плюс деякі додаткові операції, для яких час виконання пропорційно />.
Цього можна досягти, обчислюючи
/>.
Коефіцієнти будь-якого многочленастепені />можназаписати у вигляді лінійної комбінації значень цього многочлена в /> різних точках.Час, необхідний для узяття такої комбінації, якнайбільше пропорційно />. У дійсностідобутком /> є,точно кажучи, не добутками />-розрядних чисел, а добуткамичисел, розряд яких не перевищує />, де />– фіксована величина, що залежитьвід />.Легко скласти програму множення для /> – розрядних чисел, що вимагаєвиконання лише /> операцій, тому що при фіксованому/> двадобутки />-розряднихчисел на />-розрядніможна одержати за /> операцій. Можна показати, що дляцього методу
/>.
Теорема 2
Для кожного /> існує така постійна /> і такийалгоритм множення, що число елементарних операцій />, які необхідно виконати, щобпомножити два /> — розрядних числа, відповідаєоцінці />. Цятеорема ще не найкращий результат. Для практичних цілей великий недолік, щометод різко ускладнюється при /> тобто />. Ця теорема незадовільна й зтеоретичної точки зору, тому що в ній не повною мірою використовується лежачийу її основі метод багаточленів.
Перш ніж розглянути алгоритмТоома-Кука, розберемо один приклад. На цьому прикладі не можна побачитиефективність методу, оскільки ми маємо справу з невеликими числами. Але можнапобачити деякі корисні спрощення, що застосовні в загальному випадку.
Приклад
Припустимо, нам потрібно помножити/> на />.
У двійковій системі числення /> на />.
Нехай />.
Багаточлени /> />, />.
Звідси знаходимо />:
/> (3.1)
Тепер, використовуючи п'ятьостанніх величин, знайдемо п'ять коефіцієнтів багаточлена />.
Для перебування коефіцієнтівбагаточлена
/>
при заданих значеннях /> можнаскористатися одним цікавим невеликим алгоритмом. Спочатку запишемо
/>,
/>
Позначаючи ліву частину виразучерез /> мибачимо, що
/>
Отже, коефіцієнти /> можна обчислити задопомогою дуже простого методу, якому можна продемонструвати для багаточлена />, визначеногоспіввідношеннями (3.1):
/>
Крайній стовпчик складається іззаданих значень />; щоб одержати />-ту колонку, потрібно обчислитирізниці між сусідніми величинами попереднього стовпчика і розділити їх на />. Коефіцієнти /> розташовуютьсяв колонках зверху; так, />, тому ми маємо
/>
У загальному вигляді можназаписати
/>
ця формула показує, яким чином зкоефіцієнтів /> можна отримати коефіцієнти />:
/>
Послідовно виходять коефіцієнтибагаточленів
/>
Відповідно до останньої таблиці мимаємо
/>
Отже, відповіддю до нашої вихідноїзадачі буде /> де /> виходить у результаті дійдодавання і зрушення. Крім того, якщо коефіцієнти багаточлена /> – ненегативні, тотакими будуть і числа />, а тоді всі проміжні результати,одержувані в процесі проведення обчислення, є ненегативними.