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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

7
10.* Рассмотрите прямоугольный параллелепипед размером a × b × c,
разделенный на
abc единичных кубиков плоскостями, параллельными гра-
ням параллелепипеда, с диагональю, проходящей внутри параллелепипеда.
Используйте результаты задания 9
*
, чтобы показать, что эта диагональ про-
ходит точно через (
a, b, c) +1 углов единичных кубиков. Используйте зада-
ние 5, чтобы показать, что количество единичных кубиков, которые пере-
секает диагональ, находится по формуле
a + b + c – ((a, b) + ( b, c) + (с,
a)) + (a, b, c). [Эта формула может быть обобщена для n-мерных параллеле-
пипедов и представляет собой пример «принципа включения–исключения»,
который встречается при описании решета Лежандра].
11. Пусть
p
i
означает i-е простое число (p
1
= 2, p
2
= 3 и т. д.) и пусть
p
k
< n < p
k+1
2
( для некоторого k ≥ 1). Через m обозначим произведение пер-
вых
k простых чисел и пусть m = qn + r, где 0 ≤ r < n (так что r – это остаток
от деления
m на n). (Например, 7 < 101 < 11
2
(k = 4) и m = 210 = 2 × 101 + 8).
Принимаем, что
r ≠ 0. Покажите, что n будет простым числом, если и толь-
ко если (
n, r) =1. [Доказательство того, что, если (n, r) = 1, тогда n – простое
число, будет использовано более полно позднее. Достаточно показать, что
n
не делится на
p
1
, p
2
, . . ,p
k
, но если n – составное число, тогда найдется не-
которое простое число
≤
n
, которое должно быть делителем для n].
12. Проверьте, что целые числа от 2184 до 2200 включительно обла-
дают тем свойством, что каждое из них имеет общее кратное
>1, по крайней
мере, еще с одним из остальных чисел. Покажите, что это свойство теряет
силу, если список целых чисел продолжить за границы интервала. [Необы-
чайно длинный список для такого размера чисел!].
2.2. Упражнения
1. Несомненно, если
h = (a, b) и l = [a, b], тогда h | l. Наоборот, если
h | l , тогда существуют a и b (а именно, a = h и b = l), для которых h = (a, b)
и
l = [a, b]. Найдем все a и b, для которых (a, b) = 12 и [a, b] = 72. Какая бу-
дет основная процедура в этом случае? Будет ли решение единственным?
2. Пусть
r и s – целые числа. Покажите, что они могут быть представле-
ны как
r = ux, s = vy, где (u, v) = (x, y) = 1 и uv = НОК(r, s), xy = НОД(r, s), опре-
деляя
x и y следующим образом. Пусть r = p
1
r1
p
2
r2
. . . p
k
rk
, s = p
1
s1
p
2
s2
. . . p
k
sk
,
отсюда определим
x = p
1
х1
p
2
х2
. . . p
k
хk
, y = p
1
y1
p
2
y2
. . . p
k
yk
, где
⎩
⎨
⎧
≥
<
=
ii
iii
i
sr
srr
x
,0
,,
и
⎩
⎨
⎧
≤
>
=
ii
iii
i
sr
srs
y
,0
,,
.
Заметим, что когда
r
i
= s
i
, то можно перенести соответствующую сте-
пень
p
i
либо на x, либо на y, при этом сохраняя требуемые свойства. Найди-
те все возможные решения для
u, v, x и y, включая одно, предлагаемое для
r = 100 и s = 60 и для r = 700 и s = 300.

Страницы