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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

73
19.9. Упражнения. Пусть р и q – различные простые числа и предпо-
ложим, что
r является простым делителем для обоих случаев
a = (p
q
– 1)/(p – 1) = p
q–1
+ p
q–2
+ . . . + 1 и
b = (q
p
– 1)/(q – 1) = q
p–1
+ q
p–2
+ . . . + 1.
1. Покажите, что если
r | (p – 1), тогда a ≡ q (mod r) и докажите, что
r = q. Так как q не делит b, это показывает, что r не делит (p – 1) и, анало-
гично,
r не делит (q – 1).
2. Покажите, что, если
р = 2, тогда 2q – 1 ≡ q + 1 ≡ 0 (mod r). Докажи-
те, что ord
r
2 = q и, следовательно, q | (r – 1). Аналогично p | (q + 1). Дока-
жите, что
р > 2 и, аналогично, q > 2.
3. Покажите, что
а и b являются нечётными и докажите, что r – нечётное.
4. Используйте
p
q
≡ 1 (mod r) и п. (1), чтобы показать, что ord
r
p = q , и
докажите, что
q | (r – 1). Аналогично для p | (r – 1). Докажите, что r имеет
вид 2
kpq + 1.
5. Возьмите
р = 17 и напишите программу для нахождения наимень-
шего простого числа
q, для которого r = 2pq + 1 является общим кратным a
и
b, как проделано выше.
19.10. Упражнение: наименьшее общее кратное порядка.
Если вы-
брать два элемента
a и b порядков, соответственно, r и s (mod n), то сущест-
вует простая конструкция для нахождения другого элемента
с порядка
НОК(
r, s) таким образом. Покажите, что существуют числа u, v, x, y, такие,
что
r = ux, s = vy и (среди прочего) (u, v) = 1 и uv = HOK (r, s). Используйте
выражение
с ≡ a
x
b
y
(mod n). Требованием является наличие порядка uv.
Сначала покажите, что с
uv
≡ 1 (mod n), так что порядок является делителем
uv. Затем выберите с
k
≡ a
kx
b
ky
≡ 1 (mod n). Увеличьте степень каждой из час-
тей до
u и докажите, что s | kuy и, следовательно, v | k; аналогично покажите,
что
u | k. Докажите, что uv является делителем порядка.
19.11. Упражнение: формула Серпинского – Селфриджа, дающая
только составные
числа. В 1960 г. Серпинский показал, что существует
бесконечно много
k, для которых N = k ⋅ 2
n
+ 1 является составным числом
для всех
n ≥ 1. В 1963 г. Селфридж показал, что k = 78 557 обладает таким
свойством, и Вам даётся шанс, чтобы доказать это. Действительно, Вы мо-
жете показать, что
N всегда делится на 3, 5, 7, 13, 19, 37 или 73. Например,
рассмотрим 7: когда выполняется
N ≡ 0 (mod 7)? Так как 78 557 ≡ 3 (mod 7),
то получим решение 2
n–1
≡ 1 (mod 7). Краткое вычисление показывает, что
ord
7
2 = 3, так что, опираясь на п. 19.5, это эквивалентно 3 | (n – 1), т. е., n ≡
≡ 1 (mod 3). Аналогично рассмотрите 13: когда верно N ≡ 0 (mod 13)? Так
как 78557
≡ –2 (mod 13), то это решение относится к 2
n + 1
≡ 1 (mod 13). Мы
нашли, что ord
13
2 = 12, так что, используя п. 19.5, мы получим 12 | (n + 1),

Страницы