Контрольная работа: Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчисл
Ефективний шлях багаторазового зведення за модулем – використання методу Монтгомері, який було запропоновано в 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;
--> ЧИТАТЬ ПОЛНОСТЬЮ <--