Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 14

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 8 9 10 11 12 13 < 14 > 15 16 17 18 19 20 .. 125 >> Следующая


Следствие 3. Если a = b (mod т), с = d (mod т) и НОД (с, т) = 1 (в этом случае, конечно, НОД (d,m) = 1), то ас 1 = bd 1 (mod т) (где с и d обозначают целые числа, являющиеся обратными к с и d по модулю т).

Для доказательства следствия 3 рассмотрим сравнения с(ас 1 — bd ) = (асе — bdd ) = а — b = 0 (mod гп), и так как гп не имеет общих делителей с с, го гп должно делить ас 1 — bd 1.

Предложение 1.3.2 (Малая теорема Ферма). Пусть р — простое число. Любое целое число а удовлетворяет сравнению ар = a (mod р), и любое целое число а, не делящееся на р, удовлетворяет сравнению ар = 1 (mod р).

Доказательство. Предположим сначала, что р /а. Покажем, что Oa, la, 2a, За,..., (р — 1)а есть полная система вычетов по модулю р. В самом деле, если бы какие-либо два из этих чисел, скажем ia и ja, принадлежали одному классу вычетов, т. е. ia = ja (mod р), это означало бы, что p\(i — j)a, а так как а не делится на р, мы получили бы p\i — j. Так как і и j меньше р, это возможно лишь в случае і = j. Таким образом, числа а,2а,... ,(р — 1)а, рассматриваемые по модулю р, являются перестановкой чисел 1,2,... ,р — 1. Отсюда следует, что произведение всех чисел первого набора сравнимо по модулю р с произведением чисел второго набора, т. е. ар (р—1)1 = (р-1)! (mod р). Получаем, что р\(р - 1)!(ар 1 - 1). Так как (р — 1)! не делится на р, получим p|ap_1 — 1, что и требовалось доказать. Наконец, если умно-

§ 3. СРАВНЕНИЯ

23

жить обе части сравнения ар~ = 1 (mod р) на а, получится первое сравнение из утверждения теоремы для случая, когда а не делится на р. Если же а делится на р, то сравнение ар = a (mod р) является тривиальным, так как обе части его сравнимы с нулем по модулю р. Это завершает доказательство предложения.

Следствие. Если а не делится на р и если п = т (mod (р — 1)), то a = a (mod р).

Доказательство следствия. Пусть п > т. Так

как р — 1\п — т, то п = т + с(р — 1) для некоторого положительного

целого с. Умножив почленно с сравнений ар = 1 (mod р) и сравнение

а = а (mod р), получим искомый результат: а = а (mod р).

Пример 2. Найти последнюю цифру в семиричной записи чи-Оюооооо ела 2

Решение. Пусть р = 7. Так как 1000000 при делении на р—1 = о дает остаток 4, получаем 2 = 2 = 16 = 2 (mod 7), и,

значит, последняя цифра равна 2.

Предложение 1.3.3 (Китайская теорема об остатках). Пусть требуется решить систему сравнений по различным модулям:

X = а-[ (mod Tn1), X = а2 (mod т2),

X = ar (mod mr),

причем любые два модуля взаимно просты: НОД (m^mj) = 1 для і ф ]¦ Тогда эта система разрешима и любые два решения сравнимы по модулю M = Tn1Tn2 • • -тТ.

Доказательство. Сначала докажем единственность по модулю M (последнее утверждение теоремы). Пусть X и х" — два решения системы. Положим х = х'~ х". Тогда х сравним с нулем по любому модулю тп;, а значит, и по модулю M (по пятому свойству сравнений). Теперь покажем, как найти решение х.

Обозначим через Mj = М/тп, произведение всех модулей, кроме г-го. Очевидно, что НОД (m,-,M,-) = 1 и, следовательно, существует такое целое Ni, что MjTV1- = 1 (mod тп^) (число TV1- может быть найдено, например, по алгоритму Евклида). Положим теперь х = 5^1-O1-MjJVj. Тогда для каждого і все слагаемые в этой сумме, за исключением г-го, делятся на тп;, так как m,-|Mj для всех і ф j. Таким образом, для каждого і имеем х = OjMjTVj = а{ (mod тп;), что и требовалось доказать.

Следствие. Функция Эйлера обладает свойством «мультипликативности», т. е. ip(mn) = </p(m)(/p(n), если НОД (т,п) = 1.

24

ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ

Доказательство следствия. Для доказательства необходимо подсчитать количество целых чисел между нулем и тп—1, не имеющих общих делителей с тога. Для каждого j из этого множества обозначим через j1 наименьший неотрицательный вычет по модулю т (т. е. О ^ ji < т и j = Ji (mod т)) и через j2 наименьший неотрицательный вычет по модулю п (т.е. О ^ J2 < п и j = J2 (mod п)). Из китайской теоремы об остатках следует, что каждой паре J1, J2 соответствует одно и только одно число j в промежутке от 0 до тп — 1, для которого j = j1 (mod то) и j = J2 (mod п). Заметим, что число j не имеет общих делителей с тп тогда и только тогда, когда оно не имеет общих делителей с то (это эквивалентно взаимной простоте j1 и то) и не имеет общих делителей с п (что эквивалентно взаимной простоте J2 и п). Таким образом, числа j, взаимно простые с тога, находятся во взаимно однозначном соответствии с парами j\,j2, для которых 0 ^ j1 < то, НОД (j'i,to) = 1, 0 ^ j2 < га, НОД (j2, га) = 1. Число возможных значений для j1 равно <р(т), а для j2 равно <f(n). Итак, число пар равно ip(m)ip(n). Следствие доказано.

Поскольку каждое число га может быть представлено в виде произведения степеней различных простых чисел и уже установлена формула (р(ра) = р°(1 — р 1), следствие означает, что при n = Pi1P22 ¦ ¦ -р"г

Из формулы для <р(п) выводится следующее утверждение, которое будет использовано при обсуждении криптосистемы RSA с открытым ключом.
Предыдущая << 1 .. 8 9 10 11 12 13 < 14 > 15 16 17 18 19 20 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed