Розширений алгоритм Евклида.

Конгруенції за модулем.

Модульна арифметика

Лишки за модулем .

Кожне ціле число можна розділити з остачею на натуральне число : , < .

Остача від ділення числа на називається лишком (у даному випадку - лишком числа за модулем ). Операція, що співставляє числу його лишок за модулем , називається зведенням за модулем .

Означення.Два цілих числа і конгруентні за модулем , якщо їхня різниця ділиться на .

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

Стандартні значення лишків за модулем , належать множині (т.зв. система найменших додатних лишків).

Лишок суми за модулем дорівнює сумі лишків, зведеної, якщо необхідно, ще раз за модулем . Аналогічною властивістю володіє лишок добутку.

Відношення конгруентності дозволяє розбити множину цілих чисел на класи. Елементи одного класу мають однакові лишки за модулем . Очевидно, класи не перерізаються. Кожному класу відповідає один найменший додатний лишок і навпаки.

Лишок суми або добутку за модулем елементів і не залежить від вибору цих елементів, а залежить лише від вибору класів і .

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

Наприклад, якщо , то клас, що містить , є множиною виду . Оскільки множина цілих чисел є кільцем, то наша відповідність між класами і лишками є гомоморфізмом кілець. Образ цього гомоморфізму (кільце класів лишків за модулем ) називається фактором-кільцем кільця цілих чисел за модулем і звичайно позначається . Зауважимо, що нулем у кільці лишків у кільці є клас .

При зашифруванні інформації використовуються взаємно однозначні перетворення даних. Для перебування зворотних елементів у кільці можна використовувати т.зв. розширений алгоритм Евкліда.

Цей алгоритм призначений для пошуку целочисленного розвязку , , рівняння , > , , де і також цілі.

Розглянемо схему розширеного алгоритму Евклида на прикладі чисел 15 і 25. Ми будемо знаходити залишки і (неповні) частки від розподілу двох чисел, тобто користуватися рівностями виду , де всі числа цілі і < .

Оскільки повиннео виконуватися нерівність > , те змінимо позначення: , .

Випишемо послідовність рядків:

( , ).

Пояснення. Ділимо на з остачею. Одержуємо: тобто , відкіля , . Перевіряємо: ? Ні – працюємо далі. Обчислюємо : . Формуємо черговий рядок: .

Вихідними даними для кроку 2 будуть рядки (з попереднього кроку) і . З цими рядками діємо аналогічно.

Якщо чергова остача від ділення дорівнює 0, виписуємо розвязок з даних попереднього кроку (див. нижче).

( , )

( , ).

При формуванні чергового рядка, остачу , виписуємо рішення з даних попереднього кроку:

НОД , , НОД .