Файл: Теорія чисел в криптографії.pdf

12 за теоремою Ейлера для довільного цілого числа a і довільного числа m такого, що (a ,m) = 1 число aϕ(m) від ділення на m завжди має у залишку число 1.

13 повна система лишків за довільним модулем m створює кільце.

Контрольні питання до теми №3.

1.Сформулюйте умову конгруентності двох чисел a і b .

2.Згадайте основні властивості конгруенцій.

3.Покажіть, що такі конгруенції не мають місця:

a )689 ≡ 13(mod 16); b )21138 ≡ 31(mod 49); c )8107 ≡ 7(mod 35)

4.В чому полягає умова, необхідна і достатня для того, щоб два числа a і b належали до одного класу за модулем m .

5.Дайте визначення лишку за певним модулем, найменшої додатної системи лишків, абсолютно найменшої системи лишків, зведеної системи лишків за певним модулем.

6.Із скількох елементів складається абсолютно найменша система лишків за модулем 13? Назвіть ці елементи.

7.Чи складає система лишків (6, 18, 39, 92, 155) повну систему лишків за модулем 5?

8.Із скількох елементів складається зведена система найменших додатних лишків за модулем 24? Назвіть ці елементи.

9.Сформулюйте малу теорему Ферма.

10.Сформулюйте теорему Ейлера.

11.Чи є комутативними операції додавання та множення в найменшій додатній системі лишків за певним модулем.

10.Яка величина є в найменшій додатній системі лишків за певним модулем є нейтральним елементом за додаванням. Чи існує єдиний обернений елемент за додаванням до кожного елементу найменшої додатної системи лишків за певним модулем?

12.Яка величина в найменшій додатній системі лишків за простим модулем є нейтральним елементом за множенням. Яка теорема присвячена цьому питанню?

13.Яку алгебраїчну структуру створює повна система лишків за певним модулем?

35

ТЕМА №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