|
◄ ДП Фурье в конечных полях
▲ Выше
Примеры КОРНЕЙ ►
ТЧП Гаусса ►
|
|
Числовое преобразование Ферма |
|
Fn=1+22n
n=0,1,2,3,4,.. |
Она глядит на вас так нежно, она лепечет так небрежно, она так тонко весела, её глаза так полны чувством, вечор она с таким искусством из-под накрытого стола свою мне ножку подала! Зачем я ею очарован? Зачем расстаться должен с ней? Когда б я не был избалован цыганской жизнию моей, когда б не смутное влеченье чего-то жаждущей души, я б здесь остался — наслажденье вкушать в неведомой тиши; забыл бы всех желаний трепет, мечтою б целый мир назвал... И всё бы слушал этот лепет, всё б эти ножки целовал.
Александр Пушкин
сентябрь 1833. |
Принимаясь за дело,
соберись с духом.
Козьма Прутков
"Мысли и афоризмы",56.
|
Книга книгой —
а мозгами двигай.
Владимир Маяковский
|
Переборной алгоритм вычисления
〈
1/T
〉Fn
=
〈
T—1
〉Fn .
Чтобы найти ВЫЧЕТ T—1 mod Fn по определению нужно решить уравнение
〈
T·T—1
〉Fn
= 1
относительно T—1.
В общем случае это делается подбором или полным перебором. Рассмотрим такой алгоритм
на примере нахождения обратных значений 1/T по модулю чисел Ферма. Очевидно, что
〈
k·Fn—1
〉Fn
= —1 , где k=1,...,Fn
и
〈
(k—1)·Fn+1
〉Fn
= +1 , где k=1,...,Fn .
Тогда имеем формулу (1)
〈
T—1
〉Fn
=
Fn — (k·Fn—1)/T ,
если
〈
k·Fn—1
〉T
= 0
или формулу (2)
〈
T—1
〉Fn
=
+ ((k—1)·Fn+1)/T ,
если
〈
(k—1)·Fn+1
〉T
= 0 .
Например, при
Fn
=
F2
=
17
по формуле (1) имеем
k = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 k·F2 — 1 = k·17 — 1 = 16 33 50 67 84 101 118 135 152 169 186 203 220 237 254 Тогда для T=8 при k=1,...,15
〈
k·17 — 1
〉8
= 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 ,
т.е. при k=1
〈
1·17 — 1
〉8
= 0 , тогда
〈
8—1
〉17
=
17 — (1·17—1)/8
=
17 — 2
=
+15
Для T=4 при k=1,...,15
〈
k·17 — 1
〉4
= 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 ,
т.е. при k=1
〈
1·17 — 1
〉4
= 0 , тогда
〈
4—1
〉17
=
17 — (1·17—1)/4
=
17 — 4
=
+13
А по формуле (2) имеем
k = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 (k—1)·F2 + 1 = (k—1)·17 + 1 = 1 18 35 52 69 86 103 120 137 154 171 188 205 222 239 256 Тогда для T=8 при k=1,...,16
〈
(k—1)·17 + 1
〉8
= 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 ,
т.е. при k=8
〈
(8—1)·17 + 1
〉8
= 0 , тогда
〈
8—1
〉17
=
+ ((8—1)·17+1)/8
=
120/8
=
+15
Для T=4 при k=1,...,16
〈
(k—1)·17 + 1
〉4
= 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 ,
т.е. при k=4
〈
(4—1)·17 + 1
〉4
= 0 , тогда
〈
4—1
〉17
=
+ ((4—1)·17+1)/4
=
52/4
=
+13
Резюмируя, можно сказать, что в этом примере по формуле (1) ответ
получается быстрее, чем по формуле (2).
|
Зри в корень
Козьма Прутков
"Мысли и афоризмы",5.
|
|
Формулы для вычисления КОРНЕЙ и их порядков.
Для составных Fn , также как и для простых, КОРЕНЬ из 1 root=2 имеет порядок
T
=
2n+1
=
2·2n
=
2b ,
а
〈
T—1
〉Fn
=
〈
(2n+1)—1
〉Fn
=
〈
2(2b—(n+1))
〉Fn
=
〈
2(2(n+1)—(n+1))
〉Fn .
Отсюда по аналогии (следует)
〈
2(
—
〈
t·k
〉T
)
〉Fn
=
〈
2(2(n+1)—
〈
t·k
〉T
)
〉Fn .
Далее, для простых и составных Fn КОРЕНЬ из 1 вида
root
=
22m
,
m=0,...,n
имеет порядок
T
=
2M
=
2(n+1—m)
=
2b·2—m
,
где
b=2n .
Рассмотрим КОРЕНЬ
root
=
〈
√2
〉Fn
=
2b/4(2b/2—1)
=
Учитывая, что
= 2b/4+b/2 — 2b/4 .
〈
22b
〉Fn
= 1
и, кроме того, поскольку
22b=2b·2b=—2b
и
2(2b—b/2)=—2+b/2 ,
проводим непосредственную проверку
〈
(√2)2
〉Fn
=
〈
(
2b/4(2b/2—1)
)2
〉Fn
=
Поэтому
root2=〈
(√2)2
〉Fn=2
.
Далее (по другой формуле),
= 〈 2b/2(2b+1—2·2b/2) 〉Fn = = 〈 2b/2(2b—2b—2·2b/2) 〉Fn = = 〈 2b/2(—2(b/2+1)) 〉Fn = = 〈 —2(b+1) 〉Fn = 〈 2 〉Fn .
〈
(√2)2
〉Fn
=
〈
(
2b/4(1+2—b/2)
)2
〉Fn
=
Обратная величина — КОРЕНЬ
1/root = root—1, где
= 〈 2b/2(1+2—b+2·2—b/2 〉Fn = = 〈 2b/2(1+22b·2—b+2(—b/2+1) 〉Fn = = 〈 2b/2(1+22b—b+2(—b/2+1) 〉Fn = = 〈 2b/2(—2b+2b+2(—b/2+1) 〉Fn = = 〈 2b/2·2(—b/2+1) 〉Fn = 〈 2 〉Fn .
root—1
=
〈
(√2)—1
〉Fn
=
〈
( 2b/4·(2b/2—1) )—1
〉Fn
=
КОРЕНЬ
root
=
〈
√2
〉Fn
для n > 1 имеет порядок
〈 1/( 2b/4·(2b/2—1) ) 〉Fn = = 〈 2—b/4·(2b/2+1) / (2b/2—1)·(2b/2+1) 〉Fn = = 〈 (2—b/4+2b/4) / (2b—1) 〉Fn = = 〈 (2—b/4+2b/4) / (2b—(—2b)) 〉Fn = = 〈 2b/4(2—b/2+1) / 2·2b 〉Fn = = 〈 —2b·2b/4(2(2b—b/2)+1) / 2·2b 〉Fn = = 〈 —( 2b/4(—2+b/2+1) / 2 ) 〉Fn = = 〈 —( (—2b/2+b/4+2b/4) / 2 ) 〉Fn = = 〈 (2b/2+b/4—2b/4) / 2 〉Fn = = 〈 2(b/2+b/4 —1)—2(b/4 —1) 〉Fn .
T
=
2n+2
=
2n·22
=
b·4 = 4b .
Рассмотрим, для примера, число Ферма
F2=17=24+1
и поле GF(17) ВЫЧЕТов mod 17. Первообразными (примитивными) КОРНЯми из 1 являются такие числа, степени которых образуют все элементы поля (т.е. их порядок максимален). У НЕпримитивного КОРНЯ root=4 порядок T=4 , у НЕпримитивного КОРНЯ root=2 порядок T=8 , у примитивных КОРНЕЙ root=3 и root=6 порядок T=16. Очевидно, что
〈
2
〉17
=
〈
62
〉17 ,
тогда имеем
〈
√2
〉17
=
〈
6
〉17
=
Учитывая, что
= 〈 8-2 〉17 = 〈 8 〉17 — 〈 2 〉17 = = 〈 23 〉17 — 〈 21 〉17 = = 〈 3—1 〉17 .
〈
6·6—1
〉17
=
1
=
〈
1+17
〉17
=
〈
6·3
〉17
имеем для обратных величин
〈
(
√2
)—1
〉17
=
〈
6—1
〉17
=
〈
3
〉17
=
Это значит, что существует ЧП Ферма длины T=16 с примитивным КОРНЕм
= 〈 4-1 〉17 = 〈 4 〉17 — 〈 1 〉17 = = 〈 22 〉17 — 〈 20 〉17 .
root=
〈
√2
〉17
=
〈
6
〉17 ,
который представим в виде степеней двойки как
〈
6
〉17
=
〈
8-2
〉17
=
〈
23
〉17
—
〈
21
〉17 ,
а также, что существует обратное ЧП Ферма длины T=16 с примитивным КОРНЕм
root
=
〈
(√2)—1
〉17
=
〈
6—1
〉17
=
〈 3 〉17,
который представим в виде степеней двойки как
〈
3
〉17
=
〈
4-1
〉17
=
〈
22
〉17
—
〈
20
〉17.
Поэтому умножения чисел на степени root можно вычислять,
используя только сдвиги. Например, для умножения на root=6 достаточно
двух сдвигов (на 3 бита и на 1 бит — это соответствует умножениям на 23
и на 21) и одного вычитания результатов этих сдвигов.
|
Нет пределов совершенству.
Поговорка
|
|
Вычисление ЧП Ферма без умножений.
Базовый элемент root в T-точечном ЧП Ферма (или в ЧП Ферма порядка T, или длины T) удовлетворяет условию
root
=
〈
gj
(Fn—1)/T)
〉Fn
=
〈
gj
(
22n
)
/T
〉Fn
,
где
gj — примитивный КОРЕНЬ из 1, а при
T=2b=2n+1
имеем
root
=
〈
gj
(
22n
)
/
(
2n+1
)
〉Fn
=
〈
gj
(
2(2n—(n+1))
)
〉Fn
.
При root=2 или root=22m ЧП Ферма называют преобразованием Рейдера или ТЧП Рейдера, которое можно вычислять без целочисленных умножений на степени основания (=2), т.е. на
root
〈
wt
〉T
=
2
〈
2m
·
wt
〉T
,
используя только сдвиги влево (т.е. умножения на степени двойки ,
сложения и вычитания.
|
Примеры КОРНЕЙ для простых модулей Fn
Примеры КОРНЕЙ для составных модулей Fn
Одномерное ЧП Ферма (ЧПФ)
Двумерное ЧП Ферма (2мЧПФ)
|
Три дела, однажды начавши, трудно кончить:
1) вкушать хорошую пищу;
2) беседовать с другом, возвратившимся из похода
и
3) чесать, где чешется.
Козьма Прутков
"Мысли и афоризмы",45.
|
|
◄ ДП Фурье в конечных полях ▲ В начало текущей ММ ЧПФ ► ТЧП Гаусса ► |
|
Последнее обновление 16.09.2013
© 2005 г., Александр Тимофеев, г.Харьков, Украина, eMail: atimopheyev@yahoo.com |