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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

45
стое число находится между 200 000 и 300 000). Вы также могли бы найти
наименьшее простое число р из всех, которое даёт р, р + 6, р + 12, р + 18 по-
следовательные простые числа.
11.2. Проект: наибольшее количество простых чисел
в арифметической прогрессии
Три простых числа, начиная с 3, а именно, 3, 5, 7 образуют арифметиче-
скую прогрессию. Найдите пять простых чисел 5, 5 + d, 5 + 2d, 5 + 3d, 5 + 4d и
найдите семь простых чисел 7, 7 + d, . . . , 7 + 6d (это требует различных зна-
чений d). (К сожалению, наименьшее d, для которого 11, 11 + + d, . . . , 11 + 10d
являются простыми числами, будет d = 1 536 160 080). Следуя данным намё-
кам, напишите доказательство
теоремы: если р, р + d, p + 2d, . . . , p + (p – 1)d –
все простые числа, тогда d делится на каждое простое число q при условии
2 ≤ q < p. (Например, для р = 7, d должно делиться на 2, 3 и 5 и, следовательно,
на 30).
От противного примем, что q является простым числом, q < p и q не
делит d. Докажите, что нет двух чисел из ряда p, p + d, . . . , p + (q – 1) p, ко-
торые сравнимы по модулю q. Так как среди них существует q, почему из
этого следует, что одно из них ≡ 0 (mod q)? Используйте q | (p + jd) для не-
которого j, 0 ≤ j ≤ q – 1, и факт, что
q и p + jd – оба простые, чтобы получить
противоречие.
11.3*. Упражнение: решение сравнения x
2
≡ 1 (mod m)
Пусть модуль m представим как
12
12
2 ...
r
aa a
a
r
mppp=
,
где p
i
– нечётные простые числа в порядке возрастания. Идея заключается в
том, чтобы доказать, что число решений сравнения x
2
≡ 1 (mod m) будет
er+
2
, где
0, 0 1,
1, 2,
2, 2.
если a или
e если a
если a
=
⎧
⎪
==
⎨
⎪
>
⎩
Основой является то, что x
2
≡ 1 (mod m), если и только если
2
1(mod 2 )
a
x ≡ и
1
1
(mod )
a
p
и . . . и
(mod )
r
a
r
p
, так как эти модули попарно
взаимно сопряженные. Более того, если однажды Вы нашли решение каж-
дого из этих r + 1 сравнений, единственное решение первоначального срав-
нения по (mod m) определяется из китайской теоремы об остатках. Доста-
точно трудно найти решения сравнений по mod 2
a
и другие сравнения,
имеющие решения ± 1.
В особенности, покажите, что для a > 2 решениями x
2
≡ 1 (mod 2
а
) бу-
дут ± 1 и ±(1 + 2
a –1
) и что эти четыре числа различны по (mod 2
a
).

Страницы