NTT-Fermat_MM-1D.HTM

◄ ЧП Ферма ▲ Выше ММ 2мЧПФ ► ТЧП Гаусса ►

Одномерное ЧП Ферма

SN = RN xN mod Fn

xN = N−1 RN−1 SN mod Fn

Матричная форма ЧП Ферма по основанию 2

Введение в матричные модели БА ЧП Ферма

Матричные модели БА ЧП Ферма по основанию 2

Матричная форма ЧП Ферма по смешанному основанию

Матричная модель БА ЧП Ферма для двух сомножителей

Матричные модели БА ЧП Ферма по основанию T

Матричные модели БА ЧП Ферма по основанию 4

Матричные модели БА ЧП Ферма по смешанному основанию

Разложение N — длины ЧП Ферма на два сомножителя

Товарищ, верь...
                    Поговорка

Матричная форма ЧП Ферма по основанию 2.

Введение в матричные модели БА ЧП Ферма.

Рассмотрим прямое и обратное ЧП Ферма в матричных обозначениях.

SN = RN · xN mod Fn ,
xN = N−1 RN−1 · SN mod Fn ,

где xN=x[t] — N-точечный входной сигнал, SN=S[w] — N-точечный спектр Ферма, RN={rootwt} — матрица ЧП Ферма размером NxN. Структура матрицы RN ЧП Ферма аналогична структуре матрицы ДП Фурье, однако здесь есть особенности, позволяющие получить БА (быстрый алгоритм) с существенной экономией числа арифметических операций по сравнению с БА для ДП Фурье (т.е. с БПФ).

Для ЧП Ферма характерно, что длина преобразования N должна делить

N | Tmax=2b=O(Fn) и N=2v, v=1,...,b, b=2n

для простых Fn (где Tmax=Fn−1=2b )
и

N | Tmax=2n+2=O(Fn) и N=2v, v=1,...,n+2

для составных Fn.

ЧП Ферма существуют для всех длин N от 2 до Tmax .

Для простых Fn базовый элемент root в матрице ЧП Ферма RN связан с длиной преобразования N и сравним с некоторым КОРНЕМ из 1 gj

gj(Fn−1)/N ≡ root mod Fn .

Это сравнение разрешимо, если

root(Fn−1)/( (Fn−1)/N ) = rootN ≡ 1 mod Fn ,

т.е. если root совпадает с КОРНЕМ из 1 порядка N.

Длина N=4b совпадает с порядком T соответствующего КОРНЯ из 1, имеющего вид

root = √2

и поэтому в этом случае матрица ЧП Ферма выглядит так

RN = { root wt mod N } = { √2 wt mod N } , при N=4b ≤ Tmax .

Длины N от 2 до 2b совпадают с порядками T соответствующих КОРНЕЙ из 1, имеющих вид

root=22m,

и поэтому для них матрица ЧП Ферма выглядит так

RN = { root wt mod N } = { 2 2m · wt mod N } , при 2 ≤ N ≤ 2b < Tmax .

БА таких ЧП Ферма можно получить путём факторизации матрицы RN размером NxN в матрицы размера 2x2 (при N=2v, v=log2N), или в матрицы размера 4x4 (при N=4v, v=log4N), или в матрицы размера TxT (при N=Tv, v=logTN) .

Очевидно, что наиболее привлекательным является выбор базового элемента root=2, т.к. при этом умножения на степени

root wt mod N = 2 wt mod N

эквивалентны сдвигам целых чисел и выполняються быстрее.

Матричные модели БА ЧП Ферма по основанию 2.

Рассмотрим матричное выражение БА ЧП Ферма по основанию 2 с прореживанием по частоте (DIF) и замещением

(DIF) RN = ( (2)QN )

v=log2N

∏ ( (DIF)D2i ⊗ I2v−i )( I2i−1 ⊗ R2 ⊗ I2v−i ) ,

i=1

где матрица "бабочки"

R2 =

┌
│
│
└

1 1

1 −1

┐
│
│
┘

а диагональные матрицы весовых коэффициентов

D2i = ( I2i−1 ⊗ d2i−1 ) ,

d2i−1 = diag { root(2v−i)·p }, p=0,...,2i−1−1 .

Транспонирование матрицы (DIF)RN даёт матричную модель (ММ) БА для ЧП Ферма с прореживанием по времени (DIT) и замещением по основанию 2

(DIT) RN =

┌
│
│
│
│
│
└

v=log2N

∏ ( I2v−i ⊗ R2 ⊗ I2i−1 ) ( (DIT)D2v−(i−1) ⊗ I2i−1 )

i=1

┐
│
│
│
│
│
┘

((2)QN )T .

Пусть, например, Fn=F5=232+1. Тогда КОРЕНЬ root=256 порядка T=8 является базовым элементом ЧП Ферма длины N=T=8, т.е.

R8 = { 256wt } .

Это 8-ми точечное ЧП Ферма можно вычислять по БА, факторизуя матрицу R8 на log2N = log28 = 3 этапа преобразования по основанию 2, т.к. 23=8=N. Тогда диагональные матрицы будут иметь вид

d2i−1 = diag { root p·2v−i mod 8 }, p=0,...,2i−1−1 ,

d2i−1 = diag { 256 p·23−i mod 8 }, p=0,...,2i−1−1 .

Однако эту матрицу можно рассматривать и как бы с базовым элементом 2. Тогда диагональные матрицы будут иметь вид

d2i−1 = diag { (28)p·23−i } = diag { 2 8·p·23−i mod 8 } , p=0,...,2i−1−1 ,

хотя при этом во всех умножениях на степени 2 в показателе степени добавится 8 (28=256), но это не беда, т.к. все эти умножения на степени 2 заменяются на сдвиги.

Примеры матричных моделей БА ЧП Ферма по основанию 2.

Рассмотрим некоторые примеры построения структур БА для случая N=16, т.е.

S16 = 〈 R16 · x16 〉Fn ,

DIF — модель БА ЧП Ферма.

Модель с замещением, прямым входом и двоично-инверсным выходом (т.е. с прореживанием по частоте) при N=16

(DIF) R16 = (2)Q16

( I0 ⊗ R2 ⊗ I8 )( D4 ⊗ I4 )
( I2 ⊗ R2 ⊗ I4 )( D8 ⊗ I2 )
( I4 ⊗ R2 ⊗ I2 )( D16 ⊗ I0 )
( I8 ⊗ R2 ⊗ I0 ) ,

где диагональные матрицы весовых коэффициентов

D4 = diag (1,1,1,r4 )

D8 = diag (1,1,1,1, 1,r2,r4,r6 )

D16 = diag (1,1,1,1, 1,1,1,1, 1,r1,r2,r3, r4,r5,r6,r7 )

D2i = ( I2i−1 ⊗ d2i−1 ) ,

d2i−1 = diag { r16(24−i)·p }, (2i=4,8,16 , т.е. i=2,3,4) , p=0,...,2 i−1−1

i=2 , d22−1 = diag ( 1,r16(24−2)·1 }, p=0,...,22−1−1=1

i=3 , d23−1 = diag ( 1,r16(24−3)·1, r16(24−3)·2, r16(24−3)·3 }, p=0,...,23−1−1=3

i=4 , d24−1 = diag ( 1,r16(24−4)·1, r16(24−4)·2, r16(24−4)·3,

r16(24−4)·4, r16(24−4)·5, r16(24−4)·6, r16(24−4)·7 }, p=0,...,24−1−1=7

Например, здесь диагональная матрица весовых коэффициентов D2i при i=2 определяется так

D22 = D4 = ( I22−1 ⊗ d22−1 ) ,

где единичная матрица I22−1 = I2 имеет вид

I2 =

┌
│
│
└

1 0

0 1

┐
│
│
┘

а диагональная матрица

d22−1 = d2 = diag (1,(r16)4 )

или

d2 =

┌
│
│
└

1 0

0 (r16)4

┐
│
│
┘

Отсюда после тензорного произведения диагональных матриц получается

D4 = I2 ⊗ d2 = diag (1,1,1,r4 ) .

Далее, входной сигнал при N=16

x16[t]={xt, t=0,...,15}

Спектр до двоично-инверсной перестановки (т.е. до прореживания по частоте)

(DIF)S16[w]=( S0, S8, S4, S12, S2, S10, S6, S14, S1, S9, S5, S13, S3, S11, S7, S15 ).

Матрица двоично-инверсных перестановок — (2)Q16. И окончательно после перестановки элементов на выходе получаем спектр в нормальном порядке

S16[w]={Sw, w=0,...,15} .

DIT — модель БА ЧП Ферма.

Транспонирование матрицы (DIF)R16 даёт модель с замещением, с двоично-инверсным входом и прямым выходом (т.е. с прореживанием по времени)

(DIT) R16 =

( I8 ⊗ R2 ⊗ I0 )( D16 ⊗ I0 )
( I4 ⊗ R2 ⊗ I2 )( D8 ⊗ I2 )
( I2 ⊗ R2 ⊗ I4 )( D4 ⊗ I4 )
( I0 ⊗ R2 ⊗ I8 ) ((2)Q16)T ,

где диагональные матрицы весовых коэффициентов D4, D8, D16 такие же, как и в DIF-моделе.

Какая ночь! Я не могу,
Не спится мне. Такая лунность.
                              Сергей Есенин
                       "Какая ночь!...", 1925.

Матричная форма ЧП Ферма по смешанному основанию.

БА ЧП Ферма для остальных допустимых длин N ( 4b < N ≤ Tmax ) можно получить (это касается только простых чисел Ферма F3 и F4), если представить длину N в виде

N = N1·N2 = To·radixv .

Матричная модель БА ЧП Ферма для двух сомножителей.

Рассмотрим сначала общий случай разложения длины ЧП Ферма на два сомножителя

N = N1·N2 .

Тогда матрица RN в ЧП Ферма

SN = 〈 RN · xN 〉Fn

может быть факторизована в виде базовой ММ

(DIF) RN = (N1, N2)QN ( RN2 ⊗ IN1 )( (DIF)DN )( IN2 ⊗ RN1 ) ,

где диагональные матрицы весовых коэффициентов

DN =	diag ( IN2, dN21, ... , dN2N1−1 ) =	N1−1 ⊗ dN2k = k=0
=	diag { dN2k } , k=0,1,...,N1−1 ,

dN2k = diag ( rootN0, rootN1, ... , rootNN2−1 )k =

= diag { rootN p·k mod N } , p=0,1,...,N2−1

gj(Fn−1)/N ≡ rootN mod Fn ,

и ( (N1, N2)QN ) — матрица инверсий (перестановок) по смешанному основанию

N=N1·N2, а матрицы внутренних преобразований

RN1 = {rootN1 (N/N2)·ks mod N1 } = {rootN1 (N1)·ks mod N1 } = {rootN1ks mod N1 },

k,s=0,...,N1−1

RN2 = {rootN2(N/N1)·ks mod N2 } = {rootN2(N2)·ks mod N2 } = {rootN2ks mod N2 },

k,s=0,...,N2−1 .

Рассмотрим подстановку в базовой ММ вместо DN прямой (тензорной) суммы диагональных матриц

(RN2⊗ IN1) DN=

N1−1

⊗ RN2dN2k =

k=0

N1−1

⊗ (N2−1RN2dN2k RN2−1) RN2=

k=0

N1−1

( ⊗ CN2k) ( RN2⊗ IN1)

k=0

Очевидно, что CN2k — циркулянтные (циклические) матрицы (т.е. такие, у которых соседние строки и столбцы циклически сдвинуты на один элемент относительно друг друга), т.к. dN2k — диагональные матрицы, отсюда

( RN2 dN2k RN2−1 )

— циркулянтные матрицы. Тогда, подставляя полученное выражение в базовую ММ, получим

(DIF) RN = ( (N1, N2)QN )

N1−1

( ⊗ CN2k )( RN2 ⊗ RN1 ) ,

k=0

где CN2k = ( RN2 dN2k RN2−1 ) .

NB. Таким образом, для случая произвольных множителей N1 и N2 матрица ЧПФ RN может быть определена через кронекеровское (тензорное) произведение матриц ЧПФ RN1 и RN2 и прямую (тензорную) сумму циркулятных матриц CN2k , которая определяет оператор циклической свёртки.

Эта базовая ММ может быть записана и через двумерные массивы данных. В этом случае сигнал x[t] отображается в x[t1,t2] (в матричном виде — в xN1, N2), также и спектр S[w] — в S[w1,w2] , тогда ( IN2 ⊗ RN1 ) соответствует ЧПФ RN1 от каждой N1-й строки матрицы xN1, N2; умножение на RN — поточечному умножению матрицы DN1, N2 на [{xN1, N2}RN1], где DN1, N2 — послойная сумма из N1 матриц

DN1, N2 =
N1−1
Ξ
t1=0 diag{rootN1t1t2}, t2=0,..., N2−1 ;

( RN2 ⊗ IN1 ) — ДПФ RN2 от каждого столбца ( DN1, N2·[{xN1, N2}RN1] ); умножение на матрицу перестановки (N1, N2)QN — транспонированию выходной матрицы, отсюда

SN1, N2 = [ RN2 ( DN1, N2 · [{xN1, N2}RN1] ) ]T .

Матричные модели БА ЧП Ферма по основанию T.

Теперь рассмотрим простой случай разложения N по основанию radix

N = radixv ,

т.е. v=logradixN и, вводя новое обозначение radix=T так, что

N=Tv ,

запишем матричное выражение БА для ЧП Ферма по основанию T с прореживанием по частоте (DIF) и замещением

(DIF) RTv = ( (T)QTv )

v=logT(Tv)

∏ ( (DIF)DTi ⊗ ITv−i )( ITi−1 ⊗ RT ⊗ ITv−i ) ,

i=1

где диагональные матрицы весовых коэффициентов

DTi =

T−1

⊗ (dTi−1)k ,

k=1

(dTi−1)k = diag { rootN (Tv−i )·p·k mod N } , p=0,...,Ti−1−1 .

gj(Fn−1)/N ≡ rootN mod Fn

В этой модели БА внутреннее преобразование с матрицей RT должно вычисляться наиболее просто. Вспомним, что базовый элемент (обозначим его через rootT) в матрице RT связан с длиной (внутреннего) преобразования T и сравним с некоторым КОРНЕМ из 1 gj

gj(Fn−1)/T ≡ rootT mod Fn .

Это сравнение разрешимо, если

rootT(Fn−1)/( (Fn−1)/T ) = (rootT)T ≡ 1 mod Fn ,

т.е. если rootT совпадает с КОРНЕМ из 1 порядка T . Тогда имеем матрицу внутреннего преобразования ("бабочку")

RT = { rootT (Tv−1)·ks mod T } = { rootT ks mod T } , k,s=0,...,T−1 .

Транспонирование матрицы (DIF)RTv даёт ММ БА для ЧП Ферма с прореживанием по времени (DIT) и замещением по основанию T

(DIT) RTv =

┌
│
│
│
│
│
└

v=logT(Tv)

∏ ( ITv−i ⊗ RT ⊗ ITi−1 )( (DIT)DTv−(i−1) ⊗ ITi−1 )

i=1

┐
│
│
│
│
│
┘

((T)QTv)T

Пусть n=3, F3=257, T=2b=2n+1. Для лучшего root16=2 был найден КОРЕНЬ g1=27. Тогда T=2b=23+1=16 и подходит v=2, значит N=Tv=162=256 . Теперь имеем матрицу внутреннего преобразования порядка 16

RT = R16 = { 2(16v−1)·ks } = { 2(162−1)·ks } = { 2ks } ,

k,s=0,...,16-1 ,

поскольку 16 — это порядок КОРНЯ из 1 root16=2.

Пусть n=4, F4=65537. Для лучшего root32=2 был найден КОРЕНЬ g1=34910. Тогда T=2b=24+1=32 и пусть v=2, значит N=Tv=322=1024 . Теперь имеем матрицу внутреннего преобразования порядка 32

RT = R32 = { 2(32v−1)·ks } = { 2(322−1)·ks } = { 2ks } ,

k,s=0,...,32-1 ,

поскольку 32 — это порядок КОРНЯ из 1 root32=2.

Если v=3, N=Tv=323=32768, тогда тоже имеем матрицу внутреннего преобразования порядка 32

RT = R32 = { 2(32v−1)·ks } = { 2(323−1)·ks } = { 2ks } ,

k,s=0,...,32-1 ,

поскольку 32 — это порядок КОРНЯ из 1 root32=2.

Остальные примитивные КОРНИ из 1 для лучшего rootT=2 определяются по формуле

gj ≡ g1 · 3j·T mod Fn , j=2,...,Tv−1 .

Приведём пример факторизации матрицы ЧП Ферма для случая v=2, т.е. N=T2 (не забывая, что T — это порядок КОРНЯ из 1 rootT=2) . Тогда

(DIF) RT2 = ( (T)QT2 )

( RT ⊗ IT )( (DIF)DT2 )( IT ⊗ RT ) ,

где диагональные матрицы весовых коэффициентов

DT2 =

T−1

⊗ dTk ,

k=0

dTk = diag { rootN p·k mod N } , p=0,...,T−1 ,

gj(Fn−1)/N ≡ rootN mod Fn

и матрица внутреннего преобразования ("бабочка")

RT = { rootT ks mod T } = { 2 ks mod T } , k,s=0,...,T−1 , т.к. rootT=2 .

Матричные модели БА ЧП Ферма по основанию 4.

Рассмотрим для примера матричное выражение БА ЧП Ферма по основанию 4 с прореживанием по частоте (DIF) и замещением

(DIF) RN = ( (4)QN )

v=log4N

∏ ( (DIF)D4i ⊗ I4v−i )( I4i−1 ⊗ R4 ⊗ I4v−i ) ,

i=1

где матрица "бабочки"

R4 =

┌
│
│
│
│
│
│
│
└

1 1 1 1

1 2b/2 −1 −2b/2

1 −1 1 −1

1 −2b/2 −1 2b/2

┐
│
│
│
│
│
│
│
┘

, b=2n

заметим, что в поле GF(Fn)

2b/2 = 22n−1 ≡ √−1 mod Fn ,

и диагональные матрицы весовых коэффициентов

D4i =

4-1

⊗ (d4i−1)k ,

k=1

(d4i−1)k = diag { rootN (4v−i )·p·k mod N } , p=0,...,4i−1−1 ,

gj(Fn−1)/N ≡ rootN mod Fn

Транспонирование матрицы (DIF)RN даёт ММ БА для ЧП Ферма с прореживанием по времени (DIT) и замещением по основанию 4

(DIT) RN =

┌
│
│
│
│
│
└

v=log4N

∏ ( I4v−i ⊗ R4 ⊗ I4i−1 )( (DIT)D4v−(i−1) ⊗ I4i−1 )

i=1

┐
│
│
│
│
│
┘

((4)QN )T ,

Например, для n=3, F3=257. Пусть N=Tv=42=16, т.е. T=4, а v=2 (отметим, что root16=2). Тогда должно быть разрешимо сравнение

root(257-1)/( (257-1)/4 ) = root(256)/( 256/4 ) = root4 ≡ 1 mod F3 .

Отсюда root4=16 . Тогда имеем матрицу внутреннего преобразования порядка 4

RT = R4 = { root4(42−1)·ks } = { root4ks } = { 16ks } ,

k,s=0,...,4-1 ,

поскольку 4 — это порядок КОРНЯ из 1 root4=16. Иными словами 16-точечное ЧП Ферма с корнем root16=2 можно представить по основанию radix=4 (почти как двумерное 4x4 c внутреним 4-точечным преобразованием), но уже с базовым элементом — КОРНЕМ root4=16.

Например, для n=3, F3=257. Пусть N=Tv=43=64, т.е. T=4, а v=3 (отметим, что root64=???) , т.е. мы хотим представить ЧП Ферма длины N=64 в виде куба 4x4x4 . Тогда должно быть разрешимо сравнение

root(256)/( 256/4 ) = root4 ≡ 1 mod F3 .

Отсюда root4=16. Тогда имеем матрицу внутреннего преобразования порядка 4

RT = R4 = { root4(43−1)·ks } = { root4ks } = { 16ks } ,

k,s=0,...,4-1 ,

поскольку 4 — это порядок КОРНЯ root4=16. Иными словами 64-точечное ЧП Ферма с корнем root64=??? можно представить по основанию radix=4 (почти как трёхмерное 4x4x4 c внутреним 4-точечным преобразованием), но уже с базовым элементом — КОРНЕМ root4=16.

Пусть, например, Fn=F5=232+1. Тогда КОРЕНЬ root=2 порядка T=64 является базовым элементом ЧП Ферма длины N=T=64, т.е.

R64 = { root64wt } = { 2wt } .

Это 64-точечное ЧП Ферма можно вычислять по БА, факторизуя матрицу R64 на

log2N = log264 = 6 этапов преобразования по основанию 2, т.к. 26=64=N. Однако эту матрицу можно факторизовать и по основанию 4, т.к.

log4N = log464 = log4(43) = 3 .

Тогда должно быть разрешимо сравнение

root(232+1-1)/( (232+1-1)/4 ) = root(232)/( 232/4 ) = root4 ≡ 1 mod F5 .

Отсюда root4=216. Тогда имеем матрицу внутреннего преобразования порядка 4

RT = R4 = { root4(43−1)·ks } = { root4ks } = { 216·ks } ,

k,s=0,...,4-1 ,

поскольку 4 — это порядок КОРНЯ из 1 root4=216. Иными словами 64-точечное ЧП Ферма с корнем root64=2 можно представить по основанию radix=4 (почти как трёхмерное 4х4x4 c внутреним 4-точечным преобразованием), но уже с базовым элементом — КОРНЕМ root4=216.

Матричные модели БА ЧП Ферма по смешанному основанию.

Теперь вернёмся к общему случаю разложения длины ЧП Ферма на два сомножителя. В частном, но желанном случае

N = To·Tv ,

т.е. v=logT(N/To) .

(DIF)RN= QN(RTo ⊗ ITv)

v=logT(N/To)

∏ ( (DIF)DTo·Ti ⊗ ITv−i )( ITo·Ti−1 ⊗ RT ⊗ ITv−i ) ,

i=1

где диагональные матрицы весовых коэффициентов

DTo·Ti =

T−1

⊗ (dTo·Ti−1)k ,

k=1

(dTo·Ti−1)k = diag { rootN (Tv−i )·p·k mod N } , p=0,...,Ti−1−1 ,

gj(Fn−1)/N ≡ rootN mod Fn ,

и QN — матрица инверсий (перестановок) по смешанному основанию N=To·Tv, где To — остаточное число от разложения N на множители Tv, а матрицы внутренних преобразований

RT = {rootT (N/To)·ks mod T } = {rootT (Tv)·ks mod T } = {rootT ks mod T } ,

k,s=0,...,T−1 ,

RTo = {rootTo (N/Tv)·ks mod To } = {rootTo (To)·ks mod To } = {rootTo ks mod To } ,

k,s=0,...,To−1 .

В более общем случае разложения длины N ЧП Ферма на два сомножителя

N = Nm! = To ·
m
∏ Ti , To < Ti ,
i=1

который впрочем всегда можно обойти (ведь N=2v), ММ БА ЧП Ферма по смешанному основанию имеет вид

RNm!= QN(RTo ⊗ IN/To)

∏ (DTo·Ti ⊗ IN/(To·Ti))(I(To·Ti−1) ⊗ RT ⊗ IN/(To·Ti))

i=1

Поскольку матрица "бабочки" размерности To < T имеет вид

RTo = { (2T/To) ks } = { 2 (T/To)·ks mod To } , k,s=0,...,To−1 ,

то дополнительных умножений она не вносит (т.к. умножения на степени 2 — это сдвиги).

Сочинитель бедный, это ты ли
сочиняешь песни при луне?
Уж давно глаза твои остыли
на любви, на картах и вине.

Ах, луна влезает через раму,
свет такой, хоть выколи глаза...
Ставил я на пиковую даму,
а сыграл бубнового туза.
                           Сергей Есенин
   "Сочинитель бедный, это ты ли...", 1925.

Разложение N — длины ЧП Ферма на два сомножителя.

Например, для n=3, F3=257 можно представить ЧП Ферма длины N=128 — как 8x16 , а ЧП Ферма длины N=256 — как 16x16 или 4x4x4x4 .

Таблица. Разложение N — длины ЧП Ферма на два сомножителя: To и Tv , где T — порядок КОРНЯ из 1 rootT=4, rootT=2 или rootT=√2 .

Fn	T	rootT	N=To·Tv	rootTo (To)	rootT (Tv)	g1
F2	2 4 8 16	16 4 2 √2	2 4 8 8=2x4 16 16=2x8 16=42	16 (To=2) 16 (To=2)	4 (T1=4) 2 (T1=8) 4 (T2=42)	?? ??
F3	2 4 8 16 32 64 128 256	256 16 4 2 √2 ??? ??? 3	2 4 8 16 16=2x8 32 32=2x16 32=4x8 64 64=4x16 128 128=4x32 128=8x16 256 256=162	256 (To=2) 256 (To=2) 16 (To=4) 16 (To=4) 16 (To=4) 4 (To=8)	4 (8) 2 (T1=16) 4 (T1=8) 2 (T1=16) √2 (T1=32) 2 (T1=16) 2 (T2=162)	??? ??? ??? ??? ??? 27
F4	2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536	216 256 16 4 2 √2 ??? ??? ??? ??? ??? ??? ??? ??? ??? 3	2 4 8 16 32 32=2x16 64 64=2x32 64=4x16 128 128=4x32 256 256=4x64 256=162 512 512=16x32 512=2x162 1024 1024=322 2048 2048=2x322 4096 4096=4x322 4096=642 4096=163 8192 8192=2x642 8192=2x163 16384 16384=16x322 16384=4x642 16384=4x163 32768 32768=323 65536 65536=2x323	216 (To=2) 216 (To=2) 256 (To=4) 256 (To=4) 256 (To=4) 4 (To=16) 216 (To=2) 216 (To=2) 256 (To=4) 216 (To=2) 216 (To=2) 4 (To=16) 256 (To=4) 256 (To=4) 216 (To=2)	4 (T1=16) 2 (T1=32) 4 (T1=16) 2 (T1=32) √2 (T1=64) 4 (T2=162) 2 (T1=32) 4 (T2=162) 2 (T2=322) 2 (T2=322) 2 (T2=322) √2 (T2=642) 4 (T3=163) √2 (T2=642) 4 (T3=163) 2 (T2=322) √2 (T2=642) 4 (T3=163) 2 (T3=323) 2 (T3=323)	??? ??? ??? ??? ??? ??? ??? ??? 34910 ??? ??? ??? ??? ??? ??? ??? ??? ??? 34910 ???
F5	2 4 8 16 32 64 128	232 216 256 16 4 2 √2	2 4 8 16 32 64 64=2x32 128 128=2x64 128=4x32	232 (To=2) 232 (To=2) 216 (To=4)	4 (T1=32) 2 (T1=64) 4 (T1=32)	??? ??? ???
F6	2 4 8 16 32 64 128 256	264 232 216 256 16 4 2 √2	2 4 8 16 32 64 128 128=2x64 256 256=2x128 256=4x64	264 (To=2) 264 (To=2) 232 (To=4)	4 (T1=64) 2 (T1=128) 4 (T1=64)	??? ??? ???
F7	2 4 8 16 32 64 128 256 512	2128 264 232 216 256 16 4 2 √2	2 4 8 16 32 64 128 256 256=2x128 512 512=2x256 512=4x128	2128 (To=2) 2128 (To=2) 264 (To=4)	4 (T1=128) 2 (T1=256) 4 (T1=128)	??? ??? ???

NB. И так, все длины N=2v ЧП Ферма можно разложить на произведение двух сомножителей To и Tv: To=2, 4, 8 или (необязательное) 16 , где To — это порядок КОРНЯ из 1 , а в Tv основание T — тоже порядок КОРНЯ из 1, но равного rootT=4, rootT=2 или rootT=√2 .

Следовательно, для любой допустимой длины N=2v ЧП Ферма можно построить разные ММ БА, из которых затем выбрать оптимальную по нужному критерию.


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

◄ ЧП Ферма ▲ В начало текущей ММ 2мЧПФ ► ТЧП Гаусса ►