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

В работах [5-7] для реализации криптографических протоколов было предложено использовать эллиптические кривые над полями нечетной характеристики. Как следствие появился интерес к реализации арифметики в этих и других полях нечетной характеристики (см., например, [8-11]). Дуурсма И. и Ли Х.-С. [12, 13] модифицировали быстрый алгоритм для быстрого вычисления спаривания на эллиптических кривых Y2 = X3 — — X ± 1 над полями GF(3n) из [5] и применили его для реализации спаривания Тейта, для гиперэллиптических кривых Cb = Y2 = Xp — X + b, b = ± 1. над полом k = GF(pn). GCD(n, 2p) = = 1, p = 3 (mod 4), и над расширениями extensions F = GF (ppn) i к К = GF (p2 pn) по ля k. Эти кривые могут рассматриваться как обобщение кривых E3,b: Y2 = X3 — X + b. В первоначальной версии алгоритма. Дуурсма-Ли помимо обычных арифметических операций используется операция извлечения кубического корня. Квон С. (см. [14]) предложил модификацию алгоритма. Дуурсма-Ли без операции извлечения кубического корпя. Этот модифицированный алгоритм мы называем ниже алгоритмом Дуурсма-Ли-Квона (ДЛК-алгоритмом). В [7] введено так называемое ц-pairing и показано, что для его вычисления можно в два. раза, сократить длину цикла, алгоритма. Дуурсма-Ли. В статье [15] показано, как исключить извлечение кубических корней по модулю три при вычислении ц-спаривания. В [16] предложен метод ускорения финального экспонен-цирования при вычислении ц-спаривания. Все эти алгоритмы реализованы в арифметике поля GF(36n). В [4] дано обобщение ДЛК-алгоритма на гиперэллиптические кривые Съ. Для реализации этого обобщенного алгоритма, используются поля GF(p2np) и подполя GF (pn) 1i GF(p2n). Для случая p = 3 это обобщение ДЛК-алгоритма сделано в [6,8-10]. Можно показать (см. [4]), что увеличение p влечет уменьшение сложности схемной реализации умножения в поле GF(p2pn) (при условии, что n изменятся так, что порядок поля существенно не меняется). В настоящей статье мы рассматриваем схемную реализацию арифметики в GF(7), GF(72). GF(7n). GF(77n). и GF(714n). оцениваем сложность п глубину соответствующих схем. Рассматриваются логические схемы из двухвходовых булевых элементов, реализующих двухместные булевы функции (см., например, [23]). Под сложностью схемы понимается количество составляющих схему функциональных элементов, что по существу совпадает с понятием битовой сложности. Глубина, схемы есть максимальное число элементов в любой цепи, соединяющей входы схемы с её выходами. Результаты могут быть применены при реализации основанных на. спаривании алгоритмов, упомянутых выше. В частности, можно показать, что с увеличением p уменьшается схемная сложность ДЛК-алгоритма (при сохранении того же уровня безопасности), что согласуется с идеей из [17] выбирать для реализации ДЛК-алгоритма. поля характеристики p = 7. Все вычисления, за исключением касающихся глубины схем, можно сформулировать в терминах программной реализации, что может найти применение в компьютерной алгебре. В статье используются следующие обозначения: M(q), M(GF(q)) — схемная сложность умножения, A(q), A(GF(q)) — схемная сложность сложения в конечном поле GF(q), имеющем порядок q. Обычно q = 7 либо q = 7m. D(M(q)), D(M(GF(q))) — глубина схемы умноже-

Работа поддержана АВЦП «Развитие научного потенциала высшей школы», проект 2.1.1/12136

ния, D ( A ( q )), D ( A ( GF ( q ))) — глубина схемы сложения в поло GF ( q ).

• II.    Схемы для арифметики по модулю 7

Лемма 2.1. Умножение в GF (7) может быть выполнено схемой сложности 25 и глубины 5.  □

На наборах 000, 111 он принимает значение 000, па. наборах 100, 011 — значение 010, па. наборах 010, 101 — значение 001, на. наборах 001, ПО — значение 100. Рассмотрим оператор a 2 = d 2 x 2 V d 1 x о V dq x 1, a 1 = d 2 x 1 V d 1 x 2 V dq x q , a о = d 2 x о V d 1 x 1 V dq x 2.

На наборах 000x2x1 x0, 111 x2x 1 x0 он принимает значение 000, на наборах 001x2x1xq, 110x2x1x0 — значение x 2 x 1 xq. на на борах 010 x 2 x 1 xq. 101 x 2 x 1 x 0 — значение x 1 x0x2. (x 1 x0x2)2 = 2(x2x 1 x0)2 mod 7. на наборах 100x2x1xq. 011x2x1x0 — значение xqx2x 1. (xqx2x 1)2 = 4(x2x 1 x0)2 mod 7. Тогда, умножение чисел (x2x 1 xq)2. (у2у 1 у0)2 по мс>дулто 7 реализуется оператором z 2 = a 2 ф т, z 1 = a 1 ф т, z о = a о ф т.

Действительно, если ( у ₂ у 1 у ₀)₂ = 0, то т = 0 и он принимает значение (000)2 = (000)2 • ( x ₂ x 1 x ₀)₂ mod 7; если ( у ₂ у 1 у ₀)₂ = 7, то т = 1 и он принимает значение (111)2 = 7 = 0 mod 7 = (111)2 • ( x ₂ x 1 x ₀)₂ mod 7; если ( у ₂ у 1 у ₀)₂ = a = 1 , 2 , 4. то т = 0 и он принимает значение a ( x ₂ x 1 x ₀)₂ mod 7; если ( у ₂ у 1 у ₀)₂ = = a = 3 , 5 , 6. то —a mod 7 = b = 4 , 2 , 1. т = = 1 и он пршшм.нет значение —b ( x ₂ x 1 x ₀)₂ mod 7 = = a ( x ₂ x 1 x ₀)₂ mod 7. Сложность схемы для оператора т, d ₂ , d 1 , d о paвна 7. глубина, выходов di равна

• 2, глубина выхода т равна 3. Сложность схемы для оператора, a 2 , a 1 , a ₀ равна. 15 + 7 = 22. глубина, равна. 5. Сложность схемы для оператора, z 2 , z 1 , z ₀ равна. 22 + 3 = 25. глубина, равна. 6. Если в схеме для a 2 , a 1 , a ₀ заме нить V на. ф . то от'ратор z 2 , z 1 , z ₀ можно реализовать формулами

z 2 = ( d 2 x 2 ф d i x о) ф ( d о x 1 ф т ) ,

• *z i = ( d 2 x i ф d i x 2) ф ( d 0 x о ф т ) ,        (2 . 1)

• *z 0 = ( d 2 x о ф d 1 x 1) ф ( d 0 x 2 ф т )

с той же сложностью 25 и глубиной 5. Отождествим набор (111)2 с набюром (000)2. так как 7 = = 0 (mod7).

Лемма 2.2. Сложение в GF (7) может быть выполнено схемой сложности 17 и глубины 8.  □

Доказательство. Действительно, складываем два. трехзначных двоичных числа, при помощи схемы, построенной по формулам (2.1) со сложностью 12 и глубиной 7, получаем сумму ( ст, е ₂ , е 1 , е ₀)₂. Приведение по модулю

• ^{( ст}, ^е 2 ^,е 1 , ^е 0)2 =

= ²3 ^{ст + ( е} 2 , ^е 1 ^,е 0)2 = ^{( е} 2 ^,е 1 ^,е 0)2 ^{+ ст} =

= ( z 2 z 1 z 0)2 (mod 7)

по формулам (2.1) имеет сложность 5 и глубину 3, так как при прибавлении однобитового числа, формулы (2.1) приобретают вид z 1 = x 1 + у 1, z 2 = x 2 +(x 1 у 1) , z3 = x3 + x2 (x 1 у 1) (mod 2).

Таким образом, схема сложения в GF (7) имеет сложность 17 и глубину 8. Если подсхему прибавления однобитового числа, построить по формулам:

z 1 = x 1 + у 1, z 2 = x 2 +(x 1 у 1) , z3 = x3 + (x2x 1)у 1 (mod 2), немного изменив порядок действий, то сложность подсхемы будет 6, по глубина, основной схемы увеличится лишь па. 2, а. не па. 3, так как вычисление x2x 1 можно произвести заранее. Эта схема сложения в GF(7) имеет сложность 18 и глубину 7. Если схему сложения (2.1) переписать в виде z1 = x1 + у1, z2 = (x2 + у2) + (x 1 у 1) , z 3 = ((x 3 + у 3) + x 2 у 2) + ((x 2 + у 2 )(x 1 у 1)) , z 4 = ((x 3 у 3) + (x 3 + у 3)( x 2 у 2))+

+ (x 3 + у 3)((x 2 + у 2)(x 1 у 1)), то полученная схема, будет иметь сложность 14 и глубину 4. Таким образом, схема, сложения в GF(7) будет иметь сложность 20 и глубину 6.

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

Лемма 2.3. Существует схема, для сложения сложности 18 п глубины 7 и схема, для сложения сложности 20 и глубины 6. □

Лемма 2.4. Сложение в GF (7) может быть выполнено схемой сложности 21 и глубины 4. □

Для умножения в поле GF (72) можно использовать две схемы. Стандартная схема, основанная па. формуле

(a + bo)(c + do) = (ac — bd) + о (ad + bc), имеет сложность 4M (7) + 2A(7) = 134 и глубину D(M(7)) + D(A(7)) = 12. Существует схема сложности 142 и глубины 9 и сложности 136 и глубины 11. Схема, в нормальном базисе, основанная па. формуле

((a + b)(c + d) — 2 bd) 7 + ((a + b)(c + d) — 2 ac) yp, имеет сложность 3M (7) + 4A(7) = 146 и глубину D(M(7))+2D(A(7)). Эта схема хуже. Но для больших p она имеет меньшую сложность, чем стандартная.

III. Умножение в поле GF(72n) над полем GF(72)

Умножение многочленов 23-й и 24-й степени. Для вычисления ДПФ 48 порядка используем стандартную конструкцию, описанную например, в [20].

Пусть е = ш 3 = 1, е ³ = 1. В поле GF (7) е = = 2 , е ² = 4.

Тогда F3 определяется равенствами у о = x 0 + x 1 + x 2, у 1 = x 0 + ex 1 + е2 x 2, У 2 = x 0 + e 2 x 1 + e4 x 2, и вычисляется формулами

z 1 = x 1 + x2 , z2 = x 1 — x2 , z3 = ez2 , z 4 = z 3 — x 2, z 5 = z 1 + z 4, у 0 = x 0 + z 1, у 1 = x 0 + z 4 , у 2 = x 0 — z 5 .

Далее будет удобно применять схему F 3, приспособленную не к числам xi, а к произвольным векторам. Эта. схема, такова:

z ₁ = x ₁ + x ₂ ,

z 2 = x 1 — x 2 ,

z ³= (

е + е²

^z 1 ^,

z 4 =

ε-

ε

z 2 ,

у 0 = x 0 + z 1 ,

z 5 = у 0 + z 3 ,   у 1 = z 5 + z 4 ,   у 2 = z 5 — z 4 .

В поло GF (7) имссм: 2 = — 1. М^² — 1 = = 2. Поэтому в этой схеме z 3 = 2 z 1. z 4 = —z ₂.

Опа удобна, для векторизации, то есть для применения к векторам xi, которые сами являются результатами применения одного линейного преобразования xi = F ( Xi ). Тогда для вычисления F 3 в указанной схеме можно использовать новые операции:

Z 1 = X 1 + X 2 ,

Z2 = X1 — X2 , у 0 = x 0 + z 1 = F(X 0 + Z1), z 3 = 2 z 1 = 2 F (Z1), z 4 = —z 2 = —F(Z2), оставив остальные без изменения. Если первоначальный вариант схемы при применении к векторам xi = F(Xi) требует трехкратного вычисления преобразования F, 6 векторных сложений и 2 скалярных умножения, то указанный вариант требует те же 6 векторных сложений, ио не требует скалярных умножений; вместо трехкратного вычисления F оно вычисляется один раз в чистом виде и два раза — умноженным на скаляры 2, — 1. Это понадобится далее.

Для вычисления ДПФ порядка 16 достаточно 17 скалярных умножений и 64 сложений. В поле GF (7²) умиожение на w ⁴ «бесплатно» (то есть имеет нулевую сложность), поэтому пропадает 1 + + 2 + 4 скалярных умножений и остается только 10.

Для вычисления ДПФ порядка 48 в поле GF (7²) применяем теорему Гуда-Томаса (см. [20]) и представляем F 48 ( X ) в виде

F48 = F3( F1б( X1) ,F1б( X 2) ,F1б( X 3)), где Xi — вектора, составленные из компонент вектора X по следующему правилу:

X 1 = ( x 0 , x 3 , . . . , x 45) ,

X 2 = ( x 16 , x 19 , ..., x 46 , x 1 , x 4 , ..., x 12) ,

X3     (x32, x35,  . . . , x47, x2, x5, . . . , x29), a F3 — это векторизация ДПФ 3-го порядка, рассмотренная выше. Так как для его вычисления используется 6 векторных сложений (то есть 96 обычных) и вычисляются преобразования F16, 2F16- —F16. то дополнитслыю нужно 192 сложения и 30 скалярных умножений. Окончательно необходимо провести 288 сложений и 30 скалярных умножений. Для умножения многочленов степени 23 достаточно сделать 48 умножений и три преобразования Фурье F48. Значит, кроме умножений, достаточно не более 864 сложений и 90 скалярных умножений. Отметим, что в первых двух ДПФ экономится по 48 сложений в каждом. Действительно, в векторе коэффициентов многочлена только первые 24 коэффициента могут быть

отличны от нуля, поэтому в векторе X 1 последние 8 коэффициентов IIулевые. в векторе X 2 имеется 8 подряд идущих (в циклическом смысле) нулевых коэффициентов и в векторе X 3 тоже. Деление многочленов 15 степени с такими наборами коэффициентов на двучлены x ⁸ ± 1с остатком выполняется бесплатно: для нахождения остатка, нужен только сдвиг коэффициентов, возможно, со сменой знака у некоторых из них. Глубина F 48 равна 8 D ( A (7)). Поэтому сложность циклической свёртки (см. [20]) многочленов 23-й степени равна.

858 A ( GF (7²)) + 48 M ( GF (7²)) = 35 604 .

Глубина, равна. 16 D ( A (7)) + D ( M ( GF (7²))).

Можно проверить, что сложность и глубина, циклической свертки многочленов 24-й степени оценивается так же. Но для умножения многочленов 24-й степени, кроме вычисления этой свертки, нужно еще одно умножение и одно вычитание в GF (72).

Умножение многочленов 27-й, 31-й и 49-й степени. Можно показать, что сложность умножения многочленов степени 27 равна

874A (GF (72)) + 62M (GF (72)) = 38 024, а глубина равна 17D(A(7)) + D(M(GF(72))).

Сложность умножения многочленов степени 31 равна

890A (GF (72)) + 48M (GF (72)) + 15 A (GF (72)) + + 44 M (GF (72)) + 99A (GF (72)) = = 1004A (GF (72)) + 92M (GF (72)) = 46 464, а глубина равна 18D(A(7)) + D(M(7)) = 131.

Сложность умножения многочленов степени 49 равна 90112, а глубина равна 20 D ( A (7)) + + D ( M (7)).

Замечание. Можно показать, что даже для малых степеней n 6 31 использование ДПФ имеет преимущество перед школьным методом, методом Карацубы [18,22] и методом Тоома. [19,22].

• IV. Схемы для умножения в поле GF(714n) над полем GF(72n)

Умножение двух многочленов шестой степени. Построим схему для умножения двух многочленов шестой степени fо + f1 X + • • • + f6X6, gо + g 1 X + • • •+g6X6 с коэффицпонтами из GF(72n) методом Тоома. [19, 22]. Выберем узлы интерполяции: 0, ± 1, ±2. ±3, ±ст, ±2ст, ±3ст. Здесь ст ость «мнимая единица» в GF(72), представленном в виде квадратичного расширения GF(7), так что ст2 = — 1 mod 7. Значения в узлах многочлена, f представим следующим образом:

f (0) = fо, f (1) = ((f0 + 1f4) + 3( f2 + 2 fб)) + + 6((f1 + 4 f5) + 5 f3) , f (— 1) = ((f0 + f4) + (f2 + fб)) — — 7(( f1 + f5 ) + f3), f (ст) = ((f0 + f4) — 8( f2 + fб)) +

• ⁺    10⁽⁽ f 1 ⁺ f 5) ^— 9 f 3 ) ^ст,

f ^{( — ст} ) = ⁽⁽ f 0 ⁺ f 4) ^{— (} f 2 ⁺ f б)) ^—

• ^—    11 ⁽⁽ f 1 ⁺ f 5) ^— f 3) ^ст,

f ⁽²⁾ = ^{(( f} 0 ⁺ 12^{2 f} 4) ⁺ 14 ⁽⁴ f 2 ⁺ 13 f 6)) ^{+ +} 17⁽⁽² f 1 ⁺ 15⁴ f 5) ⁺ 16 f 3) , ^{f ( — 2)} = ⁽⁽ f 0 ^{+ 2} f 4) ^{+ (4} f 2 ^{+ f} 6)) ^—

• ^—    18 ^{((2 f} 1 ^{+ 4 f} 5) ^{+ f} 3) ,

^{f (2 ст} ) = ^{(( f} 0 ^{+ 2 f} 4) ^— 19^{(4 f} 2 ^{+ f} 6)) ^{+ +} 21 ^{((2 f} 1 ^{+ 4 f} 5) ^— 20 ^f 3) ^ст, ^{f ( — 2 ст} ) = ^{(( f} 0 ^{+ 2 f} 4) ^{— (4 f} 2 ^{+ f} 6)) ^—

• —    22 ((2 f 1 + 4 f 5) — f 3) ст,

f (3) = f (—4) = ((f0 + 234f4) + 25 (2 f2 + 24 f6)) + + 28((4 f1 + 262f5) — 27 f3), f (— 3) = f (4) = ((f0 + 4 f4) + (2 f2 + f6)) —

• —    29 ((4 f 1 + 2 f 5) — f 3) ,

^{f (3 ст} ) = ^{f ( — 4 ст} ) = ^{(( f} 0 ^{+4 f} 4) ^— 30^{(2 f} 2 ^{+ f} 6)) ⁺

• ⁺    32 ^{((4 f} 1 ^{+ 2 f} 5) ⁺ 31 ^f 3) ^ст,

^{f ( — 3 ст} ) = ^{f (4 ст} ) = ^{(( f} 0 ^{+4 f} 4) ^{— (2 f} 2 ^{+ f} 6)) ^—

• —    33 ((4 f 1 + 2 f 5) + f 3) ст.

Сложность этих вычислений, учитывая указанные скобками разбиения (порядок действий при конструировании схемы занумерован индексами при арифметических операциях), равна. 33 A ( GF (7² n )) = 66 nA (7). В этом равенстве учтено, что A ( GF (7² n )) = 2 nA (7). Глубина этой схемы равна 3 D ( A (7)). Те же вычисления необходимо проделать и для многочлена д. Суммарная сложность их равна 132 nA (7). Найдём значения многочлена h ( X ) = f ( X ) • д ( X ), h ( X ) = h ₀ + + h 1 X + • • • + h ₁₂ X ¹² в выбрашibix узлах aj. j = = 0.....12. Сложис)сть вычисления hj = h ( aj ) =

= f (aj) g (aj), j = 0,... 12. njhi p = 7 составляет 13(3 M (GF (7 n)) +4 A (GF (7 n))) = 39 M (GF (7 n)) + + 52nA(7). Здесь использован нормальный базис с оценками сложности арифметики в нём из леммы 2.Г, элемент из GF(72n) представлен в виде многочлена степени n — 1 и ад GF (72). Оценим сложность схемы для интерполяции. Многочлен h(X), согласно методу Лагранжа, представляется в виде суммы фундаментальных многочленов. Фундаментальные многочлены (по (mod 7)) после некоторой перестановки есть:

- ( X ⁴ - 4)( X ⁴ - 2)( X ⁴ - 1) h (0) =

= - ( X ⁸ + X ⁴ + 1)( X ⁴ - 1) h (0) ,

• -    4 X ( X ⁴ - 4)( X ⁴ - 2)( X ² - 1)( X + ст ) h ( ст ) ,

• -    4 X ( X ⁴ - 4)( X ⁴ - 2)( X ² - 1)( X - ст ) h ( -ст ) ,

• -    4 X ( X ⁸ + X ⁴ + 1)( X ² + 1)( X + 1) h (1) ,

• -    4 X ( X ⁸ + X ⁴ + 1)( X ² + 1)( X - 1) h ( - 1) ,

• -    4 X ( X ⁴ - 1)( X ⁴ - 4)( X ² + 4)( X + 2) h (2) ,

• -    4 X ( X ⁴ - 1)( X ⁴ - 4)( X ² + 4)( X - 2) h ( - 2) ,

• - 4 X ( X ⁴ - 1)( X ⁴ - 4)( X ² - 4)( X + 2 ст ) h (2 ст ) ,

  - 4 X ( X ⁴ - 1)( X ⁴ - 4)( X ² - 4)( X - 2 ст ) h ( - 2 ст ) ,

  - 4 X ( X ⁴ - 1)( X ⁴ - 2)( X ² - 2)( X + 4 ст ) h (3 ст ) ,

  - 4 X ( X ⁴ - 1)( X ⁴ - 2)( X ² - 2)( X - 4 ст ) h ( - 3 ст ) ,

• -    4 X ( X ⁴ - 1)( X ⁴ - 2)( X ² + 2)( X + 4) h ( - 3) ,

• -    4 X ( X ⁴ - 1)( X ⁴ - 2)( X ² + 2)( X - 4) h (3) ,

так как для получения к -го фундаментального многочлена, нужно из произведения

X х (X - 1) х (X + 1) х (X - 2) х (X + 2) х х (X - 3) х (X + 3) х (X - ст) х (X + ст) х х (X - 2 ст) х (X + 2 ст) х (X - 3 ст) х (X + 3 ст)

удалить ( X - к ). к = ± 1 , ± 2 , ± 3 , ±ст, ± 2 ст, ± 3 ст. перемножить оставшиеся скобки и результат домно-жить на h ( к ) и разделить иа значение от к полученного многочлена, которое равно - 2, за исключением случая к = 0. где ои<э равно - 1. Пусть d 0 = -h (о), d 1 = - 4 h (1). d ₂ = - 4 h ( - 1) d 11 = = - 4 h (3 ст ), d 12 = - 4 h ( - 3 ст ). Вычисление коэффициентов многочлена h ( X ) по его значениям в 13 узлах можно представить в следующем виде:

h ( X ) = ( X ⁸ + ¹ X ⁴ + ¹1)[ d о( X ⁴ - 1) +

+1 X ( X ² — 1)( d 7( X + ст ) + ² d 8( X — ст )) +

+⁴ X ( X ² + 1)( d 1( X + 1) + ² d 2( X - 1))] +

+¹² X ( X ⁴ - ⁴1)[( X ⁴ - 2)(( X ² - 2)( d 11 ( X + 4 ст ) + +² d 12( X - 4 ст ))+⁴( X ² + 2)( d 5( X +4) + ² d б( X - 4))) +

+⁸( X ⁴ - 4)(( X ² + 4)( d 4( X - 2) + ² d з( X + 2)) +

• + 4( X ² — 4)( d 9( X — 2 ст ) + ² d ю( X + 2 ст )))] .

Индексы к сверху над каждой операцией указывают ее сложность в виде кА(GF(72n)). Отсутствие индекса, означает, что сложность равна, пулю. Поэтому сложность этих вычислений равна. А (GF (72 n ))[(2 + 2 + 4 + 1) + 1 + 1) + 12+ 4 + + ((2 + 2 + 4) • 2 + 8)] = 2nA(7) • 51 = 102nA(7). Глубина этой схемы равна 6D(А(7)). Суммируя полученные оценки, находим, что сложность умножения многочленов степени 6 6 над GF(72n) ость L = 132nA(7) + 13M (GF (72n)) + 102nA(7) = = 13M(GF(72n)) + 234nA(7). Глубина схемы равна 9D(A(7)) + D(M(GF(72n))). Приведение no модулю X7 - X + 2 многочлена двенадцатой степени d о + d 1X + • • • + d 12 X12 = c о + c 1X + • • • + c 6 X6 (mod X7 - X + 2) выполняется по (формулам: c6 = = d6 + d 12- c5 = d5 - 2d 12 + dц. c4 = d4 - 2d 11 + d 10. .... c 1 = d 1 - 2d8 + d7. c0 = d0 - 2d7. которые содержат 12 сложений-вычитаний в GF(72n)) и 6 удвоений (удвоения бесплатны при схемной реализации). Таким образом, приведение по модулю X7 -- X + 2 имеет сложность 12A(GF(72n)) = 24nA(7) и глубину 2D(A(7)), и тогда, учитывая полученную оценку сложности умножения многочленов шестой степени с коэффициентами из GF(72n), имеем

M ( GF (7¹⁴ n ) 6 13 M ( GF (7² n )) + 258 nA (7) .

Для глубины справедливо неравенство

D ( M ( GF (7¹⁴ n ))) 6 11 D ( A (7)) + D ( M ( GF (7² n ))) .

Умножение многочленов степени 6 на многочлены степени 3. В алгоритме ДЛК на. самом деле используется не умножение произвольных многочленов степени p- 1 над полем GF ( p ² n ), а многочлена степени p - 1 на многочлен степени ( p + 1) / 2, у которого старший коэффициент равен 1. Представляя последний в виде суммы X ^{( p +1)} / ² л многочлена, с тепепи нс выше ( p - 1) / 2. получаем, что такое умножение сводится к умножению многочлена степени p - 1 на многочлен вдвое меньшей степени и p - 1 сложениям в поле GF ( p ² n ). При p = 7 умножается многочлен степени 6 па. многочлен степени 3. Можно показать, что сложность такого умножения не превосходит

10 M ( GF (7² n )) + 140 nA (7) ,

• а. глубина, соответствующей схемы не превосходит

10 D ( A (7)) + D ( M ( GF (7² n ))) .