Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
15 = 21, 17 = 15
Глава 6. Теория чисел
225
и
\/29 = 21 ¦ 2 + 15 -1 = 22(mod35). Действительно, 222 = 484 = 29(mod 35). ?
6.3 Функция Эйлера "фи"
В разделе 5.2.3 определена функция Эйлера "фи" (определение 5.11). Перейдем к изучению ее свойств.
Лемма 6.1. Пусть ф(п) — функция Эйлера "фи". Тогда ' А 0(1) = 1;
2. если число р — простое, то ф(р) = р — 1;
3. функция Эйлера "фи" является мультипликативной, т.е. если gcd(m, п) = = 1, то ф(тп) = ф(т)ф(п);
4. если п = р^р^2 ¦ ¦ - р^* —разложение числа п на простые множители, то
\ *«-Н)Н)~Н)-
Доказательство. Утверждения 1 и 2 являются тривиальными и следуют непосредственно из определения 5.11.
Докажем утверждение 3. Поскольку ф{1) = 1, уравнение ф(тп) = ф(т)ф(п) выполняется, когда либо число п, либо число m равно единице. Допустим, что |ттг > 1 и п > 1, причем gcd(n,m) = 1. Рассмотрим следующий массив.
О 1
тп тп — 1
(п — 1)тп (п — l)m + 1
С одной стороны, массив (6.3.1) состоит из тп последовательных целых чисел, поэтому все они являются целыми по модулю тп, и, следовательно, среди них есть ф(тп) чисел, взаимно простых по отношению к числу тп.
С другой стороны, первая строка массива (6.3.1) состоит из чисел, целых по модулю т, а все элементы любого столбца сравнимы по модулю т. Следовательно, в массиве существует ф(т) столбцов, целиком состоящих из целых чисел, взаимно простых с числом т. Обозначим эти столбцы следующим образом.
Ь, т 4- Ъ, 2т + Ь,...,(п— 1)т + Ъ
2
т + 2
т — 1 т + (т — 1)
(6.3.1)
(п- 1)т + 2 ... (п- 1)т + (т - 1)
226
Часть II. Математические основы
Они состоят из тг элементов. Поскольку gcd(m, п) = 1, по теореме 6.6 каждьи такой столбец образует полную систему вычетов по модулю тг. Следовательно, в каждом таком столбце существует ф{п) элементов, взаимно простых по отношению к числу п. Итак, массив (6.3.1) содержит ф(тп)ф(п) элементов, взаимно простых по отношению к числу п. Кроме того, заметим, что любое число является взаимно простым по отношению к числам тип тогда и только тогда, когда оно является взаимно простым по отношению к числу тп.
Объединяя полученные результаты, приходим к выводу, что ф(тп) = = Ф(т)ф{п).
Докажем утверждение 4. Для любого простого числа р элементы кортежа 1,2,..., ре, не являющиеся взаимно простыми по отношению к числу ре, являются кратными числу р, т.е. равны р,2р,... ,ре~1р. Очевидно, что количество таю^ чисел равно ре-1. Итак,
ФУ
)=p*-p*-i = p*(l-l^
Эта формула верна для любой простой степени ре \ п, где ре+1 { п. Заметим^ что две разные простые степени числа п являются взаимно простыми числами. Учитывая утверждение 3, получаем требуемый результат.
В разделе 4.5 мы рассмотрели задачу SQUARE-FREENESS, в которой требо валось определить, делится ли нечетное составное целое число на квадрат какого либо простого числа? Для того чтобы доказать, что задача SQUARE-FREENESS принадлежит классу NV, мы применили функцию ф(п). В соответствии с утверждением 4 леммы 6.1 для любого простого числа р > 1 из условия р2 | тг следует, что р | ф(п). Вот почему в качестве свидетельства того, что число тг не делится на квадрат простого числа, мы использовали условие gcd(n, ф{п)) = 1. Читатели могут сами рассмотреть вариант, когда gcd(n, ф{п)) > 1 (особенно интересным является вариант, когда тг = pq, где р \ ф(а), описанный в упражнении 6.5).
Функция Эйлера "фи" имеет одно элегантное свойство.
Теорема 6.9. Для любого целого числа п > О выполняется условие ^2 Ф{д) — Щ
d\n
Доказательство. Пусть Sd = {% \ 1 ^ х ^ n,gcd(a;,n) = d}. Очевидно, что при каждом числе d | тг множество S = {1,2,..., тг} разбивается на непересекающиеся подмножества Sd- Следовательно,
(jsd = s. Щ
d\n
Глава 6. Теория чисел
227
Заметам, что для каждого числа d | п выполняется условие = 0(n/d). Следовательно,
d\n
Однако для любого числа d \ п выполняется условие (n/d) | п. Следовательно, ?>(n/d)= Yl 0(n/d) = J>(d).
d\n {n/d)\n d\n ?
Пример 6.3. При n = 12 условию d \ n удовлетворяют числа 1,2,3,4,6 и 12. Следовательно, 0(1) + 0(2) + 0(3) + 0(4) + 0(6) + 0(12) = 1 + 1 + 2 + 2 + 2 + + 4=12. ?
6.4 Теоремы Ферма, Эйлера и Лагранжа
В главе 4 мы рассмотрели малую теорему Ферма (сравнение (4.4.8)) и уже несколько раз применили ее, не приводя доказательства. Для того чтобы доказать ее, покажем, что она является частным случаем другой знаменитой теоремы теории чисел — теоремы Эйлера.
Теорема 6.10 (Малая теорема Ферма). Если число р — простое и р \ а, то аР~1 = l(modp).
Поскольку число р — простое, выполняется условие ф(р) = р — 1. По этой причине малая теорема Ферма является частным случаем следующей теоремы.
Теорема 6.11 (Теорема Эйлера). Если gcd(a,n) = 1, то cft^ = l(modn).
Доказательство. Из условия gcd(a, n) = 1 следует, что a(mod п) € Ъ*п. Кроме того, #Z* = ф(п). Учитывая следствие 5.2, получаем, что ordn(a) | Отсюда следует, что a^n) = 1 (modn). ?
Поскольку следствие 5.2, упомянутое в доказательстве теоремы 6.11, является непосредственным применением теоремы Лагранжа (теорема 5.1), можно утверждать, что малая теорема Ферма и теорема Эйлера являются частными случаями замечательной теоремы Лагранжа.
