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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(,).

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

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

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

(,)

(,).

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

НОД,, НОД.

Дата добавления: 2014-10-15