О схемах для арифметики в конечных полях

Известно (см. [1], [2]), что при использовании стандартных базисов в полях GF (2^П) сложность булевой схемы для умножения, построенной из двухвходовых элементов, равна О(п logn log log п). Для инвертирования (т.е. вычисления мультипликативного обратного в данном поле) известен быстрый алгоритм Евклида с оценкой сложности О(пlog² п loglogn) (см. [1], [3]). Однако мультипликативная константа в этой оценке велика (несколько сотен), и при реальных значениях п стандартный алгоритм Евклида работает быстрее. Кроме того, этот алгоритм затруднительно применить при построении булевой схемы для инвертирования. Методом [4] можно построить такую схему сложности: I (п) = О(п^(ш+1)/2 log2 п), где ш — экспонента матричного умножения. Однако величина мультипликативной константы здесь с трудом поддается оценке, также трудно оценить глубину этой схемы. Используя [5], можно построить схему для инвертирования глубины О(log2n) и сложности О(п^1од2 ^v/14(log2 п)^1од2^8/7), где мультипликативные константы сравнительно невелики, но и эта схема при реальных значениях п представляется неэффективной.

При использовании в поле GF (2^П) нормального базиса можно построить схему для умножения сложности О(п²/logn) (см. [6]). Если для инвертирования применить метод [7] (основанный на методе Шольца—Брауэра для вычисления 2^п — 1 аддитивными цепочками [8]), то можно построить схему сложности О(М^ (n)logn) = О(п²) с небольшой мультипликативной константой в оценке, где M n (п) — сложность умножения в данном базисе. Для некоторых специальных нормальных базисов (существующих не при всех п) можно построить более эффективные схемы для умножения, и, как следствие, для инвертирования. В [6] показано, что для оптимальных нормальных базисов первого типа можно построить мультиплер сложности М(п) + О(п), где М (п) — сложность умножения двоичных многочленов степени п — 1. Для оптимальных нормальных базисов второго типа в [6] указана оценка 3М(п)) + 3)¹ log2n + О(п). В [6] также показано, что если п = тк, т,к > п^с, С 6 1/2, (т, к) = 1, то для некоторого нормального базиса сложность умножения равна. О(п(т + к)/ logn) = О(п^2-С/ logn), откуда следует, что если п — достаточно гладкое число, то для некоторого нормального базиса сложность умножения равна О(п^2-С) при С >  0, характеризующем гладкость числа п. В [4] доказано, что для гауссовых нормальных базисов типа к в поле GF (2^П) сложность умножения равна О(М (пк)), а в [9] подобный результат получен в более общем случае.

К упомянутым результатам можно добавить также следующие.

Теорема 1. Для любого е >  0 при любом т п = m^s us > s_e можно указать в поле GF (2^П) базис (не стандартный и не нормальный), в котором можно построить схему умножения сложности М (m^s) < п^1+е/2 и схему инвертирования сложности I (m^s ) < п^1+е.

Доказательство. Пусть k < s — параметр, значение которого укажем позднее. Выберем наименьшее г такое, что 2^m’’ >  2т^к — 1, и г = s mod к. Тогда г = О(к). Поле

GF (2^{mS )} = GF (q^m ”} = GF (q^mki) ,q = 2^m, представим в виде башни расширений

GF (q) С GF (q^{mk )} C GF (⁽q^{mk )m} ) = GF ^q^m2^{k )} C ... C GF ⁽q^mki) . Для каждого этажа башни

GF (qi) = GF (Д ) C GF ((q^)^m') = GF ^q^) " ) = GF (qi+1)

выберем стандартный базис {1,a,...,a^mk-1}, определяемый неприводимым над полем GF (qi) многочленом pi(x) степени т^к таким образом, чтобы элемент а порождал нормальный базис {а, а^ ..., а^^т 1 }, где Q = qi. Тогда произвольный элемент поля GF(qi +1 ) можно представить в виде т^к-мерного вектора с компонентами из поля GF(qi) и в виде m^k(i+1)-мepнoгo вектора с компонентами из поля GF (q). Умножение в поле GF (qi+1) можно свести к умножению по модулю многочлена pi двух многочленов степени t = т^к — 1 над полем GF(qi). Известно [1], что умножение в поле GF (qi+1) сводится к трем умножениям многочленов степени t над полем GF(qi) и t сложениям в этом поле. Для умножения двух многочленов f, g степени t над полем GF(qi) можно сначала вычислить значения f(ai),g(ai) на произвольных 2t + 1 элементах его подполя GF (q), выполнить 2t + 1 умножение в поле GF(qi) и потом, используя интерполяционную формулу, восстановить по значениям h(ai) = f (ai)g(ai) коэффициентьi произведения h(x) = f (x)g(x). Для выполнения всех этих операций с помощью схемы Горнера и формулы Лагранжа требуется O(t²) операций сложения и умножения на элементы подполя GF(q) в поле GF(qi). Поэтому сложность умножения в поле GF (qi+1) оценивается как

М(GF(qi+1)) 6 3(2тк — 1)М(GF(qi)) + О(т2к)miк(log2 q)log23, так как сложение в поле GF(qi) выполняется со сложностью log2 qi = тгк log2 q, а сложность умножения на элементы подполя GF(q) равна М(GF(q))mik = O(log2 q)log2 3miк, потому, что это умножение сводится к тгк умножениям в поле GF(q). Если обозначить М(GF(qi')') через М(г), а 3(2тк — 1) через а, то полученное рекуррентное неравенство переписывается в виде М(г + 1) 6 аМ(г) + bm(i+1)k, где b = О(а)(тктТlog23) = О(а)то(к), М(0) = М(GF(q)) = O(log2 q)log23. Применяя индукцию, имеем

М(к) 6 а1М(0) + b (аі1-1тік + а/-2т2к + ... + т1к) , следовательно:

М (/) 6 а' М (0) + а-b ¹ "  ^{(т к} 6 а>М (0) +          6

1 — тк/а             1 — тк/а

6 а-М(0) +3а-Ь/2 = О(а-+1)то(к) = О(а)то(к)2-log23(2mk-1).

Учитывая, что q- = qmki, имеем I = (log2 logy q-)/log2 тк, log2 q- = п, log2 logq 41 log2 3(2mk -1)

М(GF (2Д) = М(GF (q')) = О(т^{г log}2³⁾)2^-log2^{3(2m -1)} = т^о(к)2       ^-^k       =

= mo(k^ (logq ®)1од™к 32m/ - = mo(k4log2 qtf0^ 3(2mk-1) = mo(kn°g™k 3(2mk-1), Поскольку logmk 3(2mk — 1) ^ 1 при mk ^ то, to для любого е > 0 при любом m, n = ms и s > se, имеем М (GF(2n)) = М (GF(2mS)) = n1+e/2. Умножение на каждом этаже башни можно выполнять и в нормальном базисе, если выполнить переход к стандартному базису, произвести умножение в нем и вернуться опять в нормальный базис. Грубая оценка сложности переходов между базисами равна m2kM (GF (qi)) + (m2k — mk )mik+r, ведь для выполнения как прямого, так и обратного преобразования координат требуется не более m2k умножений и не более m2k — mk сложений в поле GF(qi), имеющем размерность m^+r. с помощью циклических сдвигов вычислим в нормальном базисе систему степеней ж®, ж®2,..., ж^™ 1, Q = qi.

Возьмем кратчайшую линейную аддитивную цепочку (см. [8]) для числа t = m^k — 1, Oo = 1,01 = 2,02,.. . ,o l = t длины L = L(t), т.е. такую последовательность, что каждый ее член о_п при n >  0 равен o_n-i + Ok, k < n (если k = n — 1, то операция вычисления о_п называется шагом удвоения, а если k < n — 1 — линейным шагом). Построим линейную аддитивную цепочку, содержащую подпоследовательность

Q"1 — 1 Q«2 — 1     Qt — 1

Q — 1 , Q — 1 ,..., Q — 1’ между соседними членами которой производятся несколько последовательных шагов удвоения и один линейный шаг, пользуясь формулами

Q'² — 1 _ Q"' " - — 1 _ Q4 — 1   Q^ — 1

Q — 1 Q — 1         Q — 1     Q — 1

Так как возведение в степень Qⁿ в нормальном базисе делается бесплатно, а ж⁽⁽2^а0^-1)/(Q^-1) = ж, то для вычисления К (ж) = х^^^1-^/^^-1) требуется только L = L(m^k — 1) операций умножения. Еще одно умножение требуется для вычисления N (ж) = жК (ж). Поэтому сложность совместного вычисления К (ж),N (ж) оценивается как

LM(GF (qi+i)) 6 L (3(m^2k + 2m^k — 1)М(GF(qi)) + O(m^2k)m^ik(m^r)^log23) .

Используя формулу ж^-1 = К (ж)/N(ж), получаем рекуррентную оценку сложности инвертирования:

I (log₂ qi+1) = I (m ^{( i +1) k + r} ) 6 I (m^{ik + r} ) + m^k M(GF(q^) + + L(m^k — 1) ⁽3(m^2k + 2m^k — 1)M(GF(qi)) + O(m^2k )m^ik(m^r )^log2^з) . Очевидно, что L(t) 6 X₂(t) + ^₂(t) — 1 6 2log2 1 6 2klog₂ m, где X₂ (t) — длина двоичной записи числа t, a ^(t) — число единиц в ней (см. [8], где приведены и более точные оценки). Из полученных выше оценок по индукции с помощью неравенства оМ (n) 6 М (on) выводим оценку

I(m^s) = I (m^{lk + r} ) = I (log₂ q_i) 6 I(m^r ) + O(km^2k log₂m)M(log₂ q _{i - 1} ) =

= I(m^r ) + O(km^k log₂ m)M(m^s ) = O(km^k log₂ m)M (m^s).

Теорема доказана.

Укажем конкретный пример применения данного метода. Пусть m = 2,n = m^s. Выберем k = 8, тогда log_m/= 3(2m^k — 1) = log₂56 1 533 < 1.33 Получаем как следствие в некотором базисе поля GF (22^п) оценку сложности умножения O(2ⁿ '33) и оценку сложности инвертирования I (n) = О(М (n)). Эти оценки асимптотически лучше оценок [10] (полученных для другого базиса).

3.    Схемы в поле GF(2п) при n = 2 • 3k

При т = 3 можно уточнить доказанную теорему следующим образом.

Теорема 2. При п = 2 • 3^к в поде GF (2^П) можно указать некоторый (не стандартный и не нормальный) базис и построить в нем схемы умножения и инвертирования сложности:

М (п) = n(logз n)^{(log2 log}3 ^п)/2+°(¹),/ (п) = О(М (п)).

Доказательство. Положим qг = 2^ai ,аг = 2 • 3^b , bi = 2^г и рассмотрим башню полей

GF (qo) С GF(qi) С ... C GF (q_k ).

Так как qi — 1 = 2^ai — 1 кратно 3^bi+1 = 3пг, то в поле GF(qi ) найдется элемент порядка 3^bi+1 = 3щ, _И) значит, определено дискретное преобразование Фурье порядка 3^bi+1 = 3пг Как следует из [11], многочлены степени меньше пг = 3^b = аг/2 над полем GF(qi ) могут быть перемножены с помощью 24пг log3 пг +О(пг) умножений и 68пг log3 пг+О(пг) сложений в этом поле. Если обозначить сложность умножения в поле GF(qг ) через М(GF(qг )), то сложность умножения многочленов степени меньше пг над полем GF(qг ) будет оцениваться как

(24пг logзпг + О(пг ))М (GF (qг)) + (68пг log3 пг + О(пг ))пг.

Обозначим далее эту оценку через Мг . Выберем в этом поле примитивный элемент аг, тогда двучлен /г = х^Пі — аг будет неприводимым согласно теореме 3.75 [12], так как пг = 3^b делит qг — 1, а значит, и qг +1 — 1 = 2^ai+1 — 1. Выбирая в расширении GF (qг+1) поля GF(qг ) стандартный базис, соответствующий двучлену /г, и замечая, что умножение в этом базисе сводится к умножению многочленов степени меньше пг над полем GF(qг ) и приведению результата по модулю /г (которое выполняется школьным алгоритмом деления с помощью пг операций умножения и пг операций сложения в поле GF((qг ))). имеем

М(GF (qг+1)) 6 Мг + пгМ(GF(qг )) + аг +i 6

6 (24пг logзпг + О(пг))М(GF(qг)) + (68пг log3 пг + О(пг))пг + аг +i 6

6 (12аг log3 аг + О(аг))М(GF(qг )) + (17а² log3 аг + О(а²)) + аг +i 6

6 (12аг log3 аг + О(аг))М(GF(qг)) + (17а² log3 аг + О(а² )) 6

6 (12аг Ьг + О(аг))М(GF(qг )).

Отсюда по индукции следует, что log2 М(GF(qn)) 6 у log2 12агЬг + О(1) = ^((log2 3)2г + г log2 24) + О(1) 6 г=1                         г=1

• ^{6 (log}2 ³⁾²” ^{+ п}2/^{2 + (}22 ^{+ log}2 ^{3)п + О(1)}, значит,

М(GF(q_n)) 6 О ^3^2п+"2^(п2^+5п)^/2) ,q_n = 2²^³2".

Обозначая для краткости а_п = 2 • 3²" через N, имеем

М(GF (2ⁿ )) 6 N (log₃N)^и/2+°(¹) = N (log₃N)^(log2^log3 ^N)/2+o(1).

Получим теперь оценку для сложности инвертирования. В расширении GF (qг+1) поля GF (qг) выполняем инвертирование по формуле

Так как

.                             2               ^п*                     2              ",' ¹                  . .

N (x)q* = xq* xq* ... xq*  = xqi xq* ... xq*    x = N (x), то N(x) € GF(qt), поэтому для инвертирования нужно вычислить К(x),N(x), потом выполнить инвертирование в подполе G F(qt) и nt раз выполнить умножение в поле G F(qt). п*/3   2п*/3

Для вычисления N(x),K (x) сначала найдем у = xx^qt x^q *   , а потом

п*/ 3 - 1                          п*/ 3 - 1

N(x) = yy^qi .. .у⁴ *      ,К (x) = у* ... у⁴ *

,. ^п*^{/ 3}    „^2п*^{/ 3}

^q *        ^q i

^u        ^u          .

Поскольку

п» /3         пі /3    2п» /3    пі qt i          qt i qqi i qqi у i — x i x i x г

п*/ 3   2 п*/ 3

= xx^q* x^q*    = у,

то у € GF (q"*^/3). Значит, для вычисления у можно сделать 2 умножения в поле GF (qt+1)

"^/3  2"/3

и 2 операции возведения в степени q^  , q^    ^{в том же} поле, потом вычислить

п* / 3 - 1

N (x) = yy^q * .. .у⁴ *

и для вычисления К (x) сделать одно умножение в поле GF (qt+1) на элемент подполя GF(q" ^/3). Учитывая, что произвольный элемент поля GF (qt+1) можно представить в виде

X o +X i yt + Х 2 у 2

где Xj = xj + x₃y^3+:i + x₃ ( _n./_{3 -} i) ₊jXt^^{ni /3-1)} € GF (q_t"* ^{/ 3} ),j = 0,1, 2, то умножение в поле GF (qt+1) на элемент подполя GF(q"^{1 /3}) сводится к трем умножениям в этом подполе. Поле GF(q" ^/3) является расширением степени nt/3 = 3^b* ^-1 подполя GF (qt) 11 в нем можно выбрать базис { 1, 3t,..., 3" ^{/3 1}}, где 3"^/3 = at. Умножение в этом базисе совпадает с умножением многочленов степени nt/3 по модулю неприводимого над полем GF(qt) многочлена x"*^/3 +a _t . В расширении GF(qt) С GF(qt+1) ранее был выбраи базис {1, y _t ,..., y"^{1 -1}}, где у" = at. Положим 3t = 7³. Тогда произвольный элемент подполя GF(q"* ^/3) имеет относительно базиса {1, 3t,..., 3" /^{3 1}} координаты, которые совпадают с nt/3 координатами этого элемента относительно базиса {1, at,..., a"^{1 -1}} (а остальные его координаты в указанном базисе равны нулю). Поэтому сложность умножения элементов данного подполя оценивается неравенством

М(GF(q" ^/3)) 6 М (at+1/3) + (nt/3)M(GF(qt)) + at+1/3 6

6 (8nt log3 nt + O(nt))M(GF(qt)) + ((68/3)nt log3 nt + O(nt))nt + at+1/3 6

6 (4atbt + O(at))M(GF(qt)).

Оценим сложность возведения в степени q"* ^{/ 3} ,q ^{2 ni /3} в поле GF(qt +1 ). Произвольный элемент x поля GF (qt+1) можно представить в виде

Хо + Х1У' + X27t2, где Xj € GF(qn"/3),j = 0,1, 2, то

^п*^{/ 3} x^q*

^пі^{/ 3}         „^пі^{/ 3}

= X0q*   + Xq*

п^/ 3 q_t

У' *

+ X2q*

^п*^{/ 3}

2,о п*/3                    оп*/3           2-Оп*/3

y2q*   =Xo +X1yq*   +X2y2q*   .

Так как q"*/3 — 1 делится па qt — 1. а 'значит, кратно nt, то ytq*    = yt(at)(qi*/ 1)/п* = atyt,yt2q* 1 = y2(at)2(q3-1 1)/9 = bty2,at,bt € GF(qt), пД3                   9'. 3          ^q4/'3

поэтому ж91   = Хо + X1yt 1   + X2yt 1   = Хо + X1atyt + JC^y^, значит, возведение в сте пень q^/ в поле G F(qt+i) сводится к двум умножениям в подполе G F(д"1/) на элементы подполя GF(qt). Следовательно, его еложность оценивается как (2щ/3)М(GF(qt)). Точно так же оценивается сложность возведения в степень q2"1 /3. Поэтому суммарная сложность всех выполненных операций равна

Lt = 2М(GF (qt+i)) + ЗМ(GF(q" ^/3)) + (4щ/3)М (GF (qt)) 6

6 (36a»bt + O(at))М(GF (qt)).

Для вычисления

П.-/ 3 - 1 уу⁹¹ ... У⁹¹

где у Е GF(q" ^/3), применяем тот же прием, вычисляя сначала

„п1/9  „2п1/9

• 2    = уу⁹¹ у⁹¹    .

^1/ 3                  ^п1/ 9                                      "-/9

Так как у⁹ 1    = у, то 2⁹1   = 2, значит, 2 Е GF(q»¹ ). Для вычисления 2 нужно выпол-

"і/3\                                   "і/9 2"/9

нить два умножения в поле GF (q»  ) и возведение в степени qt  ,q»    ^{в том} же поле.

Аналогично предыдущим рассуждениям, оцениваем их сложность как

2М (GF(q "^³ )) + (4щ/9)М (GF(qt) 6 (24at - i bt + O(at - 1 ))M(GF(qt)).

Поскольку	П1/ 3 - 1                   пх/ 9 - 1 уу9і . . .у9       = 2Ғ11 . . . 29      ,
то остается вычислить	2Ғ41 ...Ғ41-1    ,2 Е GF(q"1^9').

Применяя тот же прием, сводим это вычисление со сложностью

2М (GF(q^⁹) + (4щ/27)М (GF(qt) 6 (24at - 2 bt + O(at - 2 )W(GF(qt)

к вычислению

ww91

.

Пх/ 27-1                    /07

..w⁹1       ,w Е GF (q"^1/27)

и т.д. Так как щ = 3^Ь1 , этот процесс закончится через bt шагов. На каждом шаге требуемая сложность уменьшается асимптотически в три раза, поэтому сложность вычисления N (ж) оценивается как

( 24| at - i bt + О(а»^М (GF (qt)), значит, сложность вычисления N (х),К (ж) оценивается как

(44ctbt + O(a» ))М (GF (qt)).

Отсюда следует рекуррентная оценка сложности инвертирования:

I (at+i) 6 I(at)+ntМ(GF (qt)) + (44a»bt + О(а»))М (GF(qt)-) 6

6 I (at) + (44atbt + О(а»))М (GF (qt()

Из нее по индукции получаем, что

I(а"( 6 52(44atbt + O(at))М(GF (q»)) + I(ao) = t=i

= (44a_n-ib_n-i + O(a_n—i))M (GF (q.-i)).

Поскольку М(GF (qt+i)) 6 (12a_tb_t + О(а_і))М(GF(q_t)), то предполагая, что

М (GF (qt+i)) = (12atbt + О(сі))М (GF (qt)), получаем асимптотическую оценку:

I (а,) 6 (у + «(1))

М (GF (q„)).

Замечая, что М(GF(q2)) = О (з2' +'2'22' 52 2 j , во всех случаях имеем

I (а.) = (44a2-ib2-i + O(C2-1))M (GF (q.-i)) = О ^^2П+²2⁽²2+⁵²)^/2) .

Поэтому при N = а₂ справедлив о равенство I (N ) = О(М (GF (2^N ))). Такие же оценки можно получить и для любого N = 2 • 3². Для этого выберем к так, чтобы 2^fc-1 6 и <  2^к и определим последовательность а^ = N, at—i = 2 • 3^^1og3^(ai/2))/2^, положим qt = 2^a* и рассмотрим башню полей GF (qg) С GF (qi) С ... С GF(q^ ). Теорема доказана.

Для практического построения схем для умножения и инвертирования в полях GF (2²) произвольной размерности можно разложить и на множители, равные степеням простых чисел, построить эти схемы для полей, размерности которых равны указанным множителям, сводя их построение к построению схем для полей простой размерности, а потом применить метод построения схем для полей составной размерности при условии взаимной простоты сомножителей. Для инвертирования в полях простой размерности применяется метод [7]. Вместо простых чисел, при возможности, можно применять размерности, для которых существуют оптимальные нормальные базисы, или гауссовы базисы малой сложности (см., например, [9]).

4.    Вывод

Для любого е >  0 при любом т, и = m^s и s > s_e можно выбрать в поле GF (2²) базис, для которого схемная сложность умножения меньше и^1+e/2, а сложность инвертирования меньше и^1+e. При и = 2 • 3^к для некоторого базиса можно получить для умножения оценки сложности и(1одз и)^(1од2 ^1og3 ²)^/2+^o(i) и по порядку такие же оценки можно получить для инвертирования.