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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

74
т. е., n ≡ –1 (mod 12). Аналогичным образом покажите, что 3 | N ⇔ n ≡
≡ 0 (mod 2); 5 | N ⇔ n ≡ 1 (mod 4); 19 | N ⇔ n ≡ –3 (mod 18); 37 | N ⇔ n ≡
≡ –9 (mod 36) и 73 | N ⇔ n ≡ 3 (mod 9). Теперь проверьте, что каждое n по-
крывается, по крайней мере, одним из семи сравнений (проверьте в случае
mod 36).
19.12. Проект: замкнутые многоугольники.
Мы начнём с теорети-
ческих вычислений. Пусть
р будет нечётным простым числом, k ≥ 2, и пусть
n, m будут порядками 2 mod p
k
и mod p
k–1
, соответственно (сравните п. 19.6
(5)). Мы
предполагаем, что n ≠ m.
1. Утверждаем, что для любого
t ≥ 0, 2
t
+ p
k–1
является mod р
k
степе-
ни 2. Это показывает, что действительно добавка
p
k–1
меняет порядок сте-
пеней 2 mod
p
k
[Почему?]. Докажем это высказывание, используя следую-
щие подсказки. Возьмём 2
m
= 1 + hp
k–1
и увеличим степени каждой части
до, скажем,
s c помощью биномиальной теоремы. Используйте n ≠ m, чтобы
показать, что
p не делит h, и докажите, что для подходящего s 2
ms
≡ 1 + p
k–1
(mod
p
k
). Это подтверждает требование для t = 0. Теперь увеличим каждую
сторону последнего сравнения до степени
r. Покажите, что существует та-
кое
r, что 2
msr+t
≡ 2
t
+ p
k–1
(mod p
k
). Это доказывает главное утверждение.
2. Пусть
α
будет углом 2
π
r/p
k
(те же р и k, что и ранее, но с новым r), где
p не делит r. Пусть v
0
будет некоторый ненулевой вектор и пусть v
s
будет v
0
,
повёрнутым против часовой стрелки на угол
s
α
для некоторого целого s. Мы
рассматриваем векторы
w
0
, w
1
, w
2
, . . . , где w
0
= v
0
, w
1
= (w
0
, повёрнутому на
α
) = v
1
, w
2
= (w
1
, повёрнутому на 2
α
) = v
3
, w
3
= (w
2
, повёрнутому на 4
α
) = v
7
и
т. д. В общем случае,
w
i
= v
j
, где j = 2
i
– 1. Векторы w
0
, w
1
, w
2
, . . . могут быть
расположены, последовательно соединёнными своими концами, образуя мно-
гоугольную линию (см. рисунок 3): (внешний) угол между двумя рёбрами уд-
ваивает предыдущий угол между двумя рёбрами.
Покажите, что если
n – порядок 2 mod p
k
, то w
n
= w
0
(как векторы, т. е.
они параллельны). Целью является доказать, что в нотации пункта (1) при
m ≠ n, многоугольник замыкается после n изображённых сторон, т. е.,
W =
w
0
+ w
1
+ . . . + w
n-1
= 0. Примем обозначение
ρ
k
для вращения векторов
на угол
k
α
и покажем, используя (1), что
ρ
с+1
W =
ρ
W, где с = р
k–1
. Докажи-
те, что W = 0, как требуется.

Страницы