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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

70
числом. (Первые n, требующие 1, 2, 3, 4, 5, 6, 7 шагов будут 5, 13, 37, 73,
673, 1993, 15 013, соответственно).
18.15. Проект. Было доказано Р. Е. Дресслером в 1970 г., что если
N(x) = # {n > 0:
φ
(n) ≤ x},
тогда N(x)/x → A, когда х→ ∞, где А – некоторая константа. Оцените значе-
ние А. [Теоретическое значение А приблизительно равно 1,94].
19. Теорема Эйлера и понятие порядка
19.1. Теорема Эйлера (1760). Пусть n > 0, и предположим, что
(a, n) = 1. Тогда a
φ
(n)
≡ 1 (mod n).
19.2. Компьютерное упражнение. Так как a ⋅ a
φ
(n)–1
≡ 1 (mod n), то от-
сюда a
φ
(n)–1
является числом, обратным а по mod n (инверсией). Используя
этот вывод и программу для расчета
φ
, напишите программу решения ли-
нейного сравнения ax ≡ b (mod n), где (a, n) = 1. Как Вы могли бы изменить
это условие, чтобы решить такое сравнение без допущения, что (a, n) = 1?
19.3. Упражнения
1. Используя теорему Эйлера, покажите, что из сравнения
а
40
≡ 1 (mod 100) обеспечивается (а, 100) = 1. Докажите, что 7
400
– 3
400
де-
лится на 100. А делится ли оно на 1000? Заметьте, что, используя
100 = 2
2
⋅ 5
2
и теорему Эйлера отдельно для 4 и 25, Вы можете доказать, что
а
20
≡ 1 (mod 100) для (а, 100) = 1, так как сравнение содержит mod 4 и
mod 25.
2. Покажите, что, если (2, а) = (2, b) = 1 и (5, а) = (5, b) = 1, тогда
а
1000
– b
1000
делится на 10 000.
3. Покажите, что 10
6(р–1)
≡ 1 (mod 9p) для р – простого > 5. Докажите,
что существует бесконечно много целых чисел n, для которых р является
делителем числа 11 . . . 1 , содержащего n единиц в десятичной системе. Бу-
дет ли это справедливо для р = 3?
4. Пусть n = rs, где r > 2, s > 2 и (r, s) = 1. Вспомните из п. 18.5 (3), что
φ
(n) – чётная, так как n > 2. Используя теорему Эйлера, покажите, что
a
φ
(r)
φ
(s)/2
≡ 1 (mod n).
[Подсказка. Рассмотрите mod r и mod s]. В силу мультипликативности
функции
φ
(п. 18.3), это означает, что a
φ
(r)/2
≡ 1 (mod n).
5. Пусть
α
= r
π
/s, где (r, s) = 1. Представьте s = 2
a
b, где а ≥ 0, а b явля-
ется нечётным числом, и запишите
β
= 2
а
α
= r
π
/b. Используя теорему Эй-
лера, 2
k
≡ 1 (mod b) для k =
φ
(b), чтобы показать, что cos (2
k+1
β
) = cos (2
β
).
Докажите, что последовательность

Страницы