Элементы теории чисел и криптозащита. Воронков Б.Н - 57 стр.

UptoLike

Рубрика: 

57
14.8. Теорема. Пусть n = q
1
q
2
. . . q
k
, где q
i
различные простые числа
и k 2. Предположим, что для каждого i, (q
i
– 1) | (n – 1). Тогда n будет чис-
лом Кармайкла. (Заметим, что простые числа должны быть нечётными, так
как, если q
1
= 2, тогда nчётное, а q
2
, будучи нечётным, не удовлетворяет
условию (q
2
– 1) | (n – 1)).
14.9. Упражнения
1. Предположим, что р, 2р – 1 и 3р – 2 являются простыми числами,
где р > 3. Покажите, что их произведение является числом Кармайкла.
Вам необходимо показать, что р 1 (mod 6); вспомните, что некоторые
простые числа находятся по формуле р ±1 (mod 6). В свете этого три
простых числа могут быть представлены в более привлекательном виде
6m + 1, 12m
+ 1, 18m + 1 и m = 1, что даёт первый результат 7 13 19.
Найдите следующее значение m, которое даёт три простых числа 6m + 1,
12m + 1, 18m + 1.
2. Предположим, что k = 2 в п. 14.8 и пусть q
2
> q
1
. Покажите, что n
– 1 (q
1
– 1) (mod (q
2
– 1)) и найдите в этом противоречие. Следовательно,
минимальное возможное значение для k в п. 14.8 будет 3 (как показано в
примере перед п. 14.8).
3. Пусть n будет таким, как в п. 14.9 (1) (отсюда и число Кармайкла).
Покажите, что b
n
b (mod n) по некоторому основанию b, являющемуся
взаимно простым к n или нет. [Подсказка. Предположите, что (n, b) > 1. По-
чему (n, b) должно быть произведением простых чисел, взятых среди q
i
, ко-
торые появляются в (n, b) и b
n–1
1 (mod q
i
) для каждого q
i
, отсутствующего
в (n, b)?].
Можно надеяться, что такие результаты, как в вышеприведённом
пункте (1), помогут нам доказать, что существует бесконечно много чисел
Кармайкла, но фактически обычно очень трудно определить насколько
много простых чисел в двух и более выбранных последовательностях. На-
пример, не всегда известно насколько много существует «парных простых
чисел» р,
р + 2. Вопрос о количестве чисел Кармайкла основательно был
поставлен в 1992 г.; см. [7].
14.10. Компьютерные упражнения
1. Представьте в виде сомножителей 29 341, 172 081, 564 651 361 и,
отсюда, проверьте, что все они являются числами Кармайкла.
2. Найдите число Кармайкла 7 13 31 q, где qпростое число, и три
числа Кармайкла 13 37 q, где qпростое число. (Конечно, Вы можете ис-
пользовать критерий 14.8. Вероятно Вы пожелаете воспользоваться файлом
простых чисел, созданным
ранее).
3. Убедитесь, что m = 35 и m = 1515 дают числа Кармайкла в виде,
описанном в п. 14.9 (1). (Несколько более трудным упражнением будет