Материал: Теорія чисел в криптографії

ТЕМА №4 КОНГРУЕНЦІЇ З ОДНИМ НЕВІДОМИМ.

Питання 1. Основні відомості Питання 2. Конгруенції першого степеня. Розв’язання конгруенцій.

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

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

c)Використання підходящих дробів для розв’язку конгруенцій.

d)Розв’язання конгруенцій типу 2k x ≡ b(mod m), (2, m) = (2, b) = 1

Питання 3. Обернений елемент за множенням. Повернення до питання про системи лишків, як структури теорії груп.

Питання 4. Системи конгруенцій першого степеня з одним невідомим.

Питання 5. Конгруенції n-го степеня за простим модулем. Кількість коренів конгруенції n -го степеня за простим модулем.

Питання 6. Конгруенції n-го степеня за складеним модулем

Ключові терміни

Алгебраїчна конгруенція з одним невідомим, степінь конгруенції, розв’язок конгруенції, конгруенції І-го степеня, поля Галуа, системи конгруенцій з одним невідомим, розв’ язок системи конгруенцій, китайська теорема про залишки, конгруенція n-го степеня, простий модуль, складений модуль, наслідок з теореми Ферма

Питання 1. Основні відомості.

1. Алгебраїчна конгруенція з одним невідомим називається конгруенція виду:

Якщо an не ділиться на m , то n називається степінь конгруенції.

2.Розв’язати конгруенцію означає знайти усі такі xi , які задовольняють конгруенцію.

3.Дві конгруенції з одним невідомим називаються еквівалентними, якщо всякий розв'язок x однієї конгруенції є розв’язком іншої.

Теорема.

Якщо x = x1 задовольняє конгруенцію (1), то всяке число, яке належить до того самого класу лишків за модулем m , що й число x1 , також задовольняє цю конгруенцію, тобто розв'язок конгруенції складає весь клас чисел x ≡ x1 (mod m).

Доведення.

Це твердження безпосередньо випливає з властивостей конгруенцій. Справді, нехай x2 – будь-яке число, що належить до того самого класу лишків за модулемm , що й x1 ; тоді x2 ≡ x1 (mod m). За умовою x1 є розв'язок конгруенції (1), тобто має місце тотожна конгруенція f (x1 ) ≡ 0(mod m), , але тоді, згідно з властивістю конгруенцій (7),

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

Усі розв'язки конгруенції (1), що належать до одного класу чисел за модулем m , приймають за один розв'язок даної конгруенції. При цьому конгруенція (1) має стільки розв'язків, скільки класів чисел її задовольняють.

Приклад.

Розв’язати конгруенцію 141x5 − 126x3 + 196x2 − 111x + 36 ≡ 0(mod 7)

36

Розв’язання.

Використовуючи властивості конгруенцій, можна спростити дану конгруенцію, враховуючи, що

141 ≡ 1(mod 7), − 126 ≡ 0(mod 7), 196 ≡ 0 mod(7), −111 ≡ −6(mod 7) ≡ 1mod(7), 36 ≡ 1(mod 7)

Конгруенція прийме вигляд: x5 + x + 1 ≡ 0(mod 7)

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

(− 3, − 2, − 1, 0, 1, 2, 3)

Легко побачити, що 0,±1 не є коренями конгруенції. Перевіримо інші значення,

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

Теорема.

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

Доведення.

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

f (α) ≡ 0(mod m)

Помножимо обидві частини цієї конгруенції на k , отримаємо: kf (α) ≡ 0(mod m) Отже, α є розв'язком і для конгруенції kf (x) ≡ 0(mod m)

модуля, бо (k, m) = 1, отже,

f (α) ≡ 0(mod m),

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

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

37

Питання 2. Конгруенції першого степеня. Розв’ язання конгруенцій.

Конгруенції І-го степеня мають вигляд: ax + b ≡ 0(mod m) або ax ≡ b(mod m)

Дослідимо наявність розв’язків у такої конгруенції. По-перше розглянемо ситуацію, коли (a, m) = 1

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

Висновок.

За умови, що (a, m) = 1 конгруенція ax ≡ b(mod m) має єдиний розв’ язок.

По-друге розглянемо конгруенцію ax ≡ b(mod m) за умови (a, m) = d > 1

ax ≡ b(mod m) ax = b + mt . Отже, якщо d | a, d | m d | b , тоді складові конгруенції

можна подати так a = a1d , b = b1d , m = m1d , (a1, m1 ) = (b1 , m1 ) = 1, отже за властивістю конгруенцій таку конгруенцію можна скоротити на d . Отримаємо конгруенцію

a1 x ≡ b1 (mod m1 ).

З попереднього така конгруенція має єдиний розв’язок x ≡ x1 (mod m1 ) , або x = m1t + x1 . Але якщо розглянути повну систему лишків для модуля m = dm1 , то можна помітити, що у інтервал [0, m] попадають такі розв’язки:

x1 , x1 + m1 , x1 + 2m1 ,..., x1 + (d − 1)m1 , тобто кількість таких розв’язків - d . Ці розв’язки не конгруентні між собою за модулем m і в свою чергу кожний з них створює свій клас лишків.

Висновок.

За умови, що (a, m) = d > 1 конгруенція має хоча б один розв’ язок, якщо d | b . Цих

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

x2 = x1 + m1 , x3 = x1 + 2 × m1 ,..., xd = x1 + (d -1)m1

Розв’ язання конгруенції першого порядку можна проводити різними методами. b. Використання функції Ейлера ϕ(m) .

Розглянемо конгруенцію ax ≡ b(mod m), (a, m) = 1 . За теоремою Ейлера в разі, якщо (a, m) = 1, aϕ(m ) ≡ 1(mod m), або, використовуючи рефлективність, 1 ≡ aϕ(m ) (mod m).

Перемножимо дві конгруенції: ax ≡ baϕ(m ) (mod m), або x ≡ baϕ(m )−1 (mod m).

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

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

а) розв’язати конгруенцію: 15x ≡ 25(mod17)

Розв’язання.

По-перше, розглянемо НСД 15 та 17: (15,17) = 1, отже конгруенція має єдиний

розв’язок. Спростимо конгруенцію за властивостями: 25 і 15 мають спільний множник 5, який є взаємно простим з модулем 17. Отже, використовуючи властивості конгруенції,

38

можемо поділити конгруенцію на 5: 3x ≡ 5(mod17) Число 5 відповідає абсолютно найменшому лишку -12, який є кратний числу 3, отже 3x ≡ −12(mod17), скоротимо на 3: x ≡ −4(mod17). Отже конгруенція має єдиний розв’язок з повної системи абсолютно найменших лишків за модулем 17, або розв’язок з повної системи найменших додатних лишків: x = −4 + 17 = 13

б) Розв’язати конгруенцію: 5x ≡ 8125 − 629 (mod 7)

Розв’язання.

(5,7) = 1 - розв’язок 1. У конгруенції складові можна заміняти відповідними лишками з мінімальних систем – узагальнення властивостей конгруенції. Отже

8125 − 629 ≡ 1125 − (− 1)29 (mod 7), Вихідна конгруенція зміниться так:

5x ≡ 2(mod 7), − 2x ≡ 2(mod 7), . Відповідь: x ≡ −1(mod 7) або x ≡ 6(mod 7)

d. Використання підходящих дробів для розв’ язку конгруенцій.

Випадок ax ≡ b(mod m) , (a, m) = 1. Розкладемо у неперервний дріб відношення

З властивостей підходящих дробів відомо: PnQn−1 − Qn Pn−1 = (− 1)n , отже

mQn−1 − aPn−1 = (− 1)n . Враховуючи, що Qn−1 ціле число, можна mQn−1 вважати за модульний період, який можна відкинути. Тобто маємо aPn−1 = (− 1)n−1 mod(m). Помножимо ліву і праву частину на число (−1)n b :

a(− 1)n−1 bPn−1 ≡ b(mod m).

Отже, розв’язок конгруенції буде: x ≡ (− 1)n Pn−1b(mod m)

39

Із схеми маємо:

Отже, x º 81(mod 337)

e. Розв’ язання конгруенцій типу 2k x º b(mod m), (2, m) = (2, b) = 1

2k x = b + mt Обираючи t = 1 або t = −1 отримуємо b ± m º 0(mod 2s ). Чим більший степінь 2, ти краще. Нехай δ найбільший степінь 2, такий, що 2δ | b ± a . Якщо δ > k , маємо:

x = b ± m (mod m) 2k

Якщо δ < k , скорочуємо конгруенцію на 2δ та повторюємо процедуру для

еквівалентної конгруенції 2k −δ x = b ±δm (mod m) 2

Приклад:

Розв’язати конгруенцію: 256x º 179(mod 337)

Розв’язання.

256 = 28 , отже можна вихідну конгруенцію подати так:

28 x º 179(mod 337)

а)Обчислимо b + m = 179 + 337 = 516 = 22129 b + m º 0(mod 4)

b - m = 179 - 337 = -158 = -2 × 79 b - m º 0(mod 2)

Обираємо b + m = 516 . Найбільша степінь 2, яка ділить b + m є 2 < 8 , отже переходимо до еквівалентної конгруенції:

Питання 3 Обернений елемент за множенням. Повернення до питання про системи лишків, як структури теорії груп.

Отримавши правила для розв’язання конгруенцій з одним невідомим, можемо дати відповідь на питання:

ДЛЯ ЯКИХ ЕЛЕМЕНТІВ ПОВНОЇ СИСТЕМИ ЛИШКІВ ЗА ДОВІЛЬНИМ МОДУЛЕМ m ІСНУЄ ОБЕРНЕНИЙ ЕЛЕМЕНТ З МНОЖЕННЯ?

Щоб дати відповідь на це питання, треба розглянути розв’язання конгруенції ax º 1(mod m)

Виходячи з вимог існування розв’язку такої конгруенції – (a, m) = 1, бо права частина

конгруенції дорівнює 1. Якщо за a взяти елементи повної системи залишків (як базу для всіх класів чисел за модулем m ), то очевидно, що конгруенція не завжди буде мати розв’язок. Наприклад, m = 15, a = 5 . Отже, з повної системи треба відкинути всі елементи,

кратні модулю. Отримаємо зведену систему лишків, кількістю j(m) елементів. Для будь

40