Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
всех j, где В — некоторое число, превосходящее все модули. Предположим, ЧТО T также велико. Найти оценку для числа двоичных операций, необходимых для решения системы. Оценка должна быть функцией Виги должна охватывать случаи, когда г либо очень мало, либо очень велико по сравнению с числом двоичных знаков в записи В.
14. Применить метод повторного возведения в квадрат для нахождения числа 3875 (mod 103).
15. Сберегает ли время метод повторного возведения в квадрат при обычных арифметических операциях с целыми числами (в отличие от операций по модулю)? Объясните ответ, используя оценки вида О-большое.
16. Заметим, что для а, взаимно простого с р, ар~2 является обратным элементом кав кольце вычетов по модулю р. Предположим, что р очень велико. Сравнить метод повторного возведения в квадрат для вычисления ар~2 с алгоритмом Евклида (как эффективные способы отыскания a-1 (mod р)) в случаях, когда: а) а имеет примерно столько же цифр, что и р, и б) когда а много меньше р.
§ 3. СРАВНЕНИЯ
29
17. Найти •fi(m) для всех m от 90 до 100.
18. Перечислите все у?(п), для которых y?(n) ^ 12, и докажите, что ваш список полон.
19. Предположим, что п не является полным квадратом и что п — 1 > <р(п) > п — п2/3. Доказать, что п есть произведение двух различных простых чисел.
20. Если m ^ 8 есть степень 2, то показатель степени в предложении I. 3.5 можно заменить на і/з(т)/2. Доказать.
21. Пусть m = 7785562197230017200 = 2Л-З3-52-7-11 ¦ 13• 19-31 ¦37¦4I-61 -73-181.
а) Найти наименьший неотрицательный вычет числа 6647362 по модулю т.
б) Пусть а — целое положительное число, меньшее m и взаимно простое с т. Сначала найдите такое положительное число к, меньшее 500, что ак сравнимо с а-1 по модулю т. Затем опишите алгоритм возведения а в эту степень к, использующий операции по модулю т. Сколько умножений и делений потребует этот алгоритм (приведение по модулю т рассматривать как одно деление). Какое максимальное количество двоичных разрядов может быть в записи чисел, с которыми вы будете работать?
Наконец, укажите хорошую оценку числа двоичных операций, необходимых для отыскания a~l (mod m) этим способом (ваш ответ должен быть конкретным числом — без использования обозначений О-большое).
22. Проведите другое доказательство предложения E 3.7 следующим способом. Для каждого делителя d числа п обозначим через Sd подмножество в Z/nZ, состоящее из всех кратных n/d. Таким образом, Sd содержит d элементов.
а) Докажите, что Sd имеет tp(d) различных элементов х, которые порождают Sd в том смысле, что кратные х (рассматриваемые по модулю п) дают все элементы ИЗ Sd-
б) Докажите, что каждый элемент х порождает одно из подмножеств Sd и, следовательно, число элементов в Z/nZ равно сумме (взятой по всем делителям d) чисел элементов, порождающих Sd- Отсюда и из п. а) следует предложение I. 3.7.
23. а) Используя основную теорему арифметики, докажите, что Г] 1/(1—р-1), где произведение берется по всем простым р, стремится к бесконечности.
б) Используя результат а), докажите, что ряд, состоящий из дробей, обратных к простым числам, расходится.
в) Найти такую последовательность Uj, стремящуюся к со, для которой Нту-.по tp(rij)/nj = 1, и последовательность nj, для которой HmJ-^00 tp(nj)/nj = 0.
24. Пусть N — очень большое секретное число, используемое для разблокирования ракетной системы, т.е. знание N позволяет запустить ракету. Предположим, что есть командующий генерал и п генерал-лейтенантов. Чтобы застраховаться от ситуации, когда командующий генерал (который знает n) будет выведен из строя, желательно, чтобы каждый из генерал-лейтенантов обладал частичной информацией относительно n, достаточной для того, чтобы любые три генерал-лейтенанта могли бы, действуя согласованно, запустить ракеты (но никакие два из них не могли бы сделать этого).
а) Пусть pi,... ,рп — различные простые числа, каждое из которых больше, Vn, но значительно меньше y/n. Используя эти числа р,-, опишите частичную информацию о числе TV1 которую нужно предоставить генерал-лейтенантам.
б) Обобщите этот способ на случай, когда требуется, чтобы доступ к системе открывался при согласованном действии любых к генерал-лейтенантов (к ^ 2), а никакие к — 1 из них не могли бы разблокировать систему. Структура такого типа при п участниках называется (я, А;)-пороговой системой разделения секрета.
зо
ГЛ. І. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
§ 4. Некоторые применения к разложению на множители
Предложение 1.4.1. Для любого целого 6 и любого целого положительного п число 6 — 1 делится на b — 1, и частное имеет вид ь"-1+ Ьп~2 + ••• + 62 + 6+1.
Доказательство. Существует полиномиальное тождество, вытекающее из того, что 1 есть корень многочлена хп — 1 и, следовательно, разность X — 1 делит х — 1. При делении многочленов получается хп — 1 = (х — 1)(хп 1 + хп + • • • + х2 + х + 1). (Это тожде-
п-1 , п-2 , 2 , -,
ство можно получить также, умножая х на х +х +•••+Z +х + 1 и затем вычитая х +х +••• + 2:+2;+!; после приведения подобных членов получится X — 1.) Подстановкой 6 вместо X доказательство завершается.
