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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

80
q
2
– 2q(p + 2) + (p – 2)
2
≤ 0.
Убедитесь, что данное условие выполняется (
q > p), если и только ес-
ли
q ≤ p + 2 + 2
2.
p
Следовательно, если оно выполняется, тогда количест-
во шагов может быть < 2. С другой стороны, число шагов >
()
1
2
p
qpq+−
(так как
pq не является точным квадратом), а условием этого будет ≥ 1 (так
что число шагов будет > 1), что указывает на то, что предыдущая оценка
q
была точной: если
222qp p≥++
, то, по крайней мере, необходимы ещё два
шага. (Конечно, мы не имеем здесь равенство для
р > 2).
Например, при
р = 11 069 это даёт q ≤ 11 368, и наибольшее простое
число, для которого
≤ 11 368 будет 11 353. Действительно, следующее простое
число – это 11369, что подтверждает, что этот метод требует двух шагов.
Испытаем некоторые другие простые числа
р и докажем, что оценка
даёт наибольшее простое число, для которого метод Ферма завершается по-
сле одного шага. Заметим, что если
р и q являются нечётными, но не явля-
ются оба простыми числами, тогда метод Ферма может закончиться более
быстро, чем согласно выдвинутым аргументам. Для этого случая можно об-
наружить, что множитель располагается
между
p
q
и q. В качестве приме-
ра выберем
p = 3, q = 15; метод обнаруживает множитель 9 сначала (после
первого шага), несмотря на то, что для простого числа
q вышеназванный
аргумент доказывает необходимость двух шагов (для
q ≥ 11).
Сможете ли Вы определить наибольшее
q, для которого достаточны
два шага, согласно изложенному методу, принимая, что
p и q являются про-
стыми числами?
3. Зная
n и
φ
(n) (и то, что n = pq для разных простых чисел р и q), не-
сложно найти
р и q. Так как
φ
(n) = (p – 1)(q – 1), то получим p + q = n + 1 –
–
φ
(n). Отсюда р и q являются корнями квадратного уравнения х
2
– (n + 1 –
–
φ
(n))x + n = 0. Напишите программу определения р и q, исходя из n и
φ
(n).
Проверьте на малых числах, а потом с числом
n ≈ 10
16
. Найденные простые
числа
р и q перемножьте между собой, используя соответствующую про-
грамму.
4. Существует возможность того, что число
Р из открытого текста
может не быть взаимно простым с произведением
pq = n (вероятность этого
(
n –
φ
(n))/n, т. е., 1/p + 1/q – 1/pq, а это очень мало, когда р и q достаточно
велики). Покажите, что даже если
de ≡ 1 (mod
φ
(n)), то и тогда
Р
de
≡ P (mod
φ
(n)). Конечно, если (P, n) > 1, тогда НОД Р и n должен быть р
или
q, так как выбирается P < n. Таким образом, послание открытым тек-
стом, которое не взаимно простое с
n, является губительным для сохране-
ния множителей
p и q в секрете!
5. Предположим, что n
G
< n
R
. Покажите, что R может послать свою
подпись
G обращением порядка вышеупомянутых операций E
G
и D
R
. Объ-

Страницы