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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

67
[Получается, что наименьшее число у, для которого
φ
(n) = у, имеет чётное
решение для n, но отсутствует нечётное решение у = 2
9
× 257
2
= 33 817 088].
18.6. Компьютерное упражнение. Напишите программу, основанную,
возможно, на программе пробного деления, чтобы вычислять
φ
(n) для данного
n. Существует несколько путей для выполнения этого, один из которых осно-
вывается на формуле п. 18.4. Т. е.
φ
начинается с 1, а пробное деление проте-
кает, как описано перед этим. Для каждого простого числа р, являющегося де-
лителем n, когда наивысшая степень х = р
а
делителя n найдена, значение
φ
умножается на х(р – 1)/р. Вы только планируете выполнить этот последний
шаг, когда действительно р является одним из простых чисел, которое может
быть найдено только делением n. (Альтернативно инициализируем
φ
по n и
умножаем на (р – 1)/р, если каждое простое р является делителем n). Проверь-
те, что Ваша программа работает с проверкой малых значений n; также про-
верьте, что
φ
(5186) =
φ
(5187) =
φ
(5188) = 2592 (довольно редкий пример!).
Другая редкость – это
φ
(25 930 + 5k) = 2
7
· 3
4
, для k = 0, 1, 2. Действительно
существует другое число, не на много большее, чем 25 940, которое имеет то
же самое значение для
φ
; можете Вы найти его?
18.7. Проект. Используйте программу для вычисления
φ
, чтобы найти
при различных значениях n среднее значение
φ
(k)/k для k = 1, 2, . . . , n. (Это
сумма значений, разделённых на n). Существует теоретическая оценка для
этого среднего значения вида 6/π
2
+ М (ln n/n), где М является константой.
Оцените величину М.
18.8. Упражнение: n
φ
(n) определяет n. Как следует из п. 18.5, суще-
ствует много n, для которых
φ
(n) имеет заданное значение. Странно, однако,
что если n
φ
(n) = m
φ
(m), тогда неизбежно n = m. Представим основание для
доказательства этого. Сначала докажите из формулы для
φ
(n), что, если р
является наибольшим простым числом, делящим n
φ
(n), тогда р также явля-
ется наибольшим простым числом, делящим n. Предположим, что n
φ
(n) =
= m
φ
(m), докажите, что р является также наибольшим простым числом, де-
лящим m, и, кроме того, степень р, на которое делится каждая часть уравне-
ния – нечётная, скажем, p
2r–1
, где p
r
является степенью р, на которую делят-
ся оба m и n. Таким образом, n = p
r
N и m = p
r
M, где p не делит N и р не де-
лит M. Теперь используем данное уравнение, чтобы доказать, что N
φ
(N) =
= M
φ
(M). Это сокращает число различных простых сомножителей до одного
и, в конце концов, сводит задачу к доказательству того, что если n = p
a
и
m = q
b
для простых чисел р и q, тогда n
φ
(n) = m
φ
(m) означает, что p = q, a
a = b, т. е., n = m. (Почему невозможно выставить все простые сомножите-
ли в одной части уравнения перед тем, как Вы выставите их на другой сто-
роне?).

Страницы