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

a₃ = 0; R – непарне; R = R + N = 1 + 41 = 42;

R = R / 2 = 21;

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.

R = 0 a₀ = 0 R - парне;

R = R / 2 = 0.

a₁ = 0; R - парне;

R = R / 2 = 0;

a₂ = 0 R - парне;

R = R / 2 = 0;

a₃ = 1; R = R + B = 0 + 40 = 40;

R - парне;

R = R / 2 = 20;

a₄ = 0; R - парне;

R = R / 2 = 10;

6. a₅ = 1; R = R + B = 10 + 40 = 50;

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

Звертання

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

Ділення

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

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