Реферат: Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень

Використаннямодульної арифметики. Обчислення з многочленами. Методи множення. Складністьобчислень

Ефективний шлях багаторазовогозведення за модулем – використання методу Монтгомері, який було запропоновано в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 = />

зведення модульмногочлен множення

Воно виконується за /> кроків, на кожному зяких здійснюється додавання до поточного значення /> значення />, /> з наступним діленням на />. Завдяки цьомуділенню отримані значення завжди знаходяться в інтервалі />. У результаті роботиданого алгоритму виходить число />. Тепер для одержання числа /> необхіднозастосувати ще один раз даний алгоритм до чисел /> і />. Оскільки число /> обчислюється задопомогою зрушень і відрахувань зі складністю /> двійкових операцій (його можнаобчислити заздалегідь і зберігати отримане значення), а алгоритм такожвиконується за /> операцій, т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 якзворотний можна взяти />. Таким чином, звертання в кільцілишків можна виконати за /> бітових операцій.

Ділення

Оскільки />, то ділення у кільці лишківвиконується зі складністю />.

Обчислення з многочленами

Між обчисленнями в кільцімногочленів над довільним кільцем /> і в кільці цілих чисел, записаниху будь-якої системи числення багато спільного. Вони виконуються за схожимиформулами, а різниця лише в тому, що для чисел необхідно враховувати знакипереносу від молодших розрядів до старших, у той час як у випадку многочленівніяких переносів при операціях з коефіцієнтами не виникає – і вихідні величиниі значення лежать у кільці />.

Складність операцій змногочленами, звичайно, оцінюють кількістю ариф-метичних операцій кільця />, яківиконуються над його коефіцієнтами. Якщо відомо бітову складність операцій у полі,то можна оцінити результуючу бітову складність операцій з многочленами. Щобвідрізняти арифметичну складність від бітової в оцінках ми використовуватимемосимволи /> і/>.

Обчислення значень многочленів.

Нехай /> – довільне кільце. Розглянемодобре відомий алгоритм Руфіні — Горнера для обчислення значень многочлена надкільцем /> уточці/>.

Останнє число />,<sub/>і будешуканим значенням многочлена. Арифметична складність алгоритму, мабуть,дорівнює />.Бітову складність у випадку, коли кільце /> розглядається як кільце цілихчисел, можна оцінити виразом />, де через /> позначений максимум іздвох чисел: числа двійкових знаків у запису найбільшого з коефіцієнтів і числа /> , а число /> означає числодвійкових знаків у запису найбільшого з чисел /> . У такий спосіб виходить оцінка />

Алгоритм Руфіні-Горнера дозволяєотримати не тільки значення />. Як показує наступна теорема,величини /> єв точності коефіцієнтами многочлена, що є лишком від ділення многочлена /> на />.

Теорема 1

Справедлива рівність

/>

Доведення

Маємо

/>

Методи множення

Для зручності ми думатимемо, що миоперуємо із цілими числами, вираженими у двійковій системі числення. У нас єдва />-розряднихчисла /> і />, то можна записати

/>

де /> – ²найбільш значуща половина² числа />, а /> – ²найменш значуща половина²; подібним же чином />, />.

Ця формула зводить задачу множення/>-розрядних чисел до трьох операцій множення /> розрядних чисел: /> плюс деякі прості операції зсувуі додавання. Цю формулу можна використовувати для множення з подвійноюточністю, коли результат потрібно отримати із четверною точністю. За допомогоюцієї формули можна визначити деякий рекурсивний процес для множення, значнобільш швидкий, ніж уже знайомий нам метод, коли />– велике та час виконання порядку />.

Якщо />– час, необхідне для виконаннямноження />-розряднихчисел, то ми маємо

/> для деякої константи />, оскільки вправій частині співвідношення потрібно виконати тільки три операції множенняплюс деякі операції додавання і зрушення. З останнього співвідношення заіндукцією випливає, що

/>,

якщо вибрати />– достатньо великим, длятого, щоб ця нерівність виконувалася при />, отримаємо

/>

Тобто час, затрачуваний намноження, можна скоротити з величини порядку /> до величини порядку />, і, звичайно,при великому /> цей алгоритм набагато швидше.

Схожий, але більш складний методвиконання множення із часом порядку /> був уперше запропонований А.Карацубою.

Час виконання можна скоротити щебільше, якщо помітити, що тільки що розглянутий метод є окремим випадком (при />) більшзагального методу, що дає

/>

для будь-якого фіксованого />. Цей більшзагальний метод можна отримати в такий спосіб. Розіб'ємо

/> і />

на /> частин:

/> />

де кожне /> і кожне /> є /> розрядними числами. Розглянемомногочлени

/>, />

і покладемо

/>.

Оскільки /> і />, то ми маємо />, і тому, якщо знатикоефіцієнти />,можна легко обчислити />. Завдання полягає в тому, щобзнайти гарний спосіб обчислення коефіцієнтів />, виконуючи лише /> операцій множення /> — розряднихчисел плюс деякі додаткові операції, для яких час виконання пропорційно />.

Цього можна досягти, обчислюючи

/>.

Коефіцієнти будь-якого многочленастепені />можназаписати у вигляді лінійної комбінації значень цього многочлена в /> різних точках.Час, необхідний для узяття такої комбінації, якнайбільше пропорційно />. У дійсностідобутком /> є,точно кажучи, не добутками />-розрядних чисел, а добуткамичисел, розряд яких не перевищує />, де />– фіксована величина, що залежитьвід />.Легко скласти програму множення для /> – розрядних чисел, що вимагаєвиконання лише /> операцій, тому що при фіксованому/> двадобутки />-розряднихчисел на />-розрядніможна одержати за /> операцій. Можна показати, що дляцього методу

/>.

Теорема 2

Для кожного /> існує така постійна /> і такийалгоритм множення, що число елементарних операцій />, які необхідно виконати, щобпомножити два /> — розрядних числа, відповідаєоцінці />. Цятеорема ще не найкращий результат. Для практичних цілей великий недолік, щометод різко ускладнюється при /> тобто />. Ця теорема незадовільна й зтеоретичної точки зору, тому що в ній не повною мірою використовується лежачийу її основі метод багаточленів.

Перш ніж розглянути алгоритмТоома-Кука, розберемо один приклад. На цьому прикладі не можна побачитиефективність методу, оскільки ми маємо справу з невеликими числами. Але можнапобачити деякі корисні спрощення, що застосовні в загальному випадку.

Приклад

Припустимо, нам потрібно помножити/> на />.

У двійковій системі числення /> на />.

Нехай />.

Багаточлени /> />, />.

Звідси знаходимо />:

/> (3.1)

Тепер, використовуючи п'ятьостанніх величин, знайдемо п'ять коефіцієнтів багаточлена />.

Для перебування коефіцієнтівбагаточлена

/>

при заданих значеннях /> можнаскористатися одним цікавим невеликим алгоритмом. Спочатку запишемо

/>,

/>

Позначаючи ліву частину виразучерез /> мибачимо, що

/>

Отже, коефіцієнти /> можна обчислити задопомогою дуже простого методу, якому можна продемонструвати для багаточлена />, визначеногоспіввідношеннями (3.1):

/>

Крайній стовпчик складається іззаданих значень />; щоб одержати />-ту колонку, потрібно обчислитирізниці між сусідніми величинами попереднього стовпчика і розділити їх на />. Коефіцієнти /> розташовуютьсяв колонках зверху; так, />, тому ми маємо

/>

У загальному вигляді можназаписати

/>

ця формула показує, яким чином зкоефіцієнтів /> можна отримати коефіцієнти />:

/>

Послідовно виходять коефіцієнтибагаточленів

/> 

Відповідно до останньої таблиці мимаємо

/>

Отже, відповіддю до нашої вихідноїзадачі буде /> де /> виходить у результаті дійдодавання і зрушення. Крім того, якщо коефіцієнти багаточлена /> – ненегативні, тотакими будуть і числа />, а тоді всі проміжні результати,одержувані в процесі проведення обчислення, є ненегативними.