Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
4. Открытым ключом Пикары должно быть у; подписание документа состоит в том, что Пикара убеждает Вивалеса, что ей известно значение дискретного логарифма этого числа.
5. Знание разложения на простые множители позволяет извлекать-тевадрат-ный корень, используя метод, приведенный в конце §11.2, вместе с китайской теоремой об остатках (см. также упражнение 5 к §1 V.2). Обратно, допустим, что нам известен алгоритм извлечения квадратного корня. Тогда выберем случайное число X и применим этот алгоритм к наименьшему неотрицательному вычету х2 по модулю п. В результате получим такое х', что х'2 = х2 (mod п). С вероятностью 0,5 оказывается, что х' 55 ±i (mod п). В этом случае сразу получаем нетривиальный делитель как НОД (х1 + х, п). Повторив процедуру T раз, с вероятностью 1 — 2~Т получим искомое разложение.
6. Да. Предположим, что некто Пикараг, играющая роль Пикары, перехватила сообщение bvi, bV2, «і, аг, посланное Пикарой Вивалесу, и с помощью этого хочет обмануть Вивалеса, внушив ему, что она сама знает разложение числа п (или раскрашивание в три краски, или дискретный логарифм числа и т. п.). Представим себе теперь, что Вивалес не удовлетворяется получением от Пикары2 точным повторением четверки, посланной Пикарой. Не зная ни секретных случайных чисел у\,уг Пикары, ни ее сообщений 7711,7712, ни дискретного логарифма хотя бы одного из чисел ?i и ?i, Пикараг не сможет построить другую четверку, которая создала бы у Вивалеса впечатление, что она знает разложение.
ОТВЕТЫ К УПРАЖНЕНИЯМ
243
7. Пикара выбирает случайно 0 ^ х' < TV и посылает Вивалесу у' = bx>. Два сообщения для скрытой передачи — это mi = х' и rai = х + х' (mod TV). Вивалес проверяет выполнение условий либо Ьх = у', либо bx+x = з/з/'. Если процедура повторяется T раз, то Пикаре может повезти лишь в одном из 2Т случаев (т. е. Пикаре удастся убедить Вивалеса в том, что она знает дискретный логарифм у, когда на самом деле не знает его).
8. Вивалес довольно легко может заставить Пикару выдать разложение числа га следующим образом. Он выбирает случайно целые числа z до тех пор, пока не найдет z, символ Якоби которого по модулю га равен —1. Тогда он посылает Пикаре у = z2 (mod га). Пикара отвечает величиной х2 квадратного корня из у (mod га), отличного от ±г. Теперь Вивалес может найти нетривиальный делитель числа га, а именно, НОД (х2 + z, га).
9. Доказательство отсутствия разглашения при передаче, использующее введение «имитатора» Клайда, здесь не работает. Другая проблема состоит в том, что Пикара должна быть уверена, что каждое з/,- получено из Центра, а не от Вивалеса, выдающего себя за Центр.
UV.1
1. а) 4, 11. б) 8, 13. в) См. часть г), г) Показать, что га —1 ее р — 1 (mod 2р— 2); таким образом, б""1 ее 1 (mod р) и 6n_1 ее ft(2p-i-i)/2 = (^-^-) (mod 2р - 1).
Тогда 6n_1 ее 1 (mod р(2р — 1)) равносильно ( 2pb_ 1) = 1.
2. а) Использовать сравнение га = га'р = га'(р — 1 + 1) ее га' (mod р — 1). б) Использовать п. а) с га' = 3, чтобы заключить, что р должно быть делителем 22 — 1, 52 — 1, 72 — 1. в) р должно быть делителем 24 — 1, 54 — 1, 74 — 1. г) Согласно п. б) любое меньшее га должно быть произведением двух простых чисел, больших 5. Затем проверить 49 и 77.
3. Поделить сравнение (1) с га = р2 на сравнение bp2~p ее 1 (mod р2), которое всегда выполняется согласно теореме Эйлера (предложение 1.3.5).
4.. а) 217. б) 341.
5. а) Предположим сначала, что га — псевдопростое по основанию 6. Так как га — 1 = pq — 1 = д — 1 (mod р — 1), то б'-1 ее 1 (mod р). Однако по малой теореме Ферма всегда 6Р_1 ее 1 (mod р). Так как d представляется как целочисленная линейная комбинация р — 1 и q — 1, то bd ее 1 (mod р). Меняя ролями р и q, получаем, что bd ее 1 (mod q), откуда следует, что bd ее 1 (mod га). Обратное утверждение доказывается аналогично (фактически —легче). В (Z/raZ)* имеется d2 оснований, б) Четыре: ±1, ±(4р + 1). в) d2/(p(341) = 100/300 = 1/3.
7. а) См. п. б), б) Имеем /V-I = Ъ(Ъп~1 - 1)/(Ь - 1). Так как га есть псевдопростое по основанию Ь, числитель делится на га; знаменатель взаимно прост с га, поэтому ra|(TV — 1). Так как 6" ее 1 (mod TV) (а именно, (4 — I)TV = 4" — 1), имеем bN~l ее 1 (mod TV). Нужно еще убедиться, что TV составное и нечетное. То, что TV составное, следует из того, что составным по предположению является п (см. следствие предложения 1.4.1). Разложение JV = б"-1 + bn~2 + ¦ ¦ ¦ + b +1 показывает, что TV нечетно (4 при этом может быть как четным, так и нечетным), в) Начиная соответственно с 341, 91, 217, использовать п. б) для построения возрастающей последовательности псевдопростых. Заметить, что условие НОД (4 — 1, n) = 1 всегда выполнено при 4 = 2,3,5. г) Число 15 — псевдопростое по основанию 4, однако TV = (415 — 1)/3 таковым не является. Чтобы убедиться в этом, заметьте, что 4 имеет в (Z/TVZ)* порядок 15, однако TV — 1 = 4(414 — 1)/3 не делится на 3, не говоря уже о 15.
244
ОТВЕТЫ К УПРАЖНЕНИЯМ
8. a) n = ( 6^-11)(Ьь+і )¦ б) Заметьте, что п нечетно (см. указание к 7 6)), следовательно, 2\(п— 1). Далее, так как (n — 1)(62 — 1) = 62(62(р-1) — 1) = 0 (mod р) и р не делит (6 + 1)(4 — 1) = б2 — 1, то р\(п — 1). в) Так как п — нечетное составное число, b2p = 1 (mod п) и 2р\(п — 1), то п — псевдопростое по основанию 6. Так как существует бесконечно много простых чисел, больших 4 + 1, то можно получить бесконечно много псевдопростых чисел по основанию 4.
