Теоретико-числовые функции

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:22, 12 июля 2015.

Теория Чисел - древняя наука.

Она связана с ТФКП, численными методами.

С 70-х годов (раб. Диффи и Хеллмана) стала применяться в криптографии (ранее не имела приложений).

Все современные алгоритмы с открытым ключом основаны на Теоретико-Числовых Методах.


Возьмем действительное число - и на его примере введем следующие определения:

Определение 1: целой частью числа называется (максимальное целое число , не превосходящще ).

Определение 2: дробной частью числа называется (разность числа и его целой части).

Пример 1:

Теперь перейдем к определениям функций:

Определение 3: мультипликативной называется функция такая, что:

1) (существует такое , для которого функция не равна 0);
2) НОД (для любых взаимнопростых чисел мультипликативная функция произведения равна произведению мультипликативных функций).

Из данного определения вытекают следующие свойства мультипликативных функций:

Доказательство: возьмем такое число , что (в силу первого условия мультипликативности , такое существует). Тогда

что и требовалось доказать.

  • и - мультипликативны - мультипликативна (произведение двух мультипликативных функций мультипликативно)

Доказательство: , следовательно, выполняется первое условие мультипликативности функции. Возьмем НОД, для них

следовательно, выполняется второе условие мультипликативности функции. Таким образом, удовлетворяет всем условиям мультипликативности, объявленным в определении мультипликативна, что и требовалось доказать.