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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

40
окончательное сравнение может быть объяснено. Решения первоначального
сравнения находятся среди более поздних, но некоторые решения оконча-
тельного сравнения отбрасываются, так как они не удовлетворяют началь-
ному.
Например, рассмотрим сравнение 17х ≡ 13 (mod 122), которое имеет
единственное решение по (mod 122), так как 17 и 122 взаимно простые чис-
ла. Последовательные упрощения дают 3х ≡ 31 (mod 22) и 2х ≡
≡ 102 (mod 122). Последнее сравнение эквивалентно x ≡ 51 (mod 56), кото-
рое имеет два решения по (mod 122): x ≡ 51 и x ≡ 107, но только
х ≡ 51 (mod 122) удовлетворяет начальному сравнению.
Решите сравнения вышеупомянутого п. 1 этим методом. Заметьте, что
возможно для сравнения, не имеющего решений, получить сравнение с ре-
шениями!
10.2. Компьютерные упражнения
1. Используйте программу для нахождения решений сравнений вида
ax ≡ c (mod m), где а и т – взаимно простые числа. Обобщите результат для
нахождения решений, когда (a, m) = h и h | c. Убедитесь, что программа ра-
ботает с повторным решением сравнений.
2. Напишите программу для решения сравнения ax ≡ c (mod m), где
(
а, т) = 1.
10.3. Упражнения. Здесь мы найдём решения сравнения
х
2
≡ 1 (mod pq), где p и q – различные простые числа.
1. Покажите, что х
2
≡ 1 (mod pq), если и только если х
2
≡ 1 (mod p) и
х
2
≡ 1 (mod q).
2. Рассмотрите случай х
2
≡ 1 (mod p), который имеет решения х ≡
≡ ± 1 (mod p). Возьмите х = ±1 + kp; покажите, что оно удовлетворяет х
2
≡
≡ 1 (mod q), если и только если (а) k ≡ 0 (mod q), давая х
≡ ±1 (mod pq) или
(б) kp ± 2 ≡ 0 (mod q).
3. Пусть теперь r удовлетворяет выражению pr ≡ 1 (mod q). Покажи-
те, что решениями х
2
≡ 1 (mod pq), полученными из (б) п. 2, будут x ≡ ±(1 –
– 2pq) (mod pq).
4. Найдите четыре решения для сравнения х
2
≡ 1 (mod pq), где р = 101
и q = 113.
5. Покажите, что если p и q – оба нечётные, тогда четыре решения ± 1,
±(1 – 2pr) различны по (mod pq), а в случае, если p или q равно 2, тогда
сравнение х
2
≡ 1 (mod pq) имеет точно два решения.
10.4. Упражнение. Существует интересное дополнение к упражне-
нию 10.3, когда p и q оба нечётные. Действительно, пусть х
1
будет решени-
ем сравнения х
2
≡ 1 (mod pq), где х
1
≡ ±1.

Страницы