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

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

, або

 - мультиплікативна функція, для якої, за умови, що , сума дільників числа  дорівнює:

Приклад. Знайти суму дільників числа 1. ; 2.

Розв’язання: 1. ;

2.,

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

Функція Ейлера визначає для довільного цілого додатного числа  кількість чисел з ряду цілих , взаємо простих з числом , тобто таких, що

Позначається функція Ейлера:

Приклади:  - за означенням.

 - перед 2 є одне просте число – 1.

 - взаємо прості з 3 – 1,2

 - взаємо прості з 4 – 1,3

 - взаємо прості з 5 – 1,2,3,4

 - оскільки 13 – просте, то увесь ряд чисел до цього числа є взаємо простий з ним.

Розглянемо канонічне подання довільного цілого . Для довільного цілого функція Ейлера буде мати вигляд:

, або

, зокрема

1. для  - простого числа - 

2. для  - степені простого числа -

Функція Ейлера є мультиплікативною функцією.

Приклади:

3 Порівняння (конгруенції). Властивості порівнянь

3.1 Основні поняття та теореми.

Розглянемо ділення із залишком цілих чисел на деяке певне ціле число , яке будемо називати модулем. Подання довільного цілого через неповну частку та залишок розглядалося в п. 1.1: . Серед множини цілих чисел, знайдуться такі, які діленням на модуль  дадуть різні неповні частки і однаковий залишок.

Наприклад, якщо за модуль узяти , то можна навести ряд чисел, які діленням на 7 дають залишок 1:

Числа, які від ділення на модуль  дають рівні залишки  називаються рівно залишковими, або конгруентними (порівнянними) за модулем .

Конгруенція чисел  і  за модулем  записується так:

 

Такі твердження є еквівалентними з конгруенцією  і :

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

2.

Приклад: Розглянувши попередній приклад, можемо записати:

Ділення будь якого натурального числа можна подати двічі, наприклад:

, або , що відповідає 2-м поданням через конгруенції:

Отже у загальному випадку будь яке число можна подати через конгруенцію так:

 або

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

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

·  Для конгруенцій вірними є такі закони рівностей:

o  рефлективність –  

o  симетричність – якщо , то

o  транзитивність – якщо ; , то

·  Інші властивості конгруенцій, які відповідають властивостям рівностей.

1.  Конгруенції можна додавати:

Дійсно, . Додамо дві рівності:

, отже

Властивість розповсюджується на довільну кількість порівнянь.

2.  Доданок з будь якого боку конгруенції можна перенести у інший бік із зміною знаку:

Дійсно, розглядаючи за законом рефлективності конгруенцію , додамо її до вихідної , отримаємо

3.  Оскільки , то до кожної з частин конгруенції можна додати будь яке число, кратне модулю.

4.  Конгруенції можна перемножати:

Властивість розповсюджується на довільну кількість порівнянь.

5.  Обидві частини конгруенції можна піднести до однієї і тієї ж степені:

Якщо

6.  Обидві частини конгруенції можна помножити на однакове число .

Вірним є , отже за властивістю 5 маємо

7.  Узагальнення: Якщо у виразі поліному від  змінних із сталими коефіцієнтами

 замінити  на , порівнянним  за модулем  і змінні  замінити на порівняні з ними по модулю  змінні , то новий вираз поліному  буде порівнянним з вихідним виразом по модулю .

Для доведення використовуються властивості 1-7.

Зокрема, для полінома -го степеня від однієї змінної:

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

·  Властивості, які належать тільки конгруенціям.

1.  Обидві частини конгруенції і модуль можна помножити на одне й те саме число.

2.  Обидві частини конгруенції і модуль можна розділити на будь який їх спільний множник

3.  Якщо  та  можуть бути конгруентними по декількох модулях , то конгруенція  і  вірна і за модулем, рівним НСК .

Оскільки  ділиться на кожний з модулів , то воно повинно ділитися і на НСК цих модулів, тобто .