Теория остатков

то единственное условие на выбор показателя степени в отображении (1) есть

Итак, лицо, заинтересованное в организации шифрованной переписки с помощью схемы RSA, выбирает два достаточно больших простых числа и . Перемножая их, оно находит число . Затем выбирается число , удовлетворяющее условиям (7), вычисляется с помощью (6) число и с помощью (3) - число . Числа и публикуются, число остается секретным. Теперь любой может отправлять зашифрованные с помощью (3) сообщения организатору этой системы, а организатор легко сможет дешифровывать их с помощью (5).

Для иллюстрации своего метода Ривест, Шамир и Адлеман зашифровали таким способом некоторую английскую фразу. Сначала она стандартным образом (a=01, b=02, ., z=26, пробел=00) была записана в виде целого числа , а затем зашифрована с помощью отображения (1) при

и . Эти два числа были опубликованы, причем дополнительно сообщалось, что , где и - простые числа, записываемые соответственно и десятичными знаками. Первому, кто дешифрует соответствующее сообщение

была обещана награда в 100$.

Эта история завершилась спустя 17 лет в 1994 г., когда D. Atkins, M. Graff, A. K. Lenstra и P. C. Leyland сообщили о дешифровке фразы, предложенной в [1]. Она1) была вынесена в заголовок статьи, а соответствующие числа и оказались равными

4 Функция Эйлера

Определение. Функция : R R (или, более общо, : C C ) называется мультипликативной если:

1). Функция определена всюду на N и существует а N такой, что ( а ) 0.

2). Для любых взаимно простых натуральных чисел а 1 и а 2 выполняется ( а 1 · а 2 ) = ( а 1 ) · ( а 2 ).

Пример 1. ( а ) = а s , где s - любое (хоть действительное, хоть комплексное) число. Проверка аксиом 1) и 2) из определения мультипликативной функции не составляет труда, а сам пример показывает, что мультипликативных функций по меньшей мере континуум, т.е. много.

Перечислим, кое-где доказывая, некоторые свойства мультипликативных функций. Пусть всюду ниже ( а ) - произвольная мультипликативная функция.

Свойство 1. (1) = 1.

Доказательство. Пусть а - то самое натуральное число, для которого

( а ) 0. Тогда ( а · 1) = ( а ) · (1) = ( а ).

Свойство 2.

,

где р 1 , р 2 , ., р n - различные простые числа.

Доказательство очевидно.

Свойство 3. Обратно, мы всегда построим некоторую мультипликативную функцию ( a ), если зададим (1) = 1 и произвольно определим ( р ) для всех простых р и всех натуральных , а для остальных натуральных чисел доопределим функцию ( a ) используя равенство

.

Доказательство сразу следует из основной теоремы арифметики.

Пример 2. Пусть (1) = 1 и ( р ) = 2 для всех р и . Тогда, для произвольного числа,

.

Свойство 4. Произведение нескольких мультипликативных функций является мультипликативной функцией.

Доказательство. Сначала докажем для двух сомножителей: Пусть 1 и 2 - мультипликативные функции = 1 · 2 , тогда (проверяем аксиомы определения)

1) (1) = 1 (1) · 2 (1) = 1 и, кроме того, существует такое a (это a = 1), что ( a ) 0.

2) Пусть ( a , b ) = 1 - взаимно просты. Тогда

( a · b ) = 1 ( a · b ) · 2 ( a · b ) =

= 1 ( a ) 1 ( b ) 2 ( a ) 2 ( b ) =

= 1 ( a ) 2 ( a ) · 1 ( b ) 2 ( b ) = ( a ) ( b ).

 Скачать реферат