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

ЛЕКЦІЯ 3

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

План.

1. Обчислення  в кільці лишків. Алгоритм Монтгомері.

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

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

4. Метод А. Карацуби.

5. Оцінка складності алгоритмів.

Ефективний шлях багатократного приведення за модулем – використання методу Монтгомері, запропонованого у 1985 році. Цей метод є особливо ефективном за апаратної реалізації алгоритмів. Дуже зручно відмовитися від операцій ділення і множення і замінити їх операціями додавання. Метод полягає в наступному. Нехай  - непарне число, треба перемножити лишки  и . Розглянемо алгоритм:

R = 0;

for i = 0 until i < n do

          begin

if a_i = 1 then R = R + B;

if R - нечетно then R = R + N;

R = R / 2;

end

if R ³ N then R = R - N.

Сутність даного алгоритму в тому, що за рівності

A =

Множення числа числа В на число А зводиться до обчислення виразу

AB =

      Воно виконується за кроків, на кожному з яких виконується додавання да поточного значення    значення ,  з подальшим діленням на 2. завдяки цьому діленню, отримані значення завжди знаходяться у інтервалі . У результаті роботи даного алгоритма отримуємо число . Тепер для отримання числа  необхідно ще раз застосувати даний алгоритм до чисел  и . Оскільки число   обчислюється за допомогою зсувів і віднімань зі складністю  двійкових операцій (його можна обчислити зазделегідь і зберігати отримане значення), а алгоритм також виконується за  двійкових операцій.

        Напиклад:

        Нехай А = 1´2⁰ + 0´2¹ + 1´2²  + 0´2³ + 1´2⁴ = 1 + 4 + 16 = 21 (10101)

          В = 18

          N = 41

Зрозуміло, що АВ (mod N) = 21´18 (mod 41) = 9

Обчислимо добуток цих чисел за допомогою вищенаведеного алгоритму.

1. R = 0

    a₀ = 1  

    R = R + B = 0 + 18 = 18;

    R - четно;

    R = R / 2 = 9.

2. a₁ = 0;

R - нечетно;

R = R + N = 9 + 41 = 50;

R = R / 2 = 25;

3. a₂ = 1

    R = R + B = 25 + 18 = 43;

    R - нечетно;

    R = R + N = 43 + 41 = 84;

    R = R / 2 = 42;

4. a₃ = 0;

      R - нечетно;

      R = R + N = 1 + 41 = 42;

R = R / 2 = 21;

5. a₄ = 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’ = 2²ⁿ (mod N) = 2^{2 ´5}(mod N) = 1024(mod 41) = 40 = 0´2⁰ + 0´2¹ + 0´2²  + 1´2³ + 0´2⁴ + 1´2⁵

B ’= 40;

N = 41.

1. R = 0

    a₀ = 0

    R - парне;

    R = R / 2 = 0.

2. a₁ = 0;

 R - парне;

 R = R / 2 = 0;

3. a₂ = 0

    R - парне;

    R = R / 2 = 0;

4. a₃ = 1;

    R = R + B = 0 + 40 = 40;

    R - парне;

R = R / 2 = 20;

5. a₄ = 0;

    R - парне;

    R = R / 2 = 10;

6.  a₅ = 1;

    R = R + B = 10 + 40 = 50;

    R = R - N = 50 - 41 = 9.

Обернення.

Для заданого числа , , знаходимо за допомогою розширеного алгоритма Евкліда числа   та  , що задовільняє рівності . Якщо  , то в якості оберненого можна взяти . Таким чином, обернення в кільці лишків можна виконати за  бітових операцій.

Ділення.

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

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

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

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

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

Над кільцем  у точці  . Він базується на наступному представленні многочлена

і полягає у послідовному обчисленні значень  за формулами

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

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