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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

89
Существует ли элемент точно порядка 40? Используя п. 22.12 (3), мы полу-
чим, что ord
32
3 = 8. Так как 25 имеет примитивный корень g (например,
g = 2), то существует g, имеющее ord
25
g =
φ
(25). Таким образом, мы ищем
решение системы
x ≡ 3 (mod 32), x ≡ g (mod 25)
с помощью китайской теоремы об остатках. (Для g = 2 это даёт x = 227). Ес-
ли
x
k
≡ 1(mod 32 и mod 25), так что, для вышеприведённых порядков, 8 | k и
20 |
k; отсюда, 40 | k и, действительно, х имеет порядок точно 40. вернее, чем
сомножитель 40. Для
λ
(800) = 40 мы получим а
λ
(800)
≡ 1 (mod 800) для всех а,
для которых (
а, 800) = 1, и существует элемент х порядка точно
λ
(800). Это
λ
и называется
минимальным универсальным показателем для 800.
Общий случай аналогичен. Таким образом, для каждого
n ≥ 1 мы
ищем число
λ
такое, что для всех а, удовлетворяющих (а, n) =1, будем
иметь
а
λ
(n)
≡ 1 (mod n), и, далее,
λ
(n) минимально в том смысле, что сущест-
вует число, чей порядок по mod n является точно
λ
(n). Существование тако-
го числа первоначально было доказано Кармайклом в 1909 г.; определение
λ
– функции введено Е. Лукасом.
23.15. Упражнение: минимальный универсальный показатель
λ
(n)
1. Используя результаты вышеприведённого п. 22.12, покажите, что
λ
(2
k
) = 2
k–2
для k ≥ 3. Отдельно покажите, что
λ
(4) = 2 и
λ
(2) = 1. Конечно,
λ
(1) = 1 тоже.
2. Пусть
n = 2
n1
p
2
n2
. . . p
r
nr
представляет собой разложение на простые
сомножители в степенях числа
n, где n
1
≥ 0, а остальные n
i
> 0. Определим
λ
(n) являющимся наименьшим общим кратным r чисел
λ
(2
n1
) (как в (1)) и
φ
(p
i
ni
) для i = 2, . . . , r. (Отметим, что если n > 2, тогда
λ
(n) будет чётным).
Покажите, что для всех
а, для которых (a, n) = 1, будем иметь место сравне-
ние
а
λ
(n)
≡ 1 (mod n).
3. Возьмём
λ
(n) такое, как в (2), и пусть g
i
будет примитивным корнем
по mod
p
i
ni
для i = 2, . . . , r. Пусть х будет решением системы уравнений
x ≡ 3 (mod 2
n1
), x ≡ g
i
(mod p
i
ni
) для i = 2, . . . , r.
Покажите, что порядок
x mod n точно равен
λ
(n).
23.16. Проект. Напишите программу для определения
λ
(n), исходя
из
n. Определите также элемент х, чей порядок по mod n равен
λ
(n).
23.17. Упражнение: снова о числах Кармайкла
Пусть
n > 2 и пусть х имеет порядок точно
λ
(n). Предположим, что
х
n–1
≡ 1 (mod n). Докажите, что
λ
(n) | (n – 1). Покажите, что это означает, что n
является нечётным (вспомните, что
λ
(n) чётное для n > 2). Предположим, для
противопоставления, что
р является простым числом (> 2) и что p
k
– наивысшая

Страницы