Page 32 - 4395

begin
зобразити n так: n = (n ...n ) ;
k-1
0 2
у:=1;
z:=x mod m;

for i:=0 to k-1 do
begin
if n =1 then y:=y·z mod m;
i
z:=z·z mod m;
end
end.

Бінарний метод справа наліво не потребує знаходження
бінарного зображення числа повністю, тобто обчислення степеня
можна виконувати, коли утворюються біти показника степеня. Крім

того, крок множення і крок піднесення до квадрата (відповідно,
рядок 5 та рядок 6 алгоритму RL_bin_exp(x,n,m)) можна виконувати
паралельно. Таке не можна застосувати у випадку бінарного методу

зліва направо. Проте варіант зліва направо може використати той
факт, що один операнд на кроці множення фіксований (завжди
дорівнює х у рядку 5 алгоритму LR_bin_exp(x,n,m)), щоб збільшити

швидкість множення. Таке не можна зробити у варіанті справа
наліво, де операнди змінні.
Розглянуті алгоритми потребують [log n] піднесень до квадрата
та Н(n) множень (Н(n) є вагою Хемінга числа n, тобто кількістю

одиничних бітів у двійковому зображенні числа п) і, отже, 2[log n]
множень у найгіршому випадку i 3[log n]/2 множень у середньому.
Оскільки [log n] є нижньою границею для кількості множень,

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

32