Содержание
1 Введение 4
2 Известные методы умножения в копечных полях характеристики два 6
3 Известные методы инвертирования в конечных полях характеристики два 9
4 Обіцие методы. 14
4.1 Сведение инвертирования в поле размерности п = щп^ к инвертированию в поле размерности п2..........14
4.2 Сведение инвертирования в поле размерности п = з
к инвертированию в поле размерности п3...................17
4.3 Расширение второй степени ..............................18
4.4 Расширение третьей степени..............................22
4.5 Расширение четвертой степени............................28
4.6 Расширение пятой степени................................39
4.7 Расширение шестой степени...............................48
5 Примеры 53
5.1 ЄР{ 22)...................................................53
5.1.1 Оптимальный нормальный базис 2-го типа, х2 + х + 1 53
5.2 <?Г( 23)..................................................54
5.2.1 Оптимальный нормальный базис 3-го типа, х3 + х2 -+-1 54
5.3 вР(2*) г= СР(2?)..........................................54
5.3.1 Оптимальный нормальный базис 3-го типа, х3 4-х2 + 1 54
5.4 СГ(210) = аР(225)........................................ 58
5.4.1 Оптимальный нормальный базис 2-го типа, х5+х4 +
х2 + х 4-1.........................................58
5.5 СР(2*) = ОР(2**)..........................................58
5.5.1 Оптимальный нормальный базис 2-го типа, х2 + х + \ 58
5.6 СР(212) = ОР( 23*)........................................60
5.6.1 Оптимальный нормальный базис 1-го типа, х4+хА+
г2 . г _і_ 1 «О
5.7 СР(215) = вР{235).........................................60
5.7.1 Оптимальный нормальный базис 2-го типа, х5+х4+
х2 -Ь х +1 г................. . . . ...............60
5.8 СР(2™) = СР{2^) и вР(230) = 23 ) ..................61
і
1
5.8.1 Оптимальный нормальный базис 2-го типа, х5 4-х4 4-
х2 4- х 4- 1 .....................................61
5.9 GF(230) = GF(2253) .................................................63
5.9.1 Оптимальный нормальный базис 3-іх) типа, Xі 4- х2 4-1 63
5.10 С/'ХЗ30) = CF(23*a) ...............................................63
5.10.1 Оптимальный нормальный базис 2-го типа, х2 4- х 4-1 63
5.11 С/'Х 24)......................................................64
5.11.1 Оптимальный нормальный базис 1-го типа, х4 4-х34-
х2 4- х 4-1.............................................64
5.11.2 Стандартный базис, х4 4- х 4-1.........................65
5.12 ОР(212) = Є.Р(243)............................................ 67
5.12.1 Оптимальный нормальный базис 3-го типа, х3 4-х'2 4-1 67
5.13 Є/Хг20) = ОР(245)............................................. 68
5.13.1 Оптимальный нормальный базис 2-го типа, х5 4-х4 4-
х2 4- х 4-1.............................................68
5.14 С/Х25)........................................................69
5.14.1 Оптимальный нормальный базис 2-го типа, х54-х44-
х2 4- х 4-1.............................................69
5.14.2 Стандартный базис, х5 4-х2 4-1...................69
5.15 С^(2Ш) = С/Х25*)..............................................74
5.15.1 Оптимальный нормальный базис 2-го типа, х2 4- х 4-1 74
5.16 Є.Р(215) = ОР(253)...................................... 76
5.16.1 Оптимальный нормальный базис 3-го типа, х3 4- х2 4-1 76
5.17 GF(220) = GF(254)....................................... 78
5.17.1 Оптимальный нормальпый базис 1-го типа, х44-х3-г
х2 4- х -Ь 1......................................78
5.18 С/Х26).................................................. 79
5.18.1 Оптимальный нормальный базис 2-го типа, хе 4-х5 4-
х4 4-х 4-1........................................79
5.18.2 Стандартный базис, х6 4-х3 4-1...................79
5.19 GF(230) = СР(26&).......................................83
5.19.1 Оптимальный нормальный базис 2-го типа, х54-х44-
х2 4- х 4-1.......................................83
5.20 Заключение..............................................84
6 Общие методы. Продолжение. 84
6.1 Расширение второй степени полей с четной степенью .... 84
7 Примеры 89
7.1 CF(24) = GF(222)......................................... 89
7.1.1 Стандартный базис {1,а}...........................89
2
7.2 СР(24) = <37*’(22а)................................................93
7.2.1 Нестандартный базис {а,/?}..................................93
7.3 (Щ28) = СР(24*)....................................................97
7.3.1 Нестандартный базис {а,/?}..................................97
7.3.2 Стандартный базис {1,а}....................................102
7.3.3 "Башня "базисов в поле Є^\28) .............................104
7.4 СГ( 216)..........................................................109
7.4.1 "Башня"базисов в поле СР(216) = С.Р(242 ).................. 109
7.4.2 "Башня"базисов в поле СК(2І6)...............................114
7.5 GF(224) = вР^) ...................................................117
7.5.1 Оптимальный нормальный базис 3-го тина, Xі + х2 +1117
7.6 С/^^СРСі43") .....................................................119
7.6.1 Башня базисов. Нестандартный базис {«,/?}..................119
7.7 248) = б?^(24а )..............................................122
7.7.1 Оптимальный нормальный базис 3-го типа, хл + х2 +1122
7.8 СР(2!20) = С^(24’35) .............................................123
7.8.1 Оптимальный нормальный базис 2-го типа, гг5Ч-я^-І-
хЗ-І-х+І .................................:................123'
8 Общие методы. "Башни"расширений. 124
8.1 Инвертирование в башнях нолей и схемы NИП1П2{щ). . . . 124
8.2 О схемах для М(п,іьлп3)...........................................125
8.3 Биквадратное расширение нолей ....................................126
8.3.1 Умножение..................................................126
8.3.2 Инвертирование.............................................128
8.4 Расширение шестой степени.........................................134
8.4.1 Умножение..................................................135
8.4.2 Инвертирование.............................................136
9 Примеры 141
9.1 С?/г(212) = а?{28Л)...............................................141
9.1.1 Биквадратное расширение....................................141
9.2 СР(220) = GF(25'')................................................142
9.2.1 Биквадратное расширение....................................142
9.3 CF( 23°) = GF( 25')...............................................142
9.3.1 Расширение шестой степени..................................142
10 Сравнения с известными результатами 143
10.1 Таблица...................................................143
10.2 Метод аддитивных цепочек..................................146
10.3 Метод ИоЬ и Тэищ
147
1 Введение
Конечные поля возникли в работах Гаусса [1] и Галуа [2], которые имели предшественниками Ферма, Эйлера, Лагранжа и Лежандра. Современное изложение их теории появилось в работах Мура [3) и Диксона [4|. В учебниках алгебры, например в |5], |6], конечным нолям уделяется мало внимания, за недавним исключением [7], но зато им посвящены специальные книги, например [8], |9], [10], [11], и в каждом солидной книге по теории кодирования есть глава (или главы), посвященные конечным полям.
В диссертации изучается сложность реализации арифметических операций в конечных полях характеристики два. Так как операции сложения и совпадающая с ней операция вычитания очень просты, то заниматься приходится только умножением и делением, а точнее инвертированием ненулевых элементов, так как деление сводится к инвертированию и умножению. Хотя полученные результаты можно применять и для программной имплементации операций в конечных полях, целью работы было исследование реализации этих операций логическими схемами, точнее схемами из произвольных функциональных логических элементов с двумя входами (схемами в базисе из всех двуместных булевых функций). Выбор этого базиса объясняется как сто удобством в теоретических рассмотрениях, так и тем, что он содержится практически во всех библиотеках логических элементов, используемых в практическом синтезе УЬБ1 — больших и сверхбольших интегральных схем.
Общая теория сложности схем для булевых функций была развита работах К.Э. Шснноиа [12] и О.В.Лупанова (например, [13]).
При построении логических схем в первую очередь было стремление в первую очередь минимизировать их глубину, т.с. максимальное число элементов в любой цепи, соединяющей входы схемы с се выходами. В практическом синтезе \;ЬБ1 стремятся минимизировать задержку схемы (время сс срабатывания после подачи на вход последнего сигнала). Задержка схема равна задержке ее критического пути (пути с максимальной задержкой), которая складывается из внутренних задержек его элементов и задержек соединяющих их проводников. Реально элемент НС имеет единой задержки, задержка определяется отдельно для каждой пары входной пин-выходной пин, причем она зависит довольно сложным образом от логических значений входа и выхода в рассматриваемый момент, от их капаситстов, от капаситстов связанных с ними провод-
4
инков и т.д. Учитывать псе это и теоретической работе представляется нереальным и неинтересным. Поэтому минимизацию реальной задержки естественно заменить па минимизацию глубипы, которая в определенном смысле пропорциональна ей.
Во вторую очередь (после минимизации глубины) было стремление уменьшить сложность схемы, т.е. число составляюпшх ее элементов. В реальном синтезе сложности соответствует площадь, занимаемая схемой, которая складывается из площадей, занимаемых ее элементами (а они у разных элементов разные, иногда даже если элементы логически одинаковые), и площади, занимаемой проводниками (которая иногда превосходит площадь занимаемую элементами, хотя проводники проводят по специальным слоям схемы, не содержащим элементов). В данной работе будет рассматриваться только сложность схем, но минимизация сложности главной цслыо не является, так как практически более важно увеличить быстродействие схемы, а сложность важна только лишь когда схема с трудом помещается на кристалле.
Схемы для арифметических операций в конечных полях широко используются в кодировании (например, (14), (15), (1G), (17)), криптографии (например, [18), [19], [20], [21], [10], [23], [24]), цифровой передаче сигналов (например, |25], [26] ) и др. областях.
В частности, такие схемы используются в аппаратной реализации как кодирзтощих, так и декодирующих устройств для линейных кодов, например, кодов ВСН и Рида-Соломона (например, [27], [28]), основанных на использовании алгоритма . Верлсксмпа-Мссси (например, [14], [29], [15], [16], [17]). В последнее время кодді ВСІІ и Рида-Соломона (а потому и используемые в них схемы) нашли применение в так называемых турбо-кодах, используемых в телевизионных приемниках со спутниковыми антеннами (например, [30]).
Арифметические схемы для конечных полей используются в криптографии с секретным ключом при построении блочных шифров (например, схе\пл для операций в иоле GF(2H) применяются в новом американском стандарте AES, разработанном бельгийскими криптографами и пришедшем на смену DES [31], [32]), и в построении генераторов псевдослучайных последовательностей (см., например, [33]).
В указанных применениях чаще всего используются поля характеристики два, как наиболее удобные дія схемной реализации. Далее рассматриваются только такие ноля. В отмеченных применениях используются ноля сравнительно малой размерности (п < 16 в кодировании и п < 32 при построении псевдослучайных генераторов), что дало основание Э.Р.Бсрлекемпу написать в [14] что ноля большой размерности представляют только академический интерес.
5
Однако с развитием криптографии с открытым ключом ноли большой размерности иаїшш применение во многих криптографических протоколах, основанных на предположении о трудности задачи дискретного логарифмирования, например, в ключевом обмене Диффн-Хеллмапа [34]. После появления работы Купсршмита [35] и современного совершенствования компьютерной и программистской техники стало ясно, что для повышения надежности таких протоколов необходимо использовать поля размерности не меньше 1000.
Но благодаря возникновению в работах Коблица и Миллера и последующему развитию эллиптической криптографии (см., например, [22], [36], [38], [37], [39], [40], [41], [42]) появилась возможность использовать поля размерности порядка 200, что облегчило проблему производства схем для арифметики в таких полях.
2 Известные методы умножения в конечных полях характеристики два
Эти методы зависят от типа базисов, используемых для представления элементов поля. Чаще всего используются стандартные полиномиальные базисы, в которых элементы поля размерности п представляются в виде многочленов степени п — 1, операции над которыми выполняются по модулю данного неприводимого над двухэлементным полем многочлена. Формулу для числа неприводимых многочленов данной степени и различные алгоритмы тестирования псприводимостн и факторизации приводимых многочленов можно найти в [43]. Эти вопросы иногда относит к области компьютерной алгебры и им посвящено довольно много работ, ссылки на которые имеются в [43] .
Описание алгоритма генерации неприводимых трехчленов и пятичле-нов можно найти в [44]. Нами была написана программа, генерирующая все неприводимые трехчлены и пятнчлеиы.
Схемы для умножения в стандартных базисах, порожденных неприводимыми трехчленами и пятнчленамн, были построены в диссертации Е. Мастровито [48]. Например, им были построены мультиплеры для 71 = 2,3,..., 16 сложности
7,17,31,49,71,97,148,161,199,241,351,371,478,449,537 и глубины
3,4,4,6,5,5,6,7,7,7,8,7,8,6,7.
6
Общие оценки сложности и глубины таких схем равны 0(п2),0(1одп), так как схема вычисления остатка по модулю данного неприводимого } многочлена является линейным оператором, применяя для которого ме-
тод Лупанопа [13] можно оценить сложность как 0(п2/1одп) и глубину как Ііо&я]'
Методом Карацубы [49] можно для тех же базисов построить схемы несколько большей, но такой же по порядку глубины, и сложности 0(п1°^3). Действительно, обычное умножение многочленов степени п выполняется методом Карацубы со сложностью 0{п1одїЛ) и глубиной Зк^2 п 4- 0(1) Вычисление остатка по данному модулю, как известно (см., например, [43),[50)), можно свести к умножению на подходящий многочлен. Применяя дня этого умножения еще раз метод Карацубы, получаем нужные оценки.
Вопросы практического использования метода Карацубы для умноження в поле СЕ(2") рассмотрены, в частности в диссертации К.Паара [52], где однако указанные выше общие оценки не упоминаются.
В этой диссертации также рассмотрены схемы для умножения в полях размерности п — 2к (башнях полей), предложенные в [53]. В частности, в [53] утверждается, что при п = 8 построен мультиплер сложности 113, а при п = 16 мультиплер сложности 378.
В работе [54] приведено несколько методов построения мультиплсра в поле ОР(2Лп) через мультиплсры в поле 6’^(2‘1п). Наилучшис мульти-плсры при п = 8,12,16,20,24,28,32 имеют сложность
117,216,390,546,813,1020,1569,
и глубину
10,9,11,13,11,14.
Эти мультиплсры по сложности меньше, чем мультиплсры Маегровито, но имеют большую глубину.
В [11] описано много разных конструкций для мультинлеров в нормальных, двойственных и слабодвойственных базисах. Большая часть этих схем являются не логическими (в технической терминологии бит-параплельными), а автоматными схемами (бит-ссриальными). Подобным схемам посвящено много работ, например, [55], часть из них упомянута 1 в (11). Конструируются также систолические схемы, например, [56]. Но
мы здесь занимаемся только логическими схемами.
Далее нам понадобится и будет описана схема Мссси-Омура |57] для умножения в произвольном нормальном базисе. Ее сложность равна п(Св+п-1), а глубина равна робг Л1 + 1> где С в — сложность базиса, т.с. число единиц в некоторой п х п матрице, связанной с базисом («таблице
7
умножения» для этого базиса, которая будет определена позднее). Если С в — 0(п:>), то сложность умножения в таком базисе будет 0(п3). Однако нормальные базисы в поле GF(2n) удобны тем, что в них возведение в квадрат выполняется с нулевой сложностью и нулевой глубиной. Поэтому в них удобно выполнять операцию экспонснциации — возведения в данную степень. Имплементации этой операции и оценке се сложности посвящено много работ (см., например, [58]), так как эта операция является основной во многих криптоалгоритмах, например, в ключевом обмене Диффи-Хеллмана.
Поэтому большой интерес вызвало открытие группой канадских математиков ([59]) т.н. оптимальных нормальных базисов, т.е. базисов е .минимальной возможной сложностью, которая оказалась равна 2п — 1. В дальнейшем было доказано, что других оптимальных базисов, кроме указанных в [59] не существует, но найдены [61],[С2] методы построения базисов низкой сложности, т.е. таких, что Св = О(га). Дія таких базисов сложность умножения равна 0(п2). К сожалению, оптимальные нормальные базисы, и нормальные базисы низкой сложности существуют не при любом п. Таблицы значений га, при которых существуют оптимальные нормальные базисы, имеются в [II].
Нами была написала программа, позволяющая неограниченно продолжать эти таблицы.
В работе [63] был предложен метод умножения в нормальных базисах сложности п(Св + Зга — 2)/2. В применении к оптимальному нормальному базису первого типа он дает оценку 2га2 — 1. Там же даны его применения к композитным нолям.
Далее мы используем этот метод в основном в ситуации композитных полей, применяя для его обоснования в каждом конкретном случае более простые рассуждения, чем в [63]. Глубина этого метода имеет вид log2 га + 0(1).
В работе [64] был предложен метод умножения в оптимальных нормальных базисах, а также » некоторых других базисах низкой сложности, имеющий сложность М(га) O(ralogra) и глубину O(logra), где М(га) — сложность умножения в соответствующем стандартном базисе. Последняя же может быть оценена не только оценкой Карацубы, но и оценкой Шенхагс 0(п log га log log га), (см. [51],[43]). Однако схема Шенхаге начинает превосходить схему Карацубы только при п порядка нескольких тысяч.
Применение метода [64] к произвольному нормальному базису даст схему сложности 0(п2/1одп) и глубины 0(1одп).
В стандартном же базисе наилучшая известная оценка сложности умножения всегда равна 0{п log n log log га) с одновременной оценкой глу-
8
бины 0{logn).
З Известные методы инвертирования в конечных нолях характеристики два
Так как инвертирование в поле GF(2") есть (п,п) булевский опера-юр, а глубина любой функции от п переменных не больше n+1 согласно известным результатам из теории булевской сложности, то при небольших п можно просто выписать булевские формулы, задающие этот оператор, а потом минимизировать их глубину. Однако сложность таких формул очень быстро растет, что не удивительно, так как очевидная верхняя оценка экспоненциальна, и практически таким образом удается рассмотреть случай п < 8. Но оценки для глубины получаются при этом хорошие. Можно этот метод сочетать с другими методами, что мы тоже делаем далее. Подобный прием в компьютерной арифметике называется использованием tabic lookup. Этот метод применялся, например, в [66].
Второй очевидный подход к задаче инвертирования — сведение ее к решению системы линейных уравнений 71-го порядка над полем GF(2). Если применить для этого наилучший известный метод Винограда- Ку-першмита с оценкой 0(п2-3 " (см. ['13]), то получим такую же оценку сложности инвертирования, но практически этот метод неприменим из-за большой мультипликативной константы в оценке его сложности. Больше шансов применить метод [65] с оценкой 0(пл/ log2 п). Однако этот метод, и любые другие модификации метода Гаусса не удобен для реализации логическими схемами и дает большую глубину. Известные параллсль-иые методы решения линейных систем непригодны для конечных полей. Тем не мспсс имеется много работ, в которых применяется модификации метода Гаусса в других методов решения линейных систем для инвертирования. Но при этом строятся нс логические, а автоматные схемы (см., например, |67|).
Построению подобных схем посвящена диссертация М.Олофссона [68). В ней построено 4 типа таких инверторов, втом числе основанные на применении расширенного алгоритма Евклида и алгоритма Всрлексмпа-Мессн [14|,|29], [16],[17] и произведено их сравнение.
В ней также рассмотрено три типа инверторов в полях вида GF(2’^) («башне полей») и сделана ссылка на работу [69]. Теоретических оценок построенных схем не сделано. Есть ссылка на диссертацию Паара, который тоже занимался башней полей, и отмстил, что в [53] повторены результаты [69]. Но нет ссылки на новую работу Паара и Фана [70], п кото-
9
рой получены оценки сложности инвертирования 0(га1оВ2У) в этой башне и такие же оценки сложности умножения, улучшающие результаты его диссертации. Однако оценки для глубины его схем получаются 0(log2 и) для умножения и 0(log3n) для инвертирования. В то же время выше отмечалось, что для произвольного поля методом К арапу бы получается оценка сложности 0(п1°823) для умножения и O(logn) для глубины, правда с большой мультипликативной константой. Что лее касается инвертирования, 'го в общем случае, как будет видно ниже, известна оценка для глубины О {log2 л), правда при сложности 0(п2).
При компьютерных вычислениях для инвертирования удобен расширенный алгоритм Евклида, который имеет сложность 13л2/2 + 0(п) согласно [43]. Там же описана ускоренная версия этого алгоритма предложенная Шснхагс, имеющая сложность О (га log2 n log log га), правда с мультипликативной константой больше 100. Известны практически приемлемые ускоренные версии инвертирования методом Евклида, по крайней мере для некоторых модулей (неприводимых многочленов), например, |40]. Однако, кажегся пока неизвестны хорошие логические схемы, построенные но методу Евклида.
Наилучшая теоретическая оценка глубины инвертирования в иоле CF(2n) равна O(logra) и получена в работе Литов и Давида [71]. Улучшенное изложение имеется в работе фон цур Гатена [72]. Однако оценки сложности в этих работах приведены в виде n°W. Кажется, что показатель степени в них не меньше 4, а мультипликативная константа в оценке глубины не меньше 10, поэтому эти оценки имеют только теоретическое значение. Обычно эти оценки в технических работах даже не упоминают.
По теореме Ферма обратный элемент можно вычислить по формуле £-1 = £2"-2, и свести задачу интвертировапия к задаче экспопси-цирования частного вида. В работе [73] предложен часто цитируемый в криптографических работах основанный на теореме Ферма алгоритм инвертирования схемной сложности 0(n3) log п и глубины 0(log2n). Он рекуррентный и основан на применении тождества
х2»-1 _ £2ІП/3,"1.
Судя но названию работы он применялся для нормальных базисов, поэтому сложность и глубина каждого из возведений в квадрат равна пулю. Нетривиальных же умножений выполняется log71 + и(п) + 0(1), где u(n) — число единиц в двоичной записи га. Поэтому сложность схемы равна A/(ra)(logra + и{п) + 0(1)), а глубина равна D(n)(logn + и{п) + 0(1)), где М(га), D{n) — сложность и глубина схемы для умножения в данном нормальном базисе. Высокая оценка для сложности объясняется тем, что
10
сложность умножения в нормальных базисах методом Мссси- Омура может доходить до 0(п3).
Но выше отмечалось, что без увеличения порядка глубины можно в любом нормальном базисе умножать со сложностью 0(п2/1одп), а в базисах низкой сложности — даже со сложностью 0(nlogn log log и) с большой мультипликативной константой, и со сложностью 0(nIog23) с малой. Поэтому теоретическая оценка метода Ито равна 0{п2) всегда, а для базисов низкой сложности 0(п log2 п tag log п).
Отмстим еще, что и для стандартных базисов можно тем же методом получить оценку сложпости
0(п2)
и глубины <9(log27i), так как каждую из операций возведения в степень T2l"/2J можно, как и любой лилейный оператор реализовать схемой сложности 0{п2/1одп) и глубины O(logn), что дает общую сложность О (г?2) и общую глубину 0(log2 п), которые по порядку не меняются, если учесть сше сложность и глубину О (log п.) раз выполненных операций умножения в стандартном базисе.
Заметим еще, что оценку для глубины можно в случае нормальных базисов немного улучшить ДО П°ё2П1(П°ё2 »1 +1), не меняя по порядку оценку для сложности. Покажем, как это делается.
Отмстим, что основная идея указанного метода [73], состоящая в быстром возведении в степень 2'* — 1, известна с тридцатых годов и восходит к А.Брауэру и А.Шольпу -см. раздел об аддитивных цепочках в монографии Кнута (74|).
Аддитивной цепочкой называют любую начинающуюся с 1 последовательность натуральных чисел а0 = 1,аі,... ,ат, в которой каждое число является суммой каких-то двух предыдущих чисел (или удвоением какого-то предыдущего числа). Например, для инвертирования в поле GF(2n),n = 20 надо построить минимальную аддитивную цепочку для числа 2Л - 2, Для этого сначала надо построить минимальную линейную аддитивную цепочку для числа п — 1 = 19. Например, такой будет цепочка
1,2,4,8,16,18,19.
После этого выписываются в ряд числа
21 - 1,22 - 1,24 - 1,28 - 1,210 — 1.218 - 1,219 - 1,
и между ними вставляются последовательности удвоений. Так как удвоения реализуются путем соответствующей коммутации входов, то сложность инвертирования d поле GF(220) оцспивается как
/(20) < 6М(20),
11
где М{20) сложность умножения в нормальном базисе. Аналогично глубина оценивается как
D/(20) < 6DM(20).
Цепочку
1,2,4,8,16,18,19 можно удлинить, превратив ее в цепочку
1,2,3,4,8,16,18,19
сложности 7, по глубины 5, так как 19 = 16 + 3. По этой цепочке указанным выше приемом строится цепочка для 220 — 2, тоже имеющая глубину 5, если глубину удвоений считать равной нулю. Новая схема для инвертирования будет иметь несколько большую сложность
/(20) = 7М(20),
но меньшую глубину
Ш( 20) = 5DM(20).
Оцепим сложность и глубину умножения в нормальном базисе в поле GF(22Q). Согласно [11] наименьшая сложность нормального базиса п этом поле равна 63, и таким базисом является, например, произведение оптимальных нормальных базисов полей GF{2Л), GF(25). Используя метод Мссси-Омура, усовершенствованный в [63], можно построить мультиплеер с параметрами
М(20) = М[п) = п{Св + Зп - 2)/2 = 10(63 + 58) = 1210,
DM(20) = 1 + flog2(Сб + 1)1 - 8.
Далее однако будет построен мультиплеср с той же глубиной и сложностью 625. Используя его, получаем схемы для инвертирования с параметрами
7(20) = 4375, D/(20) = 40,
/(20) = 3750, D7 (20) = 48.
В той же работе [73] предложено усовершенствование этого метода, пригодное только для составных размерностей п = тпк и основанное на использовании тождества
аГ1 = хт-ххт~\ г = (2П - 1)/(2* - 1).
Так как хг = х ■ х2* • • • х2к1п,к~1) равно норме N(x) элемента х над подполом GF(2k), то хг = N(x) <= GF{2k) и инвертирование выполняется
12
- Киев+380960830922