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

Додавання: Оскільки конгруенції можна додавати без зміни модуля, отже результат додавання лишків з різних класів повної системи буде належати до цієї самої системи.

Причому для додавання виконуються властивості:

1.  - комутативність;

2.  - асоціативність;

3.  - клас, що є нейтральним елементом по додаванню;

4.  - клас, що є оберненим елементом по додаванню.

Висновок: Повна система лишків створює абелеву групу по додаванню.

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

Причому для множення виконуються властивості:

1. ;

2.  - дистрибутивність для лівого множника;

3.  - дистрибутивність для правого множника.

Висновок: Повна система лишків створює напівгрупу по множенню

Ніяких обмежень на значення модуля  при цьому не накладалося.

Висновок: Повна система лишків за будь яким модулем  з операціями додавання та множення створює кільце.

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

У випадку, коли модуль – просте число  існування одиничного елементу відносно множення для повної системи лишків доводить мала теорема Ферма.

 Мала теорема Ферма.

Розглядаються цілі додатні числа: довільне ціле  та просте число . Якщо , то завжди вірно:

Якщо записати у термінах модульної арифметики, то теорема Ферма набуває вигляду:

, або, використовуючи властивості конгруенцій,

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

Теорема Ейлера (узагальнення малої теореми Ферма):

Для двох довільних цілих додатних чисел  та , таких, що , вірно:

,

де  - функція Ейлера, кількість чисел, менших за  і взаємо простих з ним.

Якщо  - просте число, функція Ейлера буде , а теорема Ейлера прийме вигляд:

, що відповідає малій теоремі Ферма. Тобто теорема Ейлера розповсюджує результат теореми Ферма на будь який складний цілий модуль.

Висновки:

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

2. За складеним модулем  одиниця з множення існує тільки на класах зведеної системи лишків.

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

4 Конгруенції з одним невідомим.

4.1 Основні відомості.

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

,                                    (1)

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

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

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

Теорема:

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

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

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

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

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

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

Конгруенція прийме вигляд: