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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

29
2. Пусть n – составное число. Покажите, что, если наименьший про-
стой сомножитель p у n больше, чем корень кубический из n, то n/p –
простое число.
3. Пусть p – простое число и пусть p = 30 q + r, 0 ≤ r < 30. Покажите,
что r равно либо 1, либо является простым числом. (Почему этого доста-
точно
, чтобы доказать, что, пока r ≠ 2, 3 и 5, то r не делится на 2, 3 или 5?).
Действительно, 30 является наибольшим числом, для которого это выпол-
няется; можете ли Вы найти другие меньшие числа, для которых это усло-
вие также выполняется?
6.3. Компьютерные упражнения. Видоизменим программу для вы-
числения количества простых чисел, ограниченных заданным максималь-
ным значением, таким образом, что переменная вычислений (целого типа),
указывающая на их число, увеличивалась бы каждый раз, как только новое
простое число будет найдено. Обозначим через
π
(x) число простых чисел,
меньших x. Используйте программу для проверки следующих результатов:
x
π
(x)
x
π
(x)
x
π
(x)
1000 168
4000 550 7000 900
2000 303
5000 669 8000 1007
3000 430
6000 783 9000 1117
Перед началом создания файла простых чисел и написания програм-
мы нахождения сомножителей путем простого деления, бегло исследуем
промежутки между последовательными простыми числами. (Заметим, что
эти промежутки могут быть произвольной длины). Задавая целое число
k ≥ 2, мы стремимся найти последовательные простые числа, значения ко-
торых различаются на величину, меньшую максимума, заданного индексом
k. В особом случае k = 2 эти пары простых чисел называются двойными
простыми числами. Примерами двойных простых чисел будут 3, 5; 5, 7; 11,
13; 17, 19. Уже давно стали догадываться, что существует бесконечное
множество двойных простых чисел, но это положение не было доказано.
Рибенбойм приводит некоторые огромные двойные простые числа, такие
как 1040-разрядные простые числа
256 200 945 × 2
3426
± 1.
Они в определённом смысле далеко превосходят встречавшиеся здесь
числа, но их можно исследовать, относясь к размеру этих двойных простых чи-
сел более сдержано, а план относительно их поиска предложен ниже в п. 6.7.
Очень просто изменить программу, чтобы распечатать последова-
тельные простые числа, различающиеся на величину k: Вам нужно только
проверить выполняется ли условие p(i) – p(i–1) = k для любого i в ряду. Эту
же работу крайне трудно сделать в предыдущей программе, так как простые

Страницы