Застосування теорії чисел в криптографії, страница 7

Розв’язки будемо обирати з повної системи абсолютно найменших лишків по модулю 7:

Легко побачити, що  не є коренями конгруенції. Перевіримо інші значення, використавши схему Горнера кожний раз зводячи отримані числа до лишків за даним модулем з повної системи абсолютно найменших лишків:

	1	0	0	0	1	1
2	1	2	4≡-3	8≡1	3	7≡0
-2	1	0	4≡-3	0	3¹0 (mod7)
3	1	-2	-2	2	2¹0 (mod7)
-3	1	-1	0	1	0

Із схеми Горнера видно, що конгруенція має два кореня з повної системи абсолютно найменших лишків . Отже розв’язками даної конгруенції є два класи:

Якщо розглянути розв’язки у повній системі найменших додатних лишків, то розв’язок буде такий:

Теорема.

Якщо обидві частини  конгруенції (1) помножити на ціле число , взаємно просте з модулем , то дістанемо конгруенцію, еквівалентну даній.

Доведення. Припустимо, що  є деякий розв'язок конгруенції (1), тоді

Помножимо обидві частини цієї конгруенції на , отримаємо:

Отже,  є розв'язком і для конгруенції

В інший бік: якщо  є розв'язком конгруенції , тобто , тоді обидві частини конгруенції можна скоротити на , не змінюючи  модуля, бо , отже,

,

тобто  є розв'язком конгруенції (1), що і доводить наше твердження.

Зауважимо, що при розв'язуванні конгруенцій з невідомою величиною можна, не змінюючи модуля, скорочувати обидві частини конгруенції тільки на такий їх спільний дільник, який є взаємно простий з модулем (див. властивість 8, п.3.1).

4.2 Конгруенції першого степеня.

Конгруенції І-го степеня мають вигляд:

 або

Дослідимо наявність розв’язків у такої конгруенції.

По-перше розглянемо ситуацію, коли

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

Висновок.

За умови, що  конгруенція  має єдиний розв’язок.

По-друге розглянемо конгруенцію  за умови

. Отже, якщо , тоді складові конгруенції можна подати так , отже за властивістю конгруенцій таку конгруенцію можна скоротити на . Отримаємо конгруенцію . З попереднього така конгруенція має єдиний розв’язок , або . Але якщо розглянути повну систему лишків для модуля , то можна помітити, що у інтервал  попадають такі розв’язки:

, тобто кількість таких розв’язків - . Ці розв’язки не конгруентні між собою за модулем  і в свою чергу кожний з них створює свій клас лишків.

Висновок.

За умови, що  конгруенція має хоча б один розв’язок, якщо . Цих розв’язків є рівно  штук ( класів). Перший з розв’язків знаходиться із скороченої на  конгруенції, інші обчислюються, як

Розв’язання конгруенції першого порядку можна проводити різними методами.

a.  Використання функції Ейлера .

Розглянемо конгруенцію . За теоремою Ейлера в разі, якщо , , або, використовуючи рефлективність, .

Перемножимо дві конгруенції: , або

.

Розв’язок знайдений. Але розв’язання за цим методом доволі часто буває нераціональним через необхідність підносити числа до значних степенів.

b.  Використання властивостей конгруенцій.

Приклад. а) розв’язати конгруенцію:

Розв’язання. По-перше, розглянемо НСД 15 та 17: , отже конгруенція має єдиний розв’язок. Спростимо конгруенцію за властивостями: 25 і 15 мають спільний множник 5, який є взаємо простим з модулем 17. Отже, використовуючи властивості конгруенції, можемо поділити конгруенцію на 5:  Число 5 відповідає абсолютно найменшому лишку -12, який є кратний числу 3, отже , скоротимо на 3: . Отже конгруенція має єдиний розв’язок з повної системи абсолютно найменших лишків за модулем 17, або розв’язок з повної системи найменших додатних лишків:

б) Розв’язати конгруенцію:

Розв’язання.  - розв’язок 1. У конгруенції складові можна заміняти відповідними лишками з мінімальних систем – узагальнення властивостей конгруенції. Отже  Вихідна конгруенція зміниться так: . Відповідь:  або