Page 31 - 4395

ДОДАТОК А

БІНАРНІ АЛГОРИТМИ ПІДНЕСЕННЯ ЧИСЛА
ДО ВЕЛИКОГО СТЕПЕНЯ

Бінарний метод ґрунтується на двійковому зображенні
показника степеня. Є два варіанти цього методу залежно від того, як

переглядають біти показника степеня. Перший – бінарний метод
зліва направо, а другий – бінарний метод справа наліво. Зрозуміло,
що перший метод переглядає біти зліва направо, тоді як другий –
справа наліво.

Бінарний метод зліва направо. Нехай (п ...п ) – бінарне
k–1
о 2
зображення числа п. Тоді бінарний метод зліва направо ґрунтується
на розкладі

2
2
2
x (n k 1 ...n 0 ) 2  ((...(((x n k 1 ) x n k 2 ) x n k 3 ) 2 ...) x n 1 ) x n 0 .

Алгоритм такий:

LR_bin_exp(х,n,m)
Вхід: x,n,m;
n
Вихід: y=x mod m;
begin
зобразити n так: n = (n ...n ) ;
0 2
k-1
y:=l;
for i:=k-l downto 0 do
begin
y:=y·y mod m;

if n =1 then
i
y:=y·x mod m;
end

end.

Бінарний метод справа наліво ґрунтується на розкладі

x (n k  1 ...n 0 ) 2  (x 2 0 ) n 0 ...(x 2 k  1 ) n k  1 ,
що дає такий алгоритм:

RL_bin_exp(х, n, m)
Вхід: x,n,m;
n
Вихід: у=х mod m;

31