Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
— 1 (mod р). Пусть теперь s' > s. Возведя обе части сравнения
,2""V 1 / J4 оя'-» , 2л'-1і' .(р-1)/2
0 ее —1 (mod р) в степень 2 , получаем о ее о ' ее (J) ее 1 (mod р). Утверждение доказано.
Вернемся к доказательству случая 2 предложения V. 1.6. Запишем п в виде произведения простых чисел (не обязательно различных): п = YIp. Представим также каждое р — 1 в виде р - 1 = 23 t', t' нечетно. Как было показано, s' ^ s и (^) = —1 лишь при s' = s. Число таких случаев обозначим через к (учитывая кратность, т.е. к
I а
со свойством s=s дает вклад а, если п делится на р и не делится на ра+1). Тогда (?) = П(р) = (_i)fc- Далее, если р— такой делитель п, что s' > s, то р ее 1 (mod 2S+1), а для остальных к делителей р числа п имеем S=SHp=I +t'23 ее 1 + 2s (mod 23+1). Так как п = 1 -f 2s t ее
1 + 2* (mod 2S+1), то п ее 1 + 2* ее Цр ее (1 + 23)* ее 1 + к2° (mod 23+1) (последнее — по формуле бинома Ньютона). Это показывает, что к должно быть нечетным, т.е. (^) = ( — 1)к = —1, что и требовалось доказать.
Случай 3. Предположим, наконец, что b ее —1 (mod п) для некоторого г, 0 < г < s (используем г — 1 вместо г в (3)). Имеем
тогда i/n 1^2 ее 1 (mod п), и нам нужно показать, что (-) = 1 в случае 3.
Пусть опять р — простой делитель п, р — 1 = 2s t', t' нечетно. Утверждение. Справедливы соотношения s ^ г и
M _ Г -1, если s = г, ру \ 1, если s > г.
Доказательство этого утверждения идентично доказательству соответствующего утверждения в случае 2.
Для доказательства предложения в случае 3 обозначим через к число простых р (не обязательно различных) в произведении п = J\p,
148
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
для которых выполнена первая альтернатива, т.е. s = т. Тогда, как и в случае 2, мы, очевидно, имеем (~) = ( — l)k. С другой стороны, так как п = 1 + 23* = 1 (mod 2Г+1) и п = Цр = (l + 2r)fc (mod 2Г+1), то к должно быть четным, т.е. (?¦) = 1. Это завершает доказательство предложения V. 1. 6.
Перед доказательством предложения V. 1. 7 мы докажем одну лемму общего характера о числе решений уравнения хк = 1 в «циклической группе», содержащей тп элементов. Мы уже однажды встречались с этой леммой в начале § II. 2; данное ниже доказательство следует сравнить с доказательством предложения П. 2.1.
Лемма 1. Пусть d — НОД (к,т). В группе {<7,</2,</3, ¦ ¦ ¦ ,дт =
1} порядка т имеется ровно d элементов, удовлетворяющих урав-
k . нению X =1.
Доказательство. Элемент gJ удовлетворяет этому урав-
Jk
нению тогда и только тогда, когда g = 1, т.е. в том и только том случае, когда jk = 0 (mod т), т.е. m\jk. Это эквивалентно условию 1JlJd- Но m/d и k/d взаимно просты, поэтому j кратно m/d. Среди чисел {1,2,..., т} имеется в точности d таких значений j.
Нам нужна еще одна лемма, которая доказывается аналогично предыдущей.
Лемма 2. Пусть р — нечетное простое число, р — 1 = 2s t', где і нечетно. Тогда число х Є (Z/pZ) , удовлетворяющих уравнению Xі 1 = — 1 (mod р) (і нечетно), равно нулю, если г ^ s', и равно 2ГН0Д (t, t'), если г < з.
Доказательство. Пусть g — образующий элемент группы (Z/pZ)* и X = g\ 0 < j < р - 1. Так как д^р~1^2 = —1 (mod р) и р — 1 = 2s t', то сравнение из условия леммы эквивалентно сравнению 2rtj = 2я ~lt' (mod 2s t') (с неизвестным j). Ясно, что при г > s — 1 оно не имеет решений. Если же г ^ s - 1, то делим обе части сравнения и модуль на НОД модуля и коэффициента при j, т.е. на 2rd, где d = НОД (t,t ). Получившееся сравнение по модулю 2s Г(^;) имеет единственное решение. Поэтому исходное сравнение имеет 2 d решений, как и утверждалось. Лемма доказана.
Доказательство предложения V. 1.7.
Случай 1. Предположим сначала, что п делится на квадрат простого числа р, т.е. pa||n, a ^ 2. Покажем, что в этом случае п не может быть даже псевдопростым (не говоря уже о сильной псевдопростоте) для более, чем (n - 1)/4 оснований b, 0 < 6 < п. Для этого предположим, от противного, что Ъп 1 = 1 (mod п), и, значит, bn~l = 1 (mod р2), и найдем условия, которым должен удовлетворять
§ 1. ПСЕВДОПРОСТЫЕ ЧИСЛА
149
2 2 *
вычет 6 по модулю р . Напомним, что (Z/p Z) — циклическая группа порядка р(р— 1) (см. упражнение 2 к § П. 1), т. е. существует такое целое число (7, что (Z/p2Z)* = {д,д2,д3,¦.. ,<7Р'Р 1^}- Согласно лемме 1, число решений сравнения 6™ 1 = 1 (mod р2) в (Z/p2Z)* равно d1 = НОД (р(р - 1),п — 1). Но р — делитель п, поэтому р не делит п — 1 и, следовательно, р не делит d. Стало быть, d ^ р — 1. Поэтому доля не делящихся на р чисел в интервале от 0 до п, обладающих свойством 6™ 1 = 1 (mod р ), не превышает РГ\ — р~+т ^ j- Так как эта величина оценивает сверху долю таких оснований 6, что 0 < 6 < п и 6™ 1 = 1 (mod п), то п может быть псевдопростым не больше, чем по четверти оснований 6, 0 < 6 < п. В случае 1 предложение доказано.
Замечание. Эта верхняя 25%-я граница достигается в случае 1 при п = 9 (т.е. 9 есть сильное псевдопростое для двух из 8 возможных значений 6, именно, для 6 = ±1).
С л у ч а й 2. Теперь предположим, что п — произведение двух различных простых чисел р и q: п = pq*. Пусть р — 1 = 2s t', t' нечетно, q - 1 = 2s t", t" нечетно. Без ущерба для общности можем предположить, что s' ^ s". Чтобы элемент 6 Є (Z/nZ)* мог служить основанием, по которому п является сильно псевдопростым, должно
