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

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

Щоб скласти алгоритм обчислення будь якого підходящого дробу , позначимо та . Зауважимо, що у кожному підходящому дробу достатньо замінити на . Тоді

.................................................................................................................

Отже, для обчислення будь якого нам необхідно обчислити

та

Для обчислення зручно застосувати схему:

і	0	1	2	*....*	*і-2*	*і-1*	і	*...*	*n-1*	n
				*....*				*....*
	1			*....*				*....*
	0	1		*....*				*....*

Останні 2 рядки використовуються тільки у разі, коли дріб такий, що не скорочується.

Приклад. Розкласти у неперервний дріб . Дріб такий, що не скорочується. Розкладемо за алгоритмом Евкліда:

Отже,

Наведена схема має вигляд:

і	0	1	2	3	4	5	6
		11	1	1	1	1	2
	1	11	12	23	35	58	151
	0	1	1	2	3	5	13

Тобто дріб має такі підходящі дроби:

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

Властивості схеми розкладання:

1. Для усіх маємо: .

Дійсно,

і т. д.

2. Для усіх маємо

Дійсно,

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

2 Найважливіші функції в теорії чисел.

2.1 Функції виділення цілої та дробової частини дійсного числа.

1. Функція виділення цілої частини дійсного числа хповертає найбільше ціле число, яке не перевищує х:

Приклади:

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

Приклади:

Приклад застосування функції виділення цілої частини:

Визначити степінь простого числа , з яким це число входить до числа .

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

У числі множників, які кратні буде . Серед них множників, кратних буде , і т. д. доти, доки , а . Отже загальна кількість входжень до буде:

Приклад. Знайти з яким степенем число входить до числа

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

Дійсно,

Порахувавши усі степені 2, будемо мати:

2.2 Мультиплікативні функції.

Функція називається мультиплікативною, якщо для неї виконуються 2 умови:

1. визначена для усіх і хоча б для одного .

2. Для будь яких виконується:

Приклад - , де

Властивості мультиплікативних функцій.

1. Для будь якої мультиплікативної функції

Доведення:

Якщо розглянути попарно простих чисел, то

, зокрема

Наприклад, задамо мультиплікативну функцію так: . Тоді для довільного цілого числа будемо мати:

, зокрема:

2. Добуток двох мультиплікативних функцій – функція мультиплікативна:

Доведення:

- задана функція.

3. Нехай - довільне ціле число, - довільна мультиплікативна функція, - множина усіх дільників виду .

Тоді

Доведення:

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

Приклади:

Кількість дільників числа .

Введемо мультиплікативну функцію . Розглянемо для цієї функції 3-ю властивість мультиплікативних функцій:

Ліва частина: - кількість дільників числа

Права частина: ,

Отже, кількість дільників числа дорівнює добутку степенів усіх простих чисел, що входять до канонічного розкладу числа, збільшених на 1. Позначимо функцію визначення кількості дільників числа, як . Тоді: