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

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

Ділення

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

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

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

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