Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
УПРАЖНЕНИЯ
1. а) Найти все основания Ь, для которых 15 — псевдопростое число (не включать тривиальные основания ±1).
б) Найти все основания, для которых 21 — псевдопростое число.
в) Доказать, что существует 36 оснований 6 Є (Z/91Z)* (т.е. половина всех возможных оснований), для которых 91 — псевдопростое число.
г) Обобщая часть в), показать, что если р и Ip — 1 — простые числа и n =
152
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
р(2р — 1), то п — псевдопростое для 50% возможных оснований 6, а именно, для тех 6, которые являются квадратичными вычетами по модулю 2р — 1.
2. Пусть п — нечетное составное натуральное число и пусть НОД (6, п) = 1.
а) Показать, что если р — простой делитель п и п' = п/р, то п — псевдопростое по основанию 6 только при 6" _1 =1 (mod р).
б) Доказать, что никакое целое число п = Зр (р > 3 есть простое число) не может быть псевдопростым по основаниям 2, 5 или 7.
в) Доказать, что никакое целое п = 5р (р > 5 есть простое число) не может быть псевдопростым по основаниям 2, 3 или 7.
г) Доказать, что 91 — наименьшее псевдопростое число по основанию 3.
3. Пусть р — простое число. Показать, что р2 — псевдопростое по основанию 6 тогда и только тогда, когда 6P_1 = 1 (mod р2).
4. а) Найти наименьшее псевдопростое по основанию 5. б) Найти наименьшее псевдопростое по основанию 2.
5. Пусть п = рд есть произведение двух различных простых чисел.
а) Пусть d = НОД (р — 1, q — 1). Доказать, что п — псевдопростое по основанию 6 в том и только том случае, когда = 1 (mod п). Выразить через d число различных оснований, по которым п — псевдопростое.
б) Сколько имеется оснований, по которым п — псевдопростое, если q = 2р + 1? Привести их полный список (в терминах р).
в) Пусть п = 341. Какова вероятность того, что случайно выбранное 6, взаимно простое с п, будет основанием, по которому п — псевдопростое число?
6. Показать, что если п — псевдопростое по основанию 6 Є (Z/nZ)*, то оно будет также псевдопростым по основаниям —6 и б-1.
7. а) Доказать, что если п — псевдопростое по основанию 2, то TV = 2" — 1 — также псевдопростое по тому же основанию.
б) Доказать, что если п — псевдопростое по основанию 6 и НОД (6— 1,п) = 1, то целое число TV = (6™ — 1)/(6 — 1) — псевдопростое по основанию 6.
в) Доказать, что существует бесконечно много псевдопростых чисел по основаниям 2, 3, 5.
г) Привести пример, показывающий, что без условия НОД (6 — 1, п) = 1 часть б) неверна.
8. Пусть 6 > 1 есть любое натуральное число, р — нечетное простое, не делящее 6—1, 6, 6+1. Положим п = (62р - 1)/(62 - 1).
а) Показать, что п — составное.
б) Показать, что 2р|(п — 1).
в) Показать, что п — псевдопростое по основанию 6; вывести отсюда, что для любого основания 6 существует бесконечно много псевдопростых по этому основанию.
9. а) Использовать тест (1), чтобы показать, что число 2047 = 211 - 1 — составное.
б) Объяснить, почему никогда не следует пытаться использовать тест (1) с 6 = 2 для проверки на простоту чисел Ферма 22 +1 или чисел Мерсенна 2Р — 1. Как обстоит дело с тестом (2) по основанию 6 = 2? Как обстоит дело с тестом (3) по основанию 6 = 2?
10. Пусть т — такое натуральное число, что 6m + 1, 12т + 1, 18т + 1 — простые числа. Положим п = (6m + 1)(12т + 1)(18т + 1). Доказать, что п — число Кармайкла.
§ 1. ПСЕВДОПРОСТЫЕ ЧИСЛА
153
Замечание. Неизвестно, существует ли бесконечно много чисел Кар-майкла вида (6m + 1)(12т + 1)(18т + 1). Эвристические соображения, однако, показывают, что это так.
11. Показать, что следующие натуральные числа — это числа Кармайкла: 1105 = 5 ¦ 13 • 17; 1729 = 7 - 13- 19; 2465 = 5-17-29; 2821 = 7-13-31; 6601 = 7-23-41; 29341 = 13 • 37 • 61; 172081 = 7 • 13 • 31 • 61; 278545 = 5-17-29-113.
12. а) Найти все числа Кармайкла вида Зрд (р, д — простые).
б) Найти все числа Кармайкла вида 5рд (р, д — простые).
в) Доказать, что для любого фиксированного простого г имеется лишь конечное множество чисел Кармайкла вида rpq (р, q — простые).
13. Доказать, что 561 -- наименьшее число Кармайкла.
14. Привести пример составного числа п и основания Ь таких, что б*-"-1-*/2 = ±1 (mod п), однако п не есть эйлерово псевдопростое число по основанию 6.
15. а) Доказать, что если п — эйлерово псевдопростое по основанию 6 G (Z/nZ)*, то оно также эйлерово псевдопростое по основаниям —6 и б-1.
б) Доказать, что если п — эйлерово псевдопростое по основаниям 6i и 62, то оно также эйлерово псевдопростое по основанию 6162.
16. Пусть п имеет вид р(2р — 1), как в упражнении 1 г).
а) Доказать, что п — эйлерово псевдопростое по 25% возможных оснований Ъ Є (7./riZ)*.
б) Найти класс чисел п такого типа, являющихся сильно псевдопростыми по 25% возможных оснований.
17. Пусть п имеет вид (6m + 1)(12т + 1)(18т + 1), как в упражнении 10.
а) Доказать, что если m нечетно, то га — эйлерово псевдопростое по 50% всех возможных оснований Ъ Є (Z/nZ)*.
б) Если m четно, то п — эйлерово псевдопростое по 25% возможных оснований 6 Є (Z/nZ)*.
