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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

82
дывает», с какого решения G начал, и если он правильно угадает, тогда он
выигрывает. Так как не существует пути, по которому сообщается, с какого
решения
G начал, справедливо предсказание.
д) Теперь приступим в проверке победы или неудачи. Предположим,
что
G получает решение ± с от R, такое, что R проиграл. G доказывает это
следующим образом. Добавляя два решения, чтобы получить
b + с, G пред-
ставляет НОД (
b + c, n). Покажите, что может быть р или q (используя тот
факт, что
b и с различаются только в знаке х
1
или х
2
в формуле для х выше-
приведённого пункта (2)). Отсюда
G выбирает множитель n ! Не существует
разумного пути, но он может пойти на компромисс, обеспечивая
р и q дос-
таточно большими при отсутствии информации о полученных двух реше-
ниях. ( Теперь только остаётся возражать, если
G заранее не может пове-
рить
R, что он выиграл!).
21.4. Проект. Напишите программу, реализующую этот метод игры в
«орлянку» по телефону.
22. Применение уравнения Пелля
22.1. Упражнения
1. Докажите, что для любого иррационального
α
и любого действи-
тельного
β
найдется бесконечно много натуральных чисел
х
таких, что
xx /3<−
β
α
.
2. Докажите, что в неравенстве (1) можно заменить 3 на 2, если до-
пустить, что
х
принимает любые целые значения.
3. Докажите, что в неравенстве (2) константу 3 можно заменить на
½.
[Примените метод Морделла].
4. Докажите, что если
2
/1/
p
qq
α
−<
, то
1
1
nn
nn
rp p
p
qrq q
+
+
+
=
+
,
2
0
n
r
α
≤≤
,
,...,2,1,0,1
−
=
n
1
1
=
−
p
,
0
1
=
−
q
.
Для иррационального числа
α
обозначим через
)(
α
μ
+
такое число,
что при любом
)(
α
μ
+
<v
имеется лишь конечное число дробей
/pq
,
удовлетворяющих неравенству
2
0/ /
p
qvq
α
<−<
, а при любом
)(
α
μ
+
>v
неравенство
2
//0 qvqp <−<
α
имеет бесконечное число реше-
ний. Если же при любом числе
0>v неравенство
2
0/ /
p
qvq
α
<−<
имеет
бесконечное число решений, то положим по определению
0)( =
+
α
μ
.
Аналогично определим
)(
α
μ
−
, только вместо неравенства
0/
p
q
α
<−
используем неравенство
0/
p
q
α
<−
.
5. Докажите, что
α
α
μ
1212
inflim)(
+++
=
nn
qq
,

Страницы