NTT-Fermat_ExampRoot.HTM
◄ ЧП Ферма     ▲ Выше     ТЧП Гаусса ►

Примеры КОРНЕЙ по модулю чисел Ферма




Примеры КОРНЕЙ для простых модулей Fn.
Примеры КОРНЕЙ для составных модулей Fn.


  
Отыщи всему начало,
и ты многое поймёшь.
                     Козьма Прутков
            "Мысли и афоризмы-2",92.

Примеры КОРНЕЙ для простых модулей Fn.

Для простых чисел Ферма   Fn = F1, F2, F3, F4   любой примитивный КОРЕНЬ из 1 имеет порядок

Tmax = Fn-1 = 2b , где b=2n .

Например, root=3. Для простых чисел F3 и F4 прочие примитивные КОРНИ имеют вид нечётной степени 3.

Для КОРНЯ root=√2 порядка 4b (при n > 1)

root=√2 = 〈 √2 〉Fn = 2b−b/4 − 2b/4 .
Тогда
2b−b/4 − 2b/4 = 2b/4+b/2 − 2b/4 = 2b/42b/2 − 2b/4 =
= +2b/4(2+b/2−1) = +22n−2(2+2n−1−1) =   
= −2b/4(1−2+b/2) = −22n−2(1−2+2n−1)      
или иначе
−2b/4(1+2−b/2) = −22n−2(1+2−2n−1) .
Для обратного КОРНЯ root−1 порядка 4b (при n > 1)
root−1 = 〈 (√2)−1 〉Fn = 2b/2+b/4 −1 − 2b/4 −1 .
Тогда
2(b−b/4 −1) − 2(b/4 −1) = 2(b/4 −1+b/2) − 2(b/4 −1) = 2(b/4 −1)2b/2 - 2(b/4 −1) =
= +2(b/4 −1)(2+b/2−1) = +2(2n−2−1)(2+2n−1−1) =   
= −2(b/4 −1)(1−2+b/2) = −2(2n−2−1)(1−2+2n−1)      
или иначе
−2(b/4 −1)(1+2−b/2) = −2(2n−2−1)(1+2−2n−1) .
Для не примитивных КОРНЕЙ из 1 вида
root = 22m, m=0,...,n
порядок по модулю числа Ферма Fn определяется так
T=2n+1−m , m=0,...,n .

Например,

F2 = 222+1 = 24+1 =17, b=4, Tmax=2b=24=16 для root=3
Для примитивных корней по mod F2
n=2

root=
 3     =
Tmax=
 T=
 16
g=
3


root=
 √2     =
 23-21
4b=
 T=
 16
g=
23-21=8-2=6


root=
 (√2)-1 =
 22-20
4b=
 T=
 16
g=
22-20=4-1=3
Для не примитивных корней вида 22m         T=22+1−m
n=2
m=0
root=
 2 =
21
2b=
 T=
8

g=
2


m=1
root=
 4 =
22

T=
4

g=
4


m=2
root=
 16 =
24

T=
2

g=
16


F3 = 223+1 = 28+1 =257, b=8, Tmax=2b=28=256 для root=3
Для примитивных корней по mod F3
n=3

root=
 3     =
Tmax=
 T=
 256
g=
3
Для не примитивных корней порядка    4b
n=3

root=
 √2     =
 26-22
4b=
 T=
 32
g=
26-22=64-4=60
n=3

root=
 (√2)-1 =
 25-21
4b=
 T=
 32
g=
25-21=32-2=30
Для не примитивных корней вида 22m         T=23+1−m
n=3
m=0
root=
 2 =
21
2b=
 T=
16

g=
2


m=1
root=
 4 =
22

T=
8

g=
4


m=2
root=
 16 =
24

T=
4

g=
16


m=3
root=
 256 =
28

T=
2

g=
256


F4 = 224+1 = 216+1 =65537, b=16, Tmax=2b=216=65536 для root=3
Для примитивных корней по mod F4
n=4

root=
 3     =
Tmax=
 T=
 65536
g=
3
Для не примитивных корней порядка    4b
n=4



root=

 √2     =

 212-24

4b=

 T=

 64

g=

212-24=
4096-16=4080




root=

 (√2)-1 =

 211-23

4b=

 T=

 64

g=

211-23=
2048-8=2040
Для не примитивных корней вида 22m         T=24+1−m
n=4
m=0
root=
 2 =
21
2b=
 T=
32

g=
2


m=1
root=
 4 =
22

T=
16

g=
4


m=2
root=
 16 =
24

T=
8

g=
16


m=3
root=
 256 =
28

T=
4

g=
256


m=4
root=
 65536 =
216

T=
2

g=
65536



  
Где начало того конца, которым
оканчивается начало?
                     Козьма Прутков
              "Мысли и афоризмы",78.

Примеры КОРНЕЙ для составных модулей Fn.

Для составных чисел Ферма   Fn = F5, F6, F7, ...   примитивных КОРНЕЙ из 1 нет. Однако любой сомножитель в разложении Fn (n > 4) имеет вид (К·2n+2+1). Поэтому

2n+2=4b=Tmax
является максимальным порядком не примитивного КОРНЯ вида
root = √2 = 2b−b/4 − 2b/4 .
Тоже и для обратного значения не примитивного КОРНЯ root−1 с максимальным порядком 4b
root−1 = (√2)−1 = 2b−b/4 −1 − 2b/4 −1 .
Поскольку порядок T не примитивных КОРНЕЙ должен делить Tmax, то ЧП Ферма длины T для составного Fn существуют при условии, что T делит 2n+2=4b, т.е.
T | 2n+2.
Для КОРНЕЙ из 1 вида
root=22m, m=0,...,n
порядок по модулю числа Ферма Fn определяется также, как и для простых чисел Ферма, по формуле
T=2n+1−m, m=0,...,n .

Например,

F5=232+1, b=32, Tmax=4b=128 при g=√2=224-28= 16777216-256 = 16776960
Для не примитивных корней порядка   4b=Tmax
n=5





root=


 √2     =


 224-28


4b=


T=


128





g=


224-28 =
16777216-256=
16776960






root=


 (√2)-1 =


 223-27


4b=


T=


128





g=


223-27 =
8388608-128 =
8388480
Для не примитивных корней вида 22m         T=25+1−m
n=5
m=0
root=
 2 =
21
2b=
T=
64

g=
2


m=1
root=
 4 =
22

T=
32

g=
4


m=2
root=
 16 =
24

T=
16

g=
16


m=3
root=
 256 =
28

T=
8

g=
256


m=4
root=
 65536 =
216

T=
4

g=
65536


m=5
root=
 =
232

T=
2

g=
232


F6=264+1, b=64, Tmax=4b=256 при g=√2= 248-216
Для не примитивных корней порядка   4b=Tmax
n=6

root=
 √2     =
 248-216
4b=
T=
256

g=
248-216
n=6

root=
 √2     =
 248-216
4b=
T=
256

g=
247-215
Для не примитивных корней вида 22m         T=26+1−m
n=6
m=0
root=
 2 =
21
2b=
T=
128

g=
2


m=1
root=
 4 =
22

T=
64

g=
4


m=2
root=
 16 =
24

T=
32

g=
16


m=3
root=
 256 =
28

T=
16

g=
256


m=4
root=
 65536 =
216

T=
8

g=
65536


m=5
root=
 =
232

T=
4

g=
232


m=6
root=
 =
264

T=
2

g=
264


F7=2128+1, b=128, Tmax=4b=512 при g=√2= 296-232
Для не примитивных корней порядка   4b=Tmax
n=7

root=
 √2     =
 296-232
4b=
T=
512

g=
296-232


root=
 (√2)-1 =
 295-231

T=
512

g=
295-231
Для не примитивных корней вида 22m         T=27+1−m
n=7
m=0
root=
 2 =
21
2b=
T=
 256

g=
2


m=1
root=
 4 =
22

T=
 128

g=
4


m=2
root=
 16 =
24

T=
 64

g=
16


m=3
root=
 256 =
28

T=
 32

g=
256


m=4
root=
 65536 =
216

T=
 16

g=
65536


m=5
root=
 =
232

T=
 8

g=
232  


m=6
root=
 =
264

T=
 4

g=
264  


m=7
root=
 =
2128

T=
 2

g=
2128

NB. Для практических применений подходят только составные числа Ферма F5, F6, и F7, для которых при длинах векторов 64, 128 и 256 имеются быстрые алгоритмы ЧП Ферма (Рейдера) без умножений и обеспечивается приемлемый динамический диапазон сигналов.


  

Три дела, однажды начавши, трудно кончить:
1) вкушать хорошую пищу;
2) беседовать с другом, возвратившимся из похода
 и
3) чесать, где чешется.
                                  Козьма Прутков
                           "Мысли и афоризмы",45.
◄ ЧП Ферма     ▲ В начало текущей     ТЧП Гаусса ►






Последнее обновление 16.09.2013

© 2005 г., Александр Тимофеев, г.Харьков, Украина, eMail: atimopheyev@yahoo.com