Бінарний метод піднесення до степеня

Однією з задач, що найчастіше зустрічаюся при реалізації різноманітних криптоалгоритмів, є задача піднесення деякого числа до певного степеня, тобто обчислення значення функції f(x)= x , зокрема піднесення до степеня за деяким модулем n - f(x)=x^bmod n. Прямолінійний алгоритм (він буде експоненційним) потребує значних обчислювальних затрат. Проте відомо набагато ощадливіший алгоритм, котрий називається бінарний метод піднесення до степеня.
Нехай нам задано: x Є Z . Потрібно знайти f(x)=x^bmod n.
Подамо показник d в двійковій системі числення, тобто
d=(d_l d_l-1 ... d₁ d₀ )₂, де d_i Є {0;1}.
Алгоритм буде складатись з l+1 команд. Спочатку покладаємо z₀=l. Тоді і-та команда задається так:

Результатом виконання останньої є значення x^dmod n.