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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

42
Теперь попытайтесь найти все решения для х.
Вы можете найти массу примеров сравнений, некоторые из них очень
трудны для решения, так как они требуют разложений десятичных чисел,
например: каково наименьшее число, состоящее только из 3, 5 и 7, такое,
что само число и сумма его цифр делятся на 3, 5 и 7?
{Ответ: 33577577777777775].
10.6. Компьютерные упражнения. Напишите программу решения
системы сравнений ax ≡ b (mod m) и сх ≡ d (mod n), принимая, что (a, m) и
(c, n) оба равны 1.
10.7. Компьютерные упражнения. Эти упражнения могут быть вы-
полнены вручную, но Вы можете использовать программу п. 10.6, полезную
для экспериментов с используемыми числами.
1. Найдите все числа х, 0 ≤ х ≤ 999, удовлетворяющие
х
2
≡ х (mod 1000). Сравните с вышеприведенным п. 10.5 (5). Обратите вни-
мание на числа, которые совпадают с последними тремя цифрами их квад-
ратов.
2. Требуется найти решение сравнения 3х
2
≡ х (mod 10000). Первая
проверка даёт (х, 3х – 1) = 1 и тогда можно свести к четырём случаям уп-
ражнения 10.5 (5):
х ≡ 0 (mod 2
4
и mod 5
4
); 3х ≡ 1(mod 2
4
и mod 5
4
); х ≡ 0 (mod 2
4
) и
3х ≡ 1(mod 5
4
); 3х ≡ 1(mod 2
4
) и х ≡ 0 (mod 5
4
).
3.* Решите сравнение х
3
≡ х (mod 1000) для 0 ≤ х ≤ 999. Это слегка бо-
лее оригинально, чем в пунктах (1) и (2), так как х
3
– х = х(х – 1)(х + 1), но
эти три сомножителя не являются попарно взаимно простыми, когда х не-
чётное число.
Существует интересный результат, касающийся сравнений ax ≡ y по
модулю простого числа р, известный как лемма Тью (1902). Мы будем
иметь возможность использовать её несколько позднее.
10.8. Лемма Тью. Пусть р будет простым числом и p не делит a. То-
гда существуют х и у, 0 < | x | <
p
и 0 < | y | <
p
, удовлетворяющие срав-
нению ах ≡ у (mod p).
10.9. Китайская теорема об остатках. Пусть m
1
, m
2
, . . . , m
r
– поло-
жительные числа, а каждая пара взаимно простая: (m
i
, m
j
) = 1, когда I ≠ j.
Тогда система сравнений
x ≡ a
1
(mod m
1
), x ≡ a
2
(mod m
2
), . . . , x ≡ a
к
(mod m
к
)
имеет единственное решение – модуль произведения m
1
m
2
. . . m
r
.
10.10. Упражнения
1. Решите сравнения х
≡ 4 (mod 7), х
≡ 6 (mod 9), х
≡ 1 (mod 10) с по-
мощью последовательной подстановки. [Ответ: х
≡ 501 (mod 630)]. Конечно,

Страницы