Зворотний елемент в кільці по модулю

визначення

Нехай заданий деякий натуральний модуль, і розглянемо кільце, утворене цим модулем (тобто складається з чисел від до). Тоді для деяких елементів цього кільця можна знайти зворотний елемент.

Зворотним до числа по модулю називається таке число, що:

і його нерідко позначають через.

Зрозуміло, що для нуля зворотного елемента не існує ніколи; для інших же елементів зворотний може як існувати, так і немає. Стверджується, що зворотний існує тільки для тих елементів, які взаємно прості з модулем.

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

На завершення, розглянемо алгоритм, який дозволяє знайти зворотні до всіх числах по деякому модулю за лінійний час.

Знаходження з допомогою Розширеного алгоритму Евкліда

Розглянемо допоміжне рівняння (щодо невідомих і):

Це лінійне диофантово рівняння другого порядку. Як показано у відповідній статті, з умови випливає, що це рівняння має рішення, яке можна знайти за допомогою Розширеного алгоритму Евкліда (звідси ж, до речі кажучи, слід, що коли, рішення, а тому і зворотного елемента, не існує).

З іншого боку, якщо ми візьмемо від обох частин рівняння залишок по модулю, то отримаємо:

Таким чином, знайдене і буде зворотним к.

Реалізація (з урахуванням того, що знайдене треба взяти по модулю, і могло бути негативним):

Асимптотика цього рішення виходить.

Знаходження з допомогою бінарного зведення в ступінь

Скористаємося теоремою Ейлера:

яка вірна якраз для випадку взаємно простих і.

До речі кажучи, в разі простого модуля ми отримуємо ще більш просте твердження - малу теорему Ферма:

Помножимо обидві частини кожного з рівнянь на, отримаємо:

для будь-якого модуля:

для простого модуля:

Таким чином, ми отримали формули для безпосереднього обчислення зворотного. Для практичного застосування у звичайних випадках використовують ефективний алгоритм бінарного зведення в ступінь. який в нашому випадку дозволить зробити зведення в ступінь за.

Цей метод видається дещо простіше описаного в попередньому пункті, однак він вимагає знання значення функції Ейлера, що фактично вимагає факторизації модуля, що іноді може виявитися досить складним завданням.

Якщо ж факторизация числа відома, то тоді і цей метод також працює за асимптотику.

Знаходження всіх простих по заданому модулю за лінійний час

Нехай дано простий модуль. Потрібно для кожного числа в відрізку знайти зворотне до нього.

Застосовуючи описані вище алгоритми, ми отримаємо лише рішення з асимптотикою. Тут же ми наведемо просте рішення з асимптотикою.

Рішення це виглядає наступним чином. Позначимо через шукане зворотне до числа по модулю. Тоді для 1 "> вірно тотожність:

Реалізація цього дивно лаконічного рішення:

Доказ цього рішення вдає із себе ланцюжок простих перетворень:

звідки, беручи обидві частини по модулю, отримуємо:

Помноживши обидві частини на зворотне до і зворотне до, отримуємо шукану формулу:

що й потрібно було довести.