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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

16
4. Предположим, что a = bq + r будет на первом шаге; тогда (b, r) = 1
и по индукции, если алгоритм дает
bs
1
+ rt
1
= 1, тогда b ≥ |2t
1
| и r ≥ |2s
1
|. До-
кажите, что
s = t
1
и t = s
1
– qt
1
. А теперь докажите, что для этого требуется
b ≥ |2s | и a ≥ |2t |.
4. [x] и применения
4.1. Определение. Для вещественных x величина [x] является наи-
большим числом
≤ x. Альтернативными формулировками, которые явно да-
ют тот же результат, будут:
4.2. Функция [x] является единственным целым числом, удовлетво-
ряющим
x – 1 < [x] ≤ x. [x] является единственным целым числом, для кото-
рого
x = [x] + y и 0 ≤ y < 1.
4.3. Упражнения
1. Покажите, что если n – целое число, тогда [x + n] = [x] + n.
2. Покажите, что если
n – целое число, тогда [x] ≥ n ⇔ x ≥ n.
3. Покажите, что если
x и y – вещественные числа, тогда
[
x] < [y] ⇔ cуществует n ∈ Z и x < n ≤ y.
(Для
⇒, n может быть выбран как [y]).
4. Покажите, что [
x + y]= [x]+ [y] +
ε
, где
ε
может быть 0 или 1.
5. Покажите, что для всех вещественных чисел
x и y [x] + [y] ≤ [x + y].
(Конечно, это распространяется до определённого числа сумм).
6. Пусть
x и y будут ≥ 0. Покажите, что [xy] ≥ [x][y]. Сохраняется ли
это условие, если
x или y < 0 ?
7. Покажите, что для любого действительного
x [x] + [x +
1
2
] = [2x].
Здесь, вероятно, наиболее просто выделить на два случая, а именно,
n ≤ x < n +
1
2
и n +
1
2
≤ x < n + 1 для целого n.
Покажите, что для любого вещественного
x и целого n > 0,
[] []
1
nx x
n
⎡⎤
=
⎢⎥
⎣⎦
.
8. Пусть x ∈ R и пусть P и Q будут целыми числами, а Q > 0. Покажи-
те, что не существует целого числа
k, для которого [x] + P < Qk ≤ x + P.
(Сравните с заданием 3 упражнения 4.3). Докажите, что
[]
x
PxP
QQ
⎡
⎤⎡ ⎤
++
=
⎢
⎥⎢ ⎥
⎣
⎦⎣ ⎦
.
Как особый случай, отметим, что если
a и b – целые числа, а b > 0, тогда

Страницы