Составители:
Рубрика:
Теорема 9. Пусть n и ω – положительные степени числа
2, и m = ω
n/2
+ 1. В кольце R
m
вычетов по модулю m элемент
n имеет обратный (по модулю m ) и ω – примитивный корень
n-степени из 1.
Д о к а з а т е л ь с т в о. Поскольку n = 2
k
, а m – нечётно, то m
и n взаимно просты. Поэтому n имеет обратный элемент в R
m
.
15
Далее из (9.16) найдём
ω
n
= ω
n/2
ω
n/2
≡ (−1)(−1) = 1. (9.18)
Докажем, что
ω 6≡ 1 (mod m). (9.19)
Предполагая противное, получим
ω ≡ 1 (mod m) ⇐⇒ ω − 1 = d(ω
m/2
+ 1), (9.20)
где d – целое. Однако, по условию теоремы ω −1 6= 0 и поэтому d 6=
0; теперь видно, что в равенстве (9.20) слева стоит число заведомо
меньше, чем справа, так что (9.20) невозможно. Соотношение (9.19)
установлено.
Используя лемму 6 из (9.9), (9.18) и (9.19) видим, что ω – при-
митивный корень n-степени из 1 в R
m
.
Теорема доказана.
Для определения количества битовых операций в свёртке важно
следующее утверждение.
Лемма 7. Пусть m = ω
p
+ 1 и A =
P
l−1
i=0
a
i
ω
ip
, г де 0 ≤ a
i
< ω
p
для каждого i = 0, 1, . . . , l − 1. Тогда
A ≡
l−1
X
i=0
a
i
(−1)
i
(mod m). (9.21)
Д о к а з а т е л ь с т в о. Составим разность между левой и
правой частями соотношения (9.21); имеем
A −
l−1
X
i=0
a
i
(−1)
i
=
l−1
X
i=0
a
i
((ω
p
)
i
− (−1)
i
). (9.22)
15
Обосновать это утверждение, используя теоретико-числовые соображения.
31
Страницы
- « первая
- ‹ предыдущая
- …
- 28
- 29
- 30
- 31
- 32
- …
- следующая ›
- последняя »
