Реферат: Научные проблемы Интернета

,

,

.

Тогда

.

Последняя сумма дает остаток от деления на m , равный . Но , . Поэтому

.

Теперь нетрудно это правило применить, скажем, к

7¹³ mod 8 = ?

Запишем

.

Имеем . Поэтому .

Обратимся теперь к формуле (6.16).

Пусть , , .

Найдем

.

Итак, . Это значение и будет передано по сети вместо x .

Теперь рассмотрим, как восстановить x по y , m , e . Для этой цели нужно найти число d , удовлетворяющее условию

,

(1.3)

где – значение функции Эйлера от числа m . Функция Эйлера вычисляется сравнительно просто. Так,

.

(1.4)

Если p простое число и r – целое, то

.

(1.5)

Формул (1.4) и (1.5) достаточно для того, чтобы найти функцию Эйлера для любого целого положительного числа. В нашем случае получаем:

.

Для любознательных читателей отметим, что значение равно числу целых чисел на отрезке 1..m , взаимно простых с m . Отыскание значения функции Эйлера для больших целых чисел является вычислительной задачей очень большой сложности.

Пример . . Все четыре числа: 1, 2, 3, 4 взаимно просты с m .

Теперь обратимся к уравнению (3.3). В этом уравнении d играет роль секретного ключа. Решить уравнение (3.3) путем перебора значений d можно, но если в числе m , например, 100 цифр, то на вычисление d уйдет достаточно много времени. Для небольших значений, таких как в нашем примере, можно воспользоваться алгоритмом решения уравнений в целых числах, который мы и приведем.

Итак, в нашем примере уравнение такое:

.

(1.6)

Уравнение (1.6) можно переписать следующим известным образом:

.

(1.7)

В (1.7) r и d неизвестные целые числа. Представим (1.7) в виде системы двух линейных неравенств.

,