Піднесення до степеня за модулем - в кільці, sib soviet
Про те як звести число в дуже велику ступінь в модульної арифметики і при цьому не повісивши комп, я сьогодні розповім.
Отже, спочатку математика. Потім буде алгоритм і код на python.
Ми будемо працювати в кільці - ця така особлива структура алгебри. Це знати не обов'язково, головне користуватися особливим властивістю, але перш поговоримо про позначеннях: стандартно пишуть так: $ 7 ^ 4 \ pmod $ - це значить 7 в ступеня 4 по модулю 13, тобто 7 звести в 4 і знайти залишок від ділення на 13 ( грубо кажучи, тут математики можуть мене посварити). А вираз $ 7 ^ 4 \ equiv 9 \ pmod $ -це значить, що 7 в 4-го ступеня еквівалентно 9 по модулю 13, по суті якщо звести 7 в 4-ю ступінь і знайшовши залишок ділення на 13 то ми отримаємо 9, але можемо туди записати будь-яке число яке знаходженні залишку також дасть 9, скажімо $ 7 ^ 4 \ equiv 100 \ pmod $ теж вірно - як бачимо утворюється цілий клас еквівалентних чисел - це і будемо використовувати (це використовує RSA).
Для більш короткого позначення:
$ 7 ^ 4 \ pmod $ будемо позначати, використовуючи стиль неописаного тут алгебраїчного поняття "кільця" ось так: $ [7] ^ 4_ $, і дозволимо собі нахабну вільність, замість $ \ equiv $ використовуватимемо $ = $.
Розглянемо пропонований алгоритм спочатку на прикладі, потім в загальному вигляді. Нехай нам необхідно звести число 7 в ступінь. ем. 45 по модулю 5. Тоді робимо так:
$$
[7] ^ _ = [7] _ * [7] ^ _ = [7] _ * [49] ^ _ = [7] _ * [4] ^ _
$$
Подивившись на формулу вище, можна вже вгадати алгоритм)))) Що ми тут зробили, а ось як раз скористалися мигцем обумовленому мною властивістю. Давайте по кроках:
- Спочатку ми винесли множник щоб отримати парну ступінь - це можна, ми в "кільці"
- Потім знизили ступінь, звівши число в квадрат (зазвичай для цього не потрібні великі числа)
- Далі, просто згадали, що по-модулю у нас є велика кількість еквівалентних чисел, ну і просто знайшли від отриманого числа - 49 залишок від ділення на 5 - це 4 (адже вони еквівалентні в кільці). і з ним далі працюємо (таким чином ми не вилазимо за квадрат модуля, в нашому випадку 5)
На жаль приклад не дуже вдалий, але короткий (швидко закінчився, 1 в 11-й ступеня це 1). а так, в кінці у нас може з'явитися наприклад такий ось список:
$$
[7] _ * [4] _ * [3] _ * [2] _ * [1] _ * [2] _
$$
В цьому випадку їх попарно перемножуємо і кожен раз після множення знаходимо залишок, наприклад:
$ [7] _ * [4] _ = [3] _ $
Тепер більш-менш загальний опис алгоритму:
- Відразу скорочуємо вихідне вираз, приклад: $ [7] _ = [2] _ $
- Добиваємося парному ступеня шляхом винесення множника і додавання його в список (при додаванні в список на любителя, можна збирати елементи і потім їх попарно множити, або оптимізувати і при додаванні елемента дивитися, якщо там вже один є, то ми просто перемножуємо додається з уже наявними і записуємо залишок при діленні на модуль - таким чином "список" ніколи не виросте більше одного елемента і по-суті не стане "списком")
- Повторюємо попередній пункт потрібну кількість разів
- Перемножуємо між собою елементи списку (ефективно, тобто використовуючи властивості застосовуються вище), і залишилася елемент в списку перемножуємо з отриманим елементом операцією "зниження ступеня" і отримуємо результат (не забуваємо що він повинен бути теж поділений на модуль і відповідь - залишок - хоча це не обов'язково - так як це еквівалентні числа)
Ось і все, пора показати приклад на python (кому було незрозуміло опис вище - допоможе код):
Можете пограти з цією функцією - вона дуже швидко вважає, і так як в Пітоні за замовчуванням всі числа Великі. то спробуйте забивати найбільші числа в аргументи цієї функції, які взбредут вам в голову.
У Кріптоусіках. також реалізована ця функція - і я всіляко намагався повісити сервак - не вийшло.
Знаючи скільки студентів на лабах по-програмування зламали голову з цією процедурою зведення в ступінь по-модулю, я думаю цей матеріал буде корисний.