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

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

55
14.2. Компьютерные упражнения
1. Проверьте, что 341, 561 и 645 являются псевдопростыми числами
по основанию 2. (Не забудьте проверить, что они составные!).
2. Убедитесь, что 161 038 и 215 326 являются псевдопростыми числа-
ми по основанию 2. Заметьте, что они являются чётными. Действительно,
они являются наименьшими чётными псевдопростыми числами по основа-
нию 2.
3. Проверьте, что 1105 является псевдопростым числом по основани-
ям 2 и 3, а 1729 будет
псевдопростым числом по основаниям 2, 3 и 5, а
29 341 является псевдопростым числом по основаниям 2, 3, 5 и 7.
4. Определите первое число > 10
15
(или 10
10
, если вы работаете без
extended точности), которое либо простое, либо псевдопростое по основа-
нию 2. Получите ли Вы аналогичный ответ по основанию 3? (Если это так,
то вероятнее всего Вы нашли простое число). Если только взглянуть на
первое «вероятно простое число» > 10
15
на предмет определения является
ли первое число простым, либо псевдопростым, когда оно не явно является
составным числом, тогда, конечно, Вы пренебрежёте сомножителями 2, 3 и
5 для сокращения вычислений.
14.3. Упражнения
1. Покажите, что если (a, n) = 1 и n является псевдопростым числом
по основаниям а и ab, тогда n является, несомненно, псевдопростым числом
по основанию b.
2. Пусть р будет простым числом. Используйте теорему Ферма, чтобы
показать, что 2
р
– kp – 2 = 0 для любого целого числа k. Имея r = 2
p
– 2, по-
кажите, что 2
r
– 1 = (2
p
– 1)(2
r–p
+ 2
r–2p
+ . . . + 1) и докажите, что 2
р
– 1 будет
либо простым либо псевдопростым числом по основанию 2. (Числа 2
p
– 1
называются числами Мерсенна).
14.4. Проект: псевдопростые числа по основанию более, чем одному
Напишите программу для иллюстрации того, что числа, приведённые
ранее в п. 14.2, являются наименьшими псевдопростыми числами по отно-
шению к нескольким основаниям. (Не забывайте, что простые числа недо-
пустимы).
14.5. Проект: псевдопростые числа по основанию 2. Напишите
программу для нахождения всех псевдопростых чисел по основанию 2, ко-
торые меньше 2000. (Если не отбрасывать простые числа, то это будет
очень простой проект).
14.6. Упражнения
1. Возьмите а = 3 и наименьшее допустимое значение для р и, отсюда,
найдите псевдопростое число по основанию 3.

Страницы