ВУЗ:
Составители:
Рубрика:
94
ляется простым числом, отсюда b = ±a
k+1
, и существуют два решения:
x = ±a
k+1
и сравнение x
2
≡ a (mod p).
8. Пусть
n=pq, где р и q – разные простые числа, оба сравнимые
с 3 (mod 4), и пусть
а ≡ b
2
(mod n), как ранее. Используя тот факт, что
x
2
≡ a (mod n) ⇔ x
2
≡ a (mod p) ⇔ x
2
≡ a (mod q),
докажите, что существует точно
четыре решения x
2
≡ a (mod n).
Чтобы найти их точно, выберем
r и s такими, что rp + sq = 1 (напом-
ним, что
р и q – разные простые числа, так что (p, q) = 1), и пусть
x
1
≡ a (mod p), x
2
≡ a (mod q). (Метод вышеприведённого пункта (1) может
быть использован для нахождения
х
1
и х
2
). Покажите, что х = x
1
sq + x
2
rp
удовлетворяет x
2
≡ a (mod p и mod q) и, отсюда (mod n). Используя два вы-
бора для
х
1
и два выбора для х
2
, получим четыре решения (почему они обя-
зательно различны по модулю
n?).
