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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

69
3. Используйте задания (1) и (2), чтобы показать, что если n – нечёт-
ное, тогда С(2
r
n) = С(2
r-1
n) + 1 = . . . = C(2n) + r – 1 = C(n) + r – 1. Заметим,
что это означает, что C(2
r
n) = C(n) + C(2
r
).
4. Используйте задания (1) и (2), чтобы показать, что если n – чётное,
тогда С(2
r
n) = С(2
r1
n) + 1 = . . . = C(n) + r. Заметим, что это означает, что
C(2
r
n) = C(n) + C(2
r
) + 1.
5. У нас
φ
(3n) =3
φ
(n), или 2
φ
(n), соответственно 3 не делит n или
3 | n. Используйте это, чтобы показать, что, для k ≤ C(n),
φ
k
(3n) = 2
φ
k
(n) или
3
φ
k
(n). Докажите, что
φ
С(n)
(3n) =4 или 6, и что С(3n) = C(n) + 1 = C(n) + C(3).
Доказано, что С(pn) = C(n) + C(p) для некоторого нечётного простого
числа р. Возможно Вы хотите также попробовать это для р = 5. Из получен-
ных ранее результатов теперь следует, что С(mn) = C(n) + C(m), несмотря на
то, что
оба m и n являются чётными числами, в каждом случае мы добавля-
ем 1 в правую часть. (Удобно определить С(2) = 0, чтобы закрыть все слу-
чаи). Если у Вас имеются экспериментальные данные из вышеприведённого
п. 18.11, тогда Вы сможете сравнить их с Вашими результатами.
18.13. (Компьютерное?) упражнение. Определить все числа n ≤ 100
(или ≤ 1000, если Вы сможете), которые не охватываются теоремой Эйлера,
т. е., которые не равны
φ
(n) для некоторого n. Существует ли лучший метод,
чем составление таблицы значений
φ
(р
а
) для р
а
≤ 101 (или ≤ 1001) и получения
всех возможных произведений этих значений для различных простых чисел,
которые ≤ 100 (или ≤ 1000)? Сравните с п. 18.5 (1). Конечно, все нечётные
числа > 1 не являются эйлеровыми (сравните с п. 18.5 (3)). Чётными неэйлеро-
выми числами ≤ 200 будут 14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114,
118, 122, 124, 134, 132, 146, 152, 154, 158, 170, 174, 182, 186, 188, 194.
18.14. Проект. Если мы поменяем знаки минус на плюс в формуле
для
φ
(п. 18.4), мы получим новую функцию:
1
1
12
11 1
() (1 )(1 )...(1 ) ( 1),
i
k
ii
i
k
nn p p
pp p
α
φ
−
=
=⋅+ ⋅+ ⋅⋅+ = +
∏
где, как и ранее, p
i
– это различные простые числа – делители n. Действи-
тельно, для p
i
> 2, простым сомножителем p
i
+1 будет 2, а простые числа
должны быть меньше p
i
, чтобы показать, что итерация
φ
( т. е., n, ()n
φ
,
(())n
φφ
, . . .) даёт в конечном счёте число вида 2
а
3
b
, которое затем стано-
вится 2
а + 1
3
b
, 2
a + 2
3
b
и т. д. Напишите программу, которая вычисляет
φ
и
число шагов, необходимых, чтобы достичь вида 2
а
3
b
. Почему число шагов
совпадает для n, 2n и 3n (n ≥ 1)?
Проверьте следующую догадку: если n требуется больше шагов для
достижения вида 2
а
3
b
, тогда требуются все числа < n, а n будет простым

Страницы