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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

41
Используя теорему, предположим, что целые числа x, y, n удовле-
творяют cравнению x
2
≡ y
2
(mod n), но при этом х не сравнимо с у; c –
– у (mod n). Тогда (x – y, n) является собственным сомножителем n (т. е.,
сомножителем, отличным от 1 или n). То же относится и к (x + y, n);
найдём, что (x
1
+ 1, pq) является собственным сомножителем pq и, отсюда,
равняется p или q. То же самое подходит для (x
1
– 1, pq). Проверьте это, ис-
пользуя вышеприведённую формулу в упражнении 10.3 (3) для нахождения
решений.
Очень просто решить систему линейных уравнений последовательной
подстановкой. Приведём пример.
Найдите все х, такие, что 6х ≡ 8 (mod 10) и 4х ≡ 7 (mod 9).
Теперь 6x ≡ 8 (mod 10), если и только если 3х ≡ 4 (mod 5). Так как
3 × 2 ≡ 1 (mod 5), то должны быть решения х
≡ 8 ≡ 3 (mod 5). Возьмём
х = 3 + 5k. Тогда 4х ≡ 7 (mod 9) даёт 2k ≡ 4 (mod 9), т. е., k ≡ 2 (mod 9). От-
сюда, k = 2 + 9 j и x = 3 + 5(2 + 9 j) = 13 + 45 j.
Из этого следует, что главным решением будет х ≡ 13 (mod 45).
10.5. Упражнения
1. Решите следующие системы сравнений:
3x ≡ 3 (mod 15) и 4x ≡ 2 (mod 21). [Ответ: x ≡ 11 (mod 105)].
10x ≡ 10 (mod 25) и 3x ≡ 8(mod 10) и 7х ≡ 12 (mod 15).
[Ответ: х ≡ 6 (mod 150)].
2. Какое наименьшее число, большее 1, дающее остаток 1, когда будет
разделено на все числа 2, 3, . . . ,10? [Найдите наименьшее общее кратное,
которое даёт остаток 1, когда будет разделено на все числа
ряда 2, 3,. . ., 50].
Какое наименьшее положительное число, дающее в остатке 1, когда делится
на 2, остаток 2 при делении на 3 и т. д., вплоть до деления на 10? [Почему
это эквивалентно x ≡ – 1 (mod HOK(2, 3, . . . , 10))?].
3. Найдите приблизительно, насколько велико наименьшее число,
большее 1, которое дает остаток 1 при делении на все числа 2, 3, . . . , 50?
[Ответ: приблизительно 3,1 ×10
21
].
4. Наименьшее общее кратное чисел 1, 2, . . . , 12 будет 27 720. Если число
х даёт в остатке i – 1 при делении на i для всех делителей i = 2, 3, . . . , 12, тогда
из этого следует, что x ≡ – 1 (mod 27 720). Каково наименьшее аналогичное
число для максимального делителя 13?
5. Предположим, что х является целым числом, 0 ≤ х ≤ 99, а последние
две цифры х
2
совпадут с цифрами х. Целью является нахождение возмож-
ных значений х. Заметим, что это эквивалентно решению уравнения х
2
≡
≡ х (mod 100), что равноценно х
2
≡ x (mod 4) и х
2
≡ x (mod 25). Покажите, что
существуют всего четыре случая:
х ≡ 0 (mod 4 и mod 25); х ≡1 (mod 4 и mod 25); х ≡ 0 (mod 4) и
х
≡ 1 (mod 25); х
≡1(mod 4) и х ≡ 0 (mod 25).

Страницы