NTT-Fermat.HTM
◄ ДП Фурье в конечных полях    ▲ Выше     Примеры КОРНЕЙ ►    ТЧП Гаусса ►

Числовое преобразование Ферма


  Fn=1+22n
  n=0,1,2,3,4,.. 		Она глядит на вас так нежно,
она лепечет так небрежно,
она так тонко весела,
её глаза так полны чувством,
вечор она с таким искусством
из-под накрытого стола
свою мне ножку подала!

 Зачем я ею очарован?
Зачем расстаться должен с ней?
Когда б я не был избалован
цыганской жизнию моей,
когда б не смутное влеченье
 чего-то жаждущей души,
я б здесь остался — наслажденье
вкушать в неведомой тиши;
забыл бы всех желаний трепет,
мечтою б целый мир назвал...
И всё бы слушал этот лепет,
всё б эти ножки целовал.
Александр Пушкин
сентябрь 1833.


Деление 1/T mod Fn и условия существования ЧП Ферма
  Определение ЧП Ферма
  Условия существования ЧП Ферма
  Деление 1/T mod Fn
Переборной алгоритм вычисления 1/T mod Fn
Формулы для вычисления КОРНЕЙ и их порядков
Вычисление ЧП Ферма без умножений
Примеры КОРНЕЙ для простых модулей Fn
Примеры КОРНЕЙ для составных модулей Fn
Одномерное ЧП Ферма
  Матричная форма ЧП Ферма по основанию 2
    Введение в матричные модели БА ЧП Ферма
    Матричные модели БА ЧП Ферма по основанию 2
    Примеры матричных моделей БА ЧП Ферма по основанию 2
  Матричная форма ЧП Ферма по смешанному основанию
    Матричная модель БА ЧП Ферма для двух сомножителей
    Матричные модели БА ЧП Ферма по основанию T
    Матричные модели БА ЧП Ферма по основанию 4
    Матричные модели БА ЧП Ферма по смешанному основанию
    Разложение N — длины ЧП Ферма на два сомножителя
Двумерное ЧП Ферма (ЧПФ-2)
  Определение двумерного ЧП Ферма
  Модели вычисления ЧПФ-2
    Построчно-столбцовый алгоритм ЧПФ-m
    Вычисление ЧПФ-m по векторному основанию
    Вычисление 2D-спектра по ТА Григоряна
      Тензорное представление 2D-спектра при N — простом
      Способ вычисления 2D-спектра по ТА при N — простом
      Тензорное представление 2D-спектра при N=2v
      Способ вычисления 2D-спектра по ТА при N=2v
      Оценка вычислительной сложности ТА при N=2v
    Вычисление ЧПФ-2 по ПП Нуссбаумера
  Изоморфизм ДП Виленкина (ДП-В) и ДПФ-m
  Проблема оптимального БА для ДП Фурье
  Критика ЧПФ и ограничения его применения в ЦОС
  Ферма снова побеждает
    Модель вычисления одномерного ЧПФ через многомерное
    Модель вычисления ЧПФ-2 через одномерное ЧПФ и свёртки
    Модель вычисления одномерной ЦС через многомерную
  Резюме: сложность — плата за оптимальность


  
Принимаясь за дело,
соберись с духом.
                  Козьма Прутков
           "Мысли и афоризмы",56.

Деление 1/T mod Fn и условия существования ЧП Ферма.

Определение ЧП Ферма.

ЧП Ферма — числовое преобразование Ферма или преобразование по модулю чисел Ферма Fn сигналов, определённых в конечном поле Галуа GF(Fn) или в кольце с единицей Z/(Fn). ЧП Ферма аналогично ДП Фурье сигналов (числовых последовательностей, векторов) для поля C — рациональных комплексных чисел. Пара (прямое и обратное) преобразований Ферма выглядит так

            T−1
S[w] = ∑ x[t] rootwt ( mod Fn ) ,
          t=0
   w = 0,1,...,T−1

         T−1
x[t] = ∑ S[w] root−wt ( mod Fn ) ,
         w=0
   t = 0,1,...,T−1


причём   T|(Fn−1)   и базовый элемент   root   сравним с некоторым примитивным КОРНЕМ из 1 gj
gj (Fn−1)/T ≡ root mod Fn .
Это возможно, когда   root   равно КОРНЮ из 1 порядка T, т.е. такому, что
б rootT сFn = 1   или   rootT ≡ 1 mod Fn .
Последнее следует из такой теоремы.

Теорема. Пусть   L|(Fn−1),   L > 1   и взаимно просты   root   и   Fn , т.е.

НбОД (root,Fn)=1 ,
тогда необходимое и достаточное условие разрешимости сравнения
gjL ≡ root mod Fn
есть разрешимость сравнения (это проверочное условие)
root(Fn−1)/L ≡ 1 mod Fn ,
причём в случае его разрешимости имеется L решений для gj.

В нашем случае с ЧП Ферма

L = (Fn−1)/T .
Из   T|(Fn−1)   следует, что   L|(Fn−1).   Так как   T < (Fn−1),   то и   L > 1.   Если root — КОРЕНЬ из 1 по модулю Fn , то выполняется и условие взаимной простоты
НбОД (root,Fn)=1 .
Отсюда проверочное условие имеет вид
root(Fn−1) / (Fn−1)/T = rootT ≡ 1 mod Fn ,
т.е. КОРЕНЬ из 1 root должен имееть порядок T, значит теорема доказана.


Условия существования ЧП Ферма.

Для того, чтобы T-точечное ЧП Ферма так же, как и ДП Фурье, обеспечивало существование (или было изоморфно) циклической свёртке по модулю Fn
            T−1
y[k] = ∑ x[t] h[ б k−t сT ] ( mod Fn ) , k = 0,1,...,T−1
          t=0

необходимо выполнение нескольких условий. При простом и составном Fn ЧП Ферма обеспечивает циклическую свёртку, если T и root взаимно просты с Fn , т.е.
( T,Fn ) = 1 ,
( root,Fn ) = 1 ,
и существуют обратные значения для T и root, т.е
б T·T−1 сFn = 1 ,
б root·root−1 сFn = 1 ,
и T является порядком КОРНЯ root, т.е.
б rootT сFn = б root−T сFn = 1 ,
и ещё
( б rootk−1 сFn, Fn ) = 1 , где k = 1,...,T−1 ,
что на практике эквивалентно условию
  T−1
∑ rootkt = 0 ( mod Fn ) , где k = 1,...,T−1 .
t=0
Последнее условие более сильно, чем то, что root должно быть КОРНЕМ из 1 порядка T по модулю Fn .

Например, КОРЕНЬ root=2 порядка T=4 по модулю M=15 и все степени 20, 21, 22, 23 отличны друг от друга, и б 24 с15 = 1 . Однако б 22−1 с15 = 3 , но 3 не взаимно просто с 15, т.е. (3,15)≠1, т.к. 3|15 .

Обратное root−1 порядка T существует, если

б root·root−1 сFn = б root·rootT·root−1 сFn = б root·root(T−1) сFn = 1 и
б rootk·root−1 сFn = 1 , k=0,...,T−1 .

Для простого Fn эти условия определяют существование прямого и обратного ЧП Ферма вектора x[0..T−1]. При простом Fn ЧП Ферма также обеспечивает циклическую свёртку — базовую операцию в ЦОС .

Поскольку составные числа Ферма имеют вид (Лукас)

Fn = U1·U2· ... , где Uk = Ck·2(n+2)+1 ,
то T-точечное ЧП Ферма (обеспечивающее циклическую свёртку) для составного Fn будет существовать, если T-точечное ЧП Ферма существуют по модулю каждого сомножителя Uk и значит (по теореме Эйлера) T должно делить (Uk−1), а отсюда T должно делить 2n+2, т.е.
T | 2n+2 ,
причём 2n+2=4b=Tmax — это наибольшая длина преобразования по модулю составного числа Ферма Fn .

Вообще-то говоря, T-точечное ТЧП, определённое по модулю составного натурального (целого положительного) числа

M = p1(n1)p2(n2) ...
обеспечивает циклическую свёртку, если и только если
T | НбОД[ (p1−1), (p2−1), ... ] .


Деление 1/T mod Fn.

Нас интересуют такие КОРНИ из 1 root, у которых порядок T имеет вид   2M   (и значит существует быстрый алгоритм (БА) по снованию radix=2) , а сам root равен 2 или степени 2-х, т.е. имеет вид

root = 22m , m=0,...,n .
Заметим, что
б rootT сFn = 1
и поэтому
б root−k сFn = б root(T−k) сFn , при k≠0 .
Поскольку 2b — это порядок КОРНЯ   root=2, то
б 22b сFn = б 22·2n сFn = б 22n+1 сFn = 1 .
Тогда для T=2M, M≠0 деление на T по модулю числа Ферма Fn делается по формуле:
б 1/T сFn = б T−1 сFn =
= б 2−M сFn = б 22b·2−M сFn = б 2(2b−M) сFn .
Подставляя 2b = 2·2n = 2n+1 окончательно получим
б T−1 сFn = б 2−M сFn = б 2(2n+1−M) сFn .

Например, при F2 = 17 , 2b = 2·22 = 22+1 = 8 ,

для root=3 , T=16 , M=4   деление 1/T по модулю 17
б 1/16 с17 = б 16−1 с17 = б 2(−4) с17 = б 2(8−4) с17 = б 16 с17 = 16 ,
для root=2 , T=8 ,   M=3   деление 1/T по модулю 17
б 1/8 с17 = б 8−1 с17 = б 2(−3) с17 = б 2(8−3) с17 = б 32 с17 = 15 ,
для root=4 , T=4 ,   M=2   деление 1/T по модулю 17
б 1/4 с17 = б 4−1 с17 = б 2(−2) с17 = б 2(8−2) с17 = б 64 с17 = 13 .


  
Книга книгой —
а мозгами двигай.
                 Владимир Маяковский

Переборной алгоритм вычисления б 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).

NB. Таким образом операция

б T−1 сFn = б TT−1 сFn = б 1/T сFn
заменяется на специально подбираемое (и заранее вычисляемое) a такое, что деление a/T выполняется нацело ( формулы (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 =
= б 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 .
Поэтому   root2=б (Ц2)2 сFn=2 . Далее (по другой формуле),
б (Ц2)2 сFn = б ( 2b/4(1+2−b/2) )2 сFn =
= б 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 .
Обратная величина — КОРЕНЬ   1/root
root−1 = б (Ц2)−1 сFn = б ( 2b/4·(2b/2−1) )−1 сFn =
б 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 .
КОРЕНЬ   root = б Ц2 сFn для n > 1 имеет порядок
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 =
= б 4-1 с17 = б 4 с17 − б 1 с17 =
= б 22 с17 − б 20 с17 .
Это значит, что существует ЧП Ферма длины T=16 с примитивным КОРНЕм
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 ,
используя только сдвиги влево (т.е. умножения на степени двойки , сложения и вычитания.

NB. ЧП Ферма, с такими длинами T, равными степени 2, и базовыми элементами — КОРНЯМИ root, равными степени 2 или равными Ц2, могут вычисляться без операций умножения и представляют интерес для практики. Хотя КОРНИ   root , не равные степени 2, с порядками

T > 4b = 2n+2
для простых чисел Ферма F3 и F4 в принципе существуют и равны нечётной степени 3-х, но обойтись без целочисленных умножений, т.е. заменить их на сдвиги, в таких ЧП Ферма уже нельзя. Матрица преобразования при T=2v > 4b может быть даже факторизована в БА по основанию 2, но всё равно с обычными умножениями на степени базового элемента root (в диагональной матрице). Однако, если такую матрицу представить по смешанному основанию, т.е. разложить её размер на два сомножителя
N=To·Tv > 4b ,
равные степеням порядков T КОРНЕЙ из 1 вида
root=22m ,
то можно большую часть умножений выразить как умножения на степени 2, что эквивалентно сдвигам. Например, при
N=Tv > 4b
мы фактически представляем одномерное ЧПФ как многомерное ЧПФ-v по основанию T, и если при этом ещё и T=2b, то
rootT=2b = 2 ,
то все умножения (на степени 2) в блоках T-точечных ЧПФ заменяются на сдвиги. Хотя в диагональной матрице всё же остаются множители, равные степеням   rootN , не заменяемые на сдвиги.


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

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

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

Двумерное ЧП Ферма (ЧПФ-2)

  

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






Последнее обновление 09.09.2007, size=76 452 bytes

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