Информатика и выч. техника \ Криптография

Застосування теорії чисел в криптографії, страница 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-м поданням через конгруенції:

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

або

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

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

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

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

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

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

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

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

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

, отже

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

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

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

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

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

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

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

Якщо

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

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

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

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