2.2. Піднесення до степеня. Розглянемо задачу обчислення функції  у довільному кільці. Безхитрісна прямолінійна програма для цієї функції має складність d — 1:

У подальших розділах неодноразово виникатиме задача

Піднесення до степеня за модулем  

Задано:        .

Обчислити: .

Завжди можна вважати, що d < п. Інакше можна скористатися тео­ремою Ойлера, щоб понизити показник. Якщо ми використаємо для розв'язання цієї задачі наведену вище прямолінійну програму (з мно­женням в кільці ), то отримаємо експоненційний алгоритм. Справді, коли d не набагато менше, ніж п , то довжина входу має порядок , а кількість операцій множення має порядок п .

На щастя, є значно ощадніший алгоритм, який був відомий ще до нашої ери в Індії. Ми називатимемо його бінарним методом. Опишемо цей метод у вигляді прямолінійної програми для обчислення функції .

Подамо показник  у двійковій системі числення:  , де  і . Для спрощення запису дозволимо одній команді програми виконувати до двох множень і покладемо . Тоді -та команда задається так:

           Всього команд . Результатом виконання останньої є

Всього витрачається  множень (множення пер­шої команди не є необхідним — вона включена для однорідності). На­ведену прямолінійну програму можна легко конвертувати в алгоритм у сенсі пункту 1.2, чи в програму на будь-якій мові програмування, що розв'язує задачу піднесення до степеня за модулем .