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

4.  Якщо один з боків конгруенції і модуль діляться на деяке число, то і інший бік ділиться на це число.  (за 3-ю властивістю подільності)

5.  Якщо

3.2 Повна та зведена системи лишків

1. Повна система лишків.

Усі числа, які мають однаковий залишок  від ділення на деякий модуль  створюють клас чисел по модулю . Усі числа цього класу можна отримати з формули ділення числа із залишком , якщо надавати неповній частці  усіх значень з множини цілих чисел.

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

Кожне число з певного класу носить назву лишку відносно усіх інших чисел класу. Якщо  то лишок  є найменшим додатним лишком.

Найменший лишок за абсолютною величиною називається абсолютно найменшим лишком і позначається .

Приклад: Візьмемо за модуль число . Тоді найменшими додатними лишками будуть числа . Для кожного з них можна записати клас чисел по модулю 7:

При цьому, створюючи відповідний клас , неповна частка  пробігає всю множину цілих чисел.

Абсолютно найменшими лишками за модулем 7 будуть числа

Якщо порівняти їх з найменшими додатними лишками, можна помітити, що для лишків , а для .

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

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

Найменші додатні лишки  складають повну систему. Абсолютно найменші лишки  для  непарного і  для  парного теж складають повну систему лишків.

Узагальнення:

1. Будь які  чисел, які попарно не конгруентні за модулем  складають повну систему лишків за цим модулем.

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

Приклад. Перевірити, чи складає сукупність чисел повну систему лишків за модулем 8.

Розв’язання: Повна система лишків за модулем 8, складена з найменших додатних лишків є . Необхідно впевнитися, що дана сукупність чисел складає конгруенції за модулем 8 такі, які входять до повної системи.

.

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

2. Зведена система лишків.

Згідно із властивістю лишків числа одного і того ж класу лишків за модулем  мають з  однаковий НСД: . Серед множини класів лишків за певним модулем  розглянемо такі класи лишків, у яких , тобто класи , взаємо прості з модулем . Якщо взяти з кожного такого класу по числу, то складеться зведена система лишків за модулем . Зазвичай зведену систему лишків виділяють з найменшої додатної системи лишків, або з абсолютно найменшої системи лишків.

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

Приклад: 1. , отже зведена система лишків за модулем 130 складається з 48 чисел, взаємно простих з 130.

2. , отже зведена система лишків за модулем 16 складається з 8 чисел, взаємно простих з 16, ці числа такі: . Ці числа і складають зведену систему лишків для числа 16.

Узагальнення:

1. Будь які  чисел, попарно не порівняльні за модулем  та взаємно прості з модулем, створюють зведену систему лишків.

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

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

Розглянемо повну систему лишків (наприклад повну систему найменших додатних лишків) за модулем , яка створює  попарно не конгруентних класів. Позначимо цю систему:

.

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