Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
квадратный корень по модулю р"1, см. упражнение 20 к §11.2). Тогда любое 6 ее ±aj (mod р"1 ) является основанием, по которому п — сильно псевдопростое, так как тогда 42' ее ( — 1)' = —1 (mod га). Выбрать 4i и 4г так, чтобы 6i = aj (modpj1), 42 ее (-lY'aj (modpj'), j = 1.....г, где (єі,...,єг) — любой набор из 0 и 1, отличный от (0,...,0) и (1,...,1). Далее показать, что если b = 6162, то Ь2' ее 1 (mod га), а Ь' ее b её ±1 (mod п).
24. а) В этом случае получается число с, не равное ±1 и квадрат которого равен 1; тогда НОД (с 4-1, га) — нетривиальный делитель п. б) Выбрать р и q так, чтобы р—1 и q — 1 не имели большого общего делителя (см. выше упражнение 5).
§ V.2
1. НОД (г5 - х3, га) = НОД (21 - 63, 91) = 7; 91 = 7 • 13.
2. НОД (z6 - Z3, n) = НОД (2839 - 26, 8051) = 97; 8051 = 83 • 97.
3. НОД (Z9 - Z7, п) = НОД (869 - 3397, 7031) = 79; 7031 = 79 • 89.
4. НОД (z6 - х3, п) = НОД (630 - 112, 2701) = 37; 2701 = 37 ¦ 73.
5. Доказать индукцией по к, что для 1 ^ к ^ г вероятность того, что Z0, ii,..., H-I все различны, а хк равен одному из предыдущих Ij, равна 1/г. При к = 1 вероятность того, что /(io) = хо, равна 1/г. Шаг индукции проводим следующим образом. По предположению индукции вероятность того, что к не меньше минимального значения t, удовлетворяющего условию Zj = Xj при не-
246
ОТВЕТЫ К УПРАЖНЕНИЯМ
некотором j < А;, равна 1 — = Г~С*~1). Если это событие происходит, то
для f(xk-i) существует г — А; + 1 возможных значений, так как / — биекция и потому f(xk-i) не может принимать ни одно из значений f(xj), 0 < > < Jt — 2. Из г — (к — 1) возможных значений одно — это хо, а другие не равны Z0, х\,..., Хк-\¦ Таким образом, лишь в одном из г — к + 1 случаев значение хь совпадает с более ранним значением (а именно, когда х\. = /(x^-i) = xq). Вероятность того, что одновременно произойдут два события, — 1) ни один из не совпадает
со своими предшественниками и 2) ц = іо — равна произведению вероятностей этих событий, т.е. -——— ¦ r_^_t\ — ~- б) Так как все значения от 1 до г
равновероятны, среднее равно і YI = I ^ = ^г(г + 1)/2 =
6. Предположим, что а и га взаимно просты (если бы это было не так, мы сразу нашли бы делитель га, вычислив НОД (а, га), и могли бы не использовать ро-метод). Тогда отображение /: х —> ах + 4 есть биекция Z/rZ на себя для любого г\п. Поэтому математическое ожидание числа шагов до первого повторения какого-либо значения по модулю г — величина порядка г/2 (по упражнению 5 6)), а не у/г, т. е. значительно больше.
7. а) 2* = 2і (mod г — 1). б) / = s и к = s + тп, где тп — порядок 2 по модулю t, т.е. такое наименьшее натуральное число, что 2m = 1 (mod t). Число т есть также период двоичного разложения 1/t; в этом можно убедиться, перейдя от равенства 2m — 1 = Ut к 1/t = и YIi=I 2_ml. в) Нередки случаи, когда к имеет порядок почти такой же величины, что и г; например, если г — 1 есть удвоенное простое число, а 2 — образующий по модулю этого простого числа (тогда s = 1, m = (г - 3)/2).
§V.3
1. а) (Использовать t = [у/її] + 1 = 93) 89 ¦ 97. б) (Использовать t = [у/п] -f 4 = 903) 823 • 983. в) (Использовать t = [у/п\ + 6 = 9613) 9277 • 9949. г) (Использовать t = [^/h~] + і = 9390) 9343 • 9437. е) (Использовать t = [у/її] + 8 = 75) 43 • 107.
2. Пусть га = ab и а > 4. Если а < у/ті + у/її, то b = п/а > п/(у/п + у/її) > у/Її — у/її. С другой стороны, если мы начинаем с 6 > ^/п — у/її, то должно быть а < у/її+ у/її+2, иначе было бы га = ab > (у/її+ у/п + 2)(у/п— у/її) = п + у/її—2 у/її > га (если га > 15; для меньших значений га упражнение 2 проверяется отдельно). Таким образом, в обоих случаях а — b < 2( ¦^n + 1). Но если факторизация Ферма «не срабатывает» для первого значения t, то s и t, соответствующие разложению п = ab, удовлетворяют условию t > у/її + 1 и, следовательно, s = y/t2 — га > у/(у/п + 1)2 — п = л/2~\7п + 1 > у/2 у/її, что при га > 33 противоречит неравенству
S= < ук+і.
3. а) Мы имели бы t2 — s2 = кп = 2 (mod 4), но по модулю 4 разность квадратов не может быть сравнима с 2. б) Мы имели бы t2 — s2 = 4га = 4 (mod 8). Это может быть, лишь когда s и t четны. Но тогда (t/2)2 — га = (s/2)2 и простая факторизация Ферма «сработала» бы так же хорошо.
4. а) (Использовать / = [-\/Зга] + 1 = 455) 149 • 463. б) (Использовать t = [уДп] + 2 = 9472) 3217 • 9293. в) (Использовать t = [уДп] + 1 = 9894) 1973 • 9923. г) (Использовать t = [уДп] + 2 = 9226) 1877 • 9067.
5.B = {2,3}; векторы (0,1) и (0, 1); 4 = 52 • 53 (mod п) = 55, с = 2 • З2 = 18; НОД (55 + 18, 2701) = 73; 2701 = 37 • 73.
6. В = {-1, 2, 3, 61}; векторы (1,0, 0, 0), (1, 0, 0,1) и (0, 0, 0, 1); 4 = 68 ¦ 152 • 153 (mod п) = 1555; с = 2•3•6I = 366; НОД (1555 + 366,4633) = 113; 4633 = 41-113.
7. а) Оценить разность, взяв сумму площадей «треугольных» областей между графиком log x и прямоугольниками римановой суммы, б) Сравнить J" log х Ax с
ОТВЕТЫ К УПРАЖНЕНИЯМ
247
суммой площадей трапеций, верхние стороны которых соединяют точки (J,logj), и показать, что площадь между кривой и трапециями ограничена константой, в) lirriy — oo^ log(j/!) - (log у - 1)) = 0; итак, ответ: log у - 1.
