Содержание к диссертации
Введение
1 О схемах умножения целых чисел 14
1.1 Оптимизация метода Карацубы 14
1.2 Некоторые частные случаи метода Тоома 22
2 О сложности схем для арифметики в некоторых башнях конечных полей 32
2.1 О сложности схем для арифметики в некоторых башнях конечных полей 34
2.2 О схемах для умножения и инвертирования в композитных полях GF(2n) 42
3 О схемах умножения многочленов в некоторых конечных полях 55
3.1 Схемы для арифметики по модулю 7 61
3.2 Схемы для умножения в поле GF(7Un) 64
3.3 Некоторые эффективные схемы умножения многочленов над полем GF{72) 75
4 О схемах для арифметики в композитных полях большой характеристики 86
4.1 Схемная сложность операций в псевдомерсенновских полях 86
4.2 Схемы для умножения в башнях псевдомерсенновских полей 92
4.3 Умножение в полях GF(p2"), р = 216 + 1 108
4.4 О глубине инвертирования в поле GF(pu), р = 216 + 1 114
4.5 Умножение и инвертирование в поле GF(p2n) 119
Литература 124
- Некоторые частные случаи метода Тоома
- О схемах для умножения и инвертирования в композитных полях GF(2n)
- Схемы для умножения в поле GF(7Un)
- Схемы для умножения в башнях псевдомерсенновских полей
Введение к работе
В данной работе изучается реализация арифметических операций в некоторых конечных полях схемами из функциональных элементов.
Конечные поля возникли в исследованиях Гаусса [15] и Галуа [16]. Современное изложение теории появилось в работах Мура [40] и Диксона [41], а также в работах других авторов, например [4, 34, 50, 51]. Схемы для арифметических операций в конечных полях используются в криптографии, кодировании, цифровой передаче сигналов и других областях. В указанных применениях использовались поля сравнительно малой размерности (п < 32) [20], однако с развитием криптографии с открытым ключом поля большой размерности (п > 1000) нашли применение во многих криптографических протоколах, основанных на предположении о трудности задачи дискретного логарифмирования ([52, 53]). Благодаря развитию криптографии на эллиптических кривых появилась возможность использовать поля размерности порядка двухсот ( [6, 23, 42, 43]).
Теория сложности схем для булевых функций была развита в работах К. Э. Шеннона (см., например, [9]) и О. Б. Лупанова (см., например, [10], там же можно найти определение схемы, её сложности и глубины). Схемы обычно строятся из элементов, реализующих двуместные булевы функции. Под сложностью схемы понимается количество составляющих схему функциональных элементов. Понятие схемной сложности по существу совпадает с понятием битовой сложности. При конструировании логических схем стремятся уменьшить не только их сложность, но и глубину — максимальное число элементов в любой цепи, соединяющей входы схемы с её выходами, так как практически важно увеличить быстродействие схемы. Операции сложения и вычитания просты, поэтому наибольший интерес представляет умножение и инвертирование ненулевых элементов (инвертирование элемента поля есть нахождение мультипликативного обратного ему элемента в этом поле). Деление сводится к инвертированию и умножению. Умножение элементов конечного поля в стандартном базисе сводится к умножению представляющих эти элементы многочленов по модулю некоторого неприводимого многочлена, поэтому существенное значение имеет разработка эффективных схем для умножения многочленов над конечными полями.
Основной целью диссертации является получение эффективных верхних оценок сложности и глубины схем из двухвходовых булевых элементов для арифметики в некоторых башнях конечных полей, а также для умножения многочленов в некоторых конечных полях. Построенная в диссертации схемная реализация арифметики в конечных полях может найти применение в кодировании, криптографии, цифровой обработке
сигналов, а также может быть использована в программной реализации арифметических операций в конечных полях в компьютерной алгебре.
Краткое содержание диссертации опубликовано работах автора [54, 55, 56, 57, 58]. Работы [54, 55] выполнены в соавторстве. Автору диссертации принадлежат доказательства всех основных результатов. В работах [56, 57, 58] соавторов нет. Работы [54, 55, 56] опубликованы в журналах, рекомендованных ВАК для публикаций диссертационных материалов.
Первая глава служит предисловием к основной тематике и посвящена оптимизации метода Карацубы [7] и некоторых случаев метода Тоома [2, 8] для умножения n-битовых целых чисел с целью получения эффективных числовых оценок схемной сложности умножения для реально используемых на практике диапазонов изменения п. Методы синтеза схем для умножения целых чисел с некоторыми изменениями могут быть перенесены на умножение многочленов над конечными полями, что в свою очередь может быть использовано для эффективного схемного умножения элементов конечных полей.
Показано, что метод Карацубы умножения n-битовых чисел можно схемно реализовать с рекуррентной оценкой сложности
Т(2п) < ЗТ(п) + 52п - 9.
Этот метод эффективнее школьного метода для всех п > 16. На каждом шаге рекурсии в нем n-битовые сомножители эффективно разбивать на блоки длины [|] и [|J бит. В методе Карацубы эффективно производить не полную рекурсию, а при s = 3, п = 2s = 8 перейти на школьный метод. Сложность оптимизированного варианта метода Карацубы для п = 2s, s > 4, оценивается сверху как
^п1о^3-52п + 4,5. 27
Приблизительно это вдвое лучше неоптимизированного варианта.
Показано, что метод Тоома умножения n-битовых чисел для п = 4s, s > 4, в котором множители на каждом шаге рекурсии разбиваются на q = 4 части равной длины, можно схемно реализовать с рекуррентной оценкой сложности
Г(4п) < 7Г(п) + 662п + 1085.
В методе Тоома для q = 4 эффективно производить не полную рекурсию, а при 5 = 3, п — 4s = 64 перейти на оптимизированный вариант метода
Карацубы. Сложность оптимизированного варианта метода Тоома для 5 = 4, п = 4s, s > 4 оценивается сверху как
Апп г ,м 7 662 1085
402,5nlog47- —п —.
3 о
Приблизительно это в 4,5 раза лучше неоптимизированного варианта. В частности, Т(1024) < 1 279 651, а стандартный (школьный) метод умножения имеет оценку сложности выше шести миллионов.
Метод Тоома умножения n-битовых целых двоичных чисел для п = 8s, s > 5, в котором множители на каждом шаге рекурсии разбиваются на q = 8 частей равной длины, можно схемно реализовать с рекуррентной оценкой сложности
Г(8п) < 152» + 5762п + 63589.
В методе Тоома для q = 8 эффективно производить не полную рекурсию, а при s = 4, п = 8s = 4 096 перейти на оптимизированный вариант метода Тоома для q = 4. Сложность оптимизированного варианта метода Тоома умножения целых двоичных чисел для q = 8, п = 8s, s > 5 оценивается сверху как
Т(п) < 257,05nlogs15 - 823п - 4542.
Это приблизительно в 21 раз лучше неоптимизированного варианта.
Во второй главе изучается сложность и глубина схем для арифметики в некоторых башнях конечных полей характеристики два. Методы умножения в конечных полях зависят от типа базисов, используемых для представления элементов поля. Чаще всего используются стандартные полиномиальные базисы, в которых элементы поля размерности п представляются в виде многочленов степени п — 1, операции над которыми выполняются по модулю данного неприводимого многочлена. Очевидные оценки сложности и глубины таких схем равны 0(п2), O(logn). Методом Карацубы можно для тех же базисов построить схемы сложности 0(nlog23). Вопросы практического использования метода Карацубы для умножения в поле GF(2n) рассмотрены, в частности в диссертации К.Паара [36].
Известно (см. [22], [23]), что при использовании стандартных базисов в полях GF(2n) сложность схемы для умножения равна 0(п log п log log п). Для инвертирования в компьютерных вычислениях можно использовать быстрый алгоритм Евклида с оценкой сложности О(п log2 п log log п) (см. [22], [47]). Однако мультипликативная константа в этой оценке велика (несколько сотен), и при актуальных для приложений значениях п стандартный алгоритм Евклида лучше. Кроме того, этот алгоритм затруднительно применить при построении схемы для инвертирования. Известно,
что можно построить такую схему сложности 0(n^+1^2log2ri), где UJ — экспонента матричного умножения (см. [49]). Но величина мультипликативной константы здесь с трудом поддается оценке, также трудно оценить глубину этой схемы. Можно построить схему для инвертирования сложности 0(nlog2V^(log2n)log28/7) и глубины 0(\ogln), где мультипликативные константы сравнительно невелики (см. [19]), но и эта схема при реальных значениях п представляется неэффективной.
При использовании в поле GF(2n) нормального базиса можно построить схему для умножения сложности 0(n2/logn) (см. [1]). Если для инвертирования применить метод [24], основанный на методе Шольца-Брауэра [2], то можно построить схему сложности 0(М^(п) logn) = 0(п2) с небольшой мультипликативной константой в оценке, где Мдг(п) — сложность умножения в данном базисе. Для некоторых специальных нормальных базисов (существующих не при всех п) можно построить более эффективные схемы для умножения, и как следствие, для инвертирования. В [1] показано, что для оптимальных нормальных базисов первого типа можно построить схемы для умножения сложности М(п) + 0(п), где М(п) - сложность умножения двоичных многочленов степени п — 1. Для оптимальных нормальных базисов второго типа в [1] указана оценка ЗМ(п)) +у log2 п+0(п) и показано, что если п = тк, т,к > пс, С < 1/2, (т, к) = 1, то для некоторого нормального базиса сложность умножения равна 0(п(т + к)/logn) = 0(n2~c/logn), откуда следует, что если п — достаточно гладкое число, то для некоторого нормального базиса сложность умножения равна 0(п2~с) при С > О, характеризующем гладкость числа п.
Во второй главе диссертации построены схемы для умножения и инвертирования в башнях конечных полей вида GF(2n), п = ms. Далее приводятся формулировки результатов при помощи следующих обозначений: L(M(n)), М(п) - сложность схемы для умножения, L(I(n)), 1(п) -сложность схемы для инвертирования, L(S(n)) - сложность схемы для возведения в квадрат, D(M(n)) - глубина схемы для умножения, D(I(n)) -глубина схемы для инвертирования, D(S(n)) - глубина схемы для возведения в квадрат в конечном поле GF(2").
Теорема 2.1.1. Для любого є > 0 при любом т для n — rrf и s > s можно указать в поле GF(2n) базис, для которого можно построить схему умножения сложности M(ms) < п1+/2, и схему инвертирования сложности I(ms) < п1+.
Результаты этой теоремы в специальном случае п = 2 3fc усиливает следующая
Теорема 2.1.2. При п = 2 3fc в поле GF(2n) можно указать неко-
торый базис, для которого моснсно построить схемы для умножения сложности М(п) = n(log3n)(loS2log3n)''2+0(1) it схемы для инвертирования сложности 1(п) = 0(М(п)).
В работе [5] были указаны рекуррентные верхние оценки сложности и глубины схем для умножения и деления в некоторых базисах полей GF(2in), GF(26n) при нечетном п и п, взаимно простом с б, соответственно. Во второй главе диссертации получены подобные оценки для схем в некоторых нормальных базисах тех же полей, а также для схем в некоторых базисах полей GF(2Sn) при нечетном п и некоторых других композитных полей. Далее приводятся формулировки полученных результатов.
Теорема 2.2.1. Для расширения GF((2n)4) поля GF(2n) при нечетном п и выборе в поле GF(24) нормального базиса
{а, а2, а4, а8}, 1 + а + а2 + о? + а4 = О,
и произвольного нормального базиса в поле GF(2n), можно построить схемы для умножения и инвертирования со следующими рекуррентными оценками сложности и глубины
L(M(4n)) < Ш(М(п)) + 21n, D{M(4n)) < D(M(n)) + З,
L(/(4n)) < L{I{n)) + 19L(M(n)) + 13n, D{I{4n)) < W(M{n)) + 2 + max{D(/(n)), 2}. Можно также построить схемы для инвертирования с оценками
L(/(4n)) < L{I(n)) + \ЩМ{п)) + 15п,
D(I(4n)) < 3D(M{n)) +2 + max{D(/(n)),3}.
Теорема 2.2.2. Для расширения GF((2n)6) поля GF(2n), где п взаимно просто с 6, при выборе в подполе GF(26) нормального базиса
{а, а2, а\ а8, а16, а32}, 1 + а + а4 + а5 + а6 = О,
и произвольного нормального базиса в поле GF(2n), моснсно построить для умножения и инвертирования схемы со следующими рекуррентными оценками сложности и глубины
L(M(6n)) < 2ЩМ(п)) + 60п, D(M(6n)) < D{M(n)) + 4,
L(/(6n)) < L{I[n)) + 42L(M(n)) + 65n, D(I{6n)) = 4D(M (n)) + 4 + max{D(/(n)), 4}.
Теорема 2.2.3. В башне расширений GF(((2n)4)2) поля GF(2n) при нечетном п справедливы следующие рекуррентные оценки сложности и глубины умножения и возведения в квадрат:
L{M{8n)) < 27L(M(n)) + 80n, D(M(8n)) < D{M{n)) + 7,
L(S(8n)) < lOn + 4L(S(n)), D{S{8n)) < 5 + >(5(4n)).
Если в поле GF(2n) выбрать нормальный базис, то для инвертирования справедливы следующие рекуррентные оценки сложности и глубины:
L(I{8n)) < L(I(n)) + 45L(M(n)) + 101n,
D(I{8n)) < AD{M{n)) + 8 + max{>(/(n)), 6}.
Теорема 2.2.4. В башне расширений GF(((2")4)2) поля GF(2n) при нечетном п и выборе нормального базиса в поле GF(2n) справедливы следующие рекуррентные оценки слооїсиости и глубины умножения и инвертирования:
L{M{8n)) < 30L(M(n)) + 82n, D{M(8n)) < D{M(n)) + 5,
L(/(8n)) < L(I{n)) + 52L(M(n)) + 88n, D(I(8n)) < AD(M(n)) + 6 + max{D(I{n)), 2}.
В третьей главе изучаются схемы для умножения многочленов в некоторых конечных полях малой нечётной характеристики и схемы для умножения в этих полях. Особое внимание уделяется полям GF(7Un), где НОД(п, 14) = 1, имеющим приложения в криптографии на эллиптических кривых. В ней обычно применяются кривые или над простыми полями, или над полями характеристики два. Последние наиболее удобны для реализации в виде электронных схем (см., например, [35, 45, 6]). В связи с открытием возможности использования в криптографии так называемых билинейных спариваний, введенных в работах Вейля, Тейта и Лихтенбаума, для конструирования новых криптоалгоритмов начали применяться эллиптические и гиперэллиптические кривые над полями характеристики три (см., например, [25, 26]). Как следствие, появился
интерес к реализации арифметики в этих и других полях нечетной характеристики (см., например, [31, 32, 33, 46]). В частности, поля GF(p2pn), где НОД(п, 2р) = 1, р = 3 (mod 4), появляются в алгоритме Дуурсма-Ли [27], а поля GF(7Un) - в работе [30], но вопросы эффективной реализации арифметики в этих полях там не затрагиваются.
Далее приводятся формулировки некоторых результатов главы при помощи следующих обозначений: GF{q) - конечное поле порядка q, п -произвольное натуральное число, р - простое, M(G) - схемная сложность умножения, D(M(G)) - глубина схемы умножения в поле G, А(р) - сложность сложения, D(A(p)) - глубина схемы сложения , D(M(p)) - глубина схемы умножения в поле в поле GF(p), М(п) - сложность умножения многочленов степени меньшей п над GF(72).
Теорема 3.2.1. Умножение элементов поля GF(7Un) может быть выполнено схемой сложности M(GF(7Un)) < 13M(OF(72n))+258nA(7) и глубины D{M{GF{7Un))) < l\D{A{7)) + D{M(GF(72n))). В частности, при п = 31, M(GF(714-31)) < 698 554.
Следующая теорема может использоваться для оптимизации сложности алгоритма Дуурсма-Ли эффективнее, чем предыдущая теорема, так как указанная в ней оценка учитывает особенности этого криптоалгоритма.
Теорема 3.2.2. Умножение в поле GF(7Un) элемента f, представи-мого многочленом степени 6, на элемент д, представимый многочленом степени 4 с единичным старшим коэффициентом, имеет сложность не выше lOM(GF(72n)) + 176пЛ(7). Глубина схемы, не превосходит 13D(A(7))+D[M(GF(72n))). В частности, при п = 31, сложность умножения не превосходит 557 392, а глубина схемы не превосходит ЗШ(Л(7)) + D(M(7)) — 253. Ухудшив оценку сложности, можно получить оценку для глубины 129.
Выбор приведенных выше конкретных примеров мотивируется тем, что порядок поля GF(714'31) приблизительно равен 21000 и является минимально возможным, при котором обеспечивается необходимый уровень криптографической надёжности согласно современным стандартам. В следующей теореме указывается асимптотическая оценка сложности умножения многочленов произвольной степени над GF(72).
Теорема 3.3.1. Многочлены степени п— 1 над GF{72) могут быть умножены со сложностью М(п) < 6098707 nlog57.
В четвёртой главе изучаются схемы для арифметики в полях большой характеристики. Интерес к эффективной реализации арифметики в
таких полях также возник в связи с возможными применениями в криптографии на эллиптических кривых (см., например, [6]). С этой целью в [33] было предложено использовать поля с характеристикой, относительно мало отличающейся от степени двойки (такие простые числа в [33] названы псевдомерсенновскими), в которых существуют полиномиальные базисы, соответствующие неприводимым двучленам (такие представления этих полей в [33] названы оптимальными расширениями простых полей). Среди таких расширений в [21] выделены расширения размерности 2, 3 и представлены в виде башен полей, построенных из квадратичных и кубических расширений. С использованием этих башен (названных в [21] оптимальными башнями полей) в [21] была указана для оптимальных расширений [33] эффективная реализация умножения и инвертирования.
Далее для формулирования результатов используются следующие обозначения: M(q) - сложность умножения в GF(q), A(q) - сложность сложения в GF(q), М(С, q) - сложность умножения на константу С в GF(q). В работе [21] получен результат, который можно сформулировать следующим образом.
Умножение в башне полей GF(q2 ) имеет рекуррентную верхнюю оценку сложности
M(q2k) < tM(q) + 5(3* - 2k)A(q) + \{t - l)M(a0, q),
где многочлен х2 — а0 неприводим над GF(q), а0 є GF(q). Умножение в башне полей GF(qz ) имеет рекуррентную верхнюю оценку сложности
M(q3k) < 6kM(q) + 5(6fc - t)A{q) + ^(6* - l)M(a0,q),
где многочлен хь — а0 неприводим над GF(q), а0 Є GF(q).
Для случаев, когда характеристика поля является числом Мерсен-на или Ферма, в четвёртой главе диссертации предлагается несколько лучшая реализация арифметики в башнях полей некоторых типов. В отличие от цитированной работы в диссертации рассматривалась не программная, а схемная реализация. Но приведённые результаты (за исключением касающихся глубины) можно интерпретировать и в терминах программной реализации. Сравнения с результатом цитированной работы указаны в тексте четвёртой главы в виде замечаний.
Далее приводятся формулировки полученных результатов с использованием следующих обозначений: u>k - примитивный корень /с-ой степени из единицы в GF(q), є = w3; n, ki - неотрицательные целые, p -простое.
Теорема 4.2.1. Умножение в башне полей GF(q3), q = р", имеет оценку сложности
M(q3) < 5M(q) + 2lA(q) + 6М(2, q)+
+2(М(4, q) + M(l/2, q) + M(l/6, q)) + 2М(а0,р)
в предположении, что q — 1 кратно 3, двучлены хп — а0 u ж3" ~~ ао неприводимы над GF(p).
Теорема 4.2.2. Умножение в башне полей GF(q4), q = рп, имеет оценку сложности
M(q4) < 7M(q) + 6М(ш3, q) + 54A(q) + 6M(l/6, tf) + ЗМ(а0,р)
в предположении, что q — 1 кратно 12 и многочлены х11 -а0 и хАп — а0 неприводимы над GF{p).
Теорема 4.2.3. При q = рп, р = 213 - 1, п = 2fc 3fel 5*2 7кз ІЗ*4, ко = 0,1, умножение в башне полей GF(q5) имеет оценку сложности M(q5) <77A{q) + llM{q).
Теорема 4.2.4. Умножение в башне полей GF(q6), q — рп, имеет оценку сложности
М(д6) < 12M(q) + 12lA{q) + 6М{а0,р) + М(1/12,q)+ +2(Af(-3/2, q) + M(-^,q) + M (-1/8, q) + M(^f, q))+
+2{M{uA, q) + M(-3w4/2, g) + M(w4^^, ?))+
+M(^' Ч) + M(-u74/8,9) + М{ш4^-, q)
в предположении, что q — 1 кратно 12, многочлены хп — а0 и х6п — а0 неприводимы над GF(p).
Теорема 4.2.5. Умножение в поле GF(q7), q = рп, р = 213 — 1, имеет оценку сложности M(q7) < 13M(q)-\-344A(q) + 6A(p) в предположении, что п = 2к 3kl Ьк2 7кз 13fc4, kQ = 0,1.
Теорема 4.2.6. Умножение в поле GF(q9), q = рп, р = 217 —1, имеет оценку сложности M(q9) < 17M(q) + 57SA(q) +6А(р) в предположении, что n = 2k- 3kl Ьк2 174 ^о = 0,1.
Теорема 4.2.7. Умножение в поле GF(q13), q = рп, р = 213 — 1 имеет оценку сложности M{qn) < 26M(q) + 1026A(q) + 12А(р) в предположении, что n = 2ko- З*1 5к2 7кз 13fc4, к0 = 0,1.
Теорема 4.2.8. Умножение в поле GF(qli), q — рп, р = 213 — 1 имеет оценку сложности M(qu) < 26M(q) + 1032Л(д) + 13А(р) в предположении, что п = 2ко 3fcl 5fc2 7ка 13fc4, А;0 = 0,1.
Теорема 4.2.9. Умножение в поле GF(qls), q = рп, р = 217 — 1, имеет оценку сложности M(q18) < 35M(q) + 1825A(q) + ПА(р) в предположении, что п = 2ко З*1 5fe2 17fcs, к0 = 0,1.
Теоремы 4.3.2-4. Умножение в поле GF(q2), к<4, q = рп, п — 2т, р = 216 + 1, имеет оценки сложности
M{q4) < 7M{q) + 59Л(д) + ЗМ(3,р),
M(qs) < lbM{q) + mA{q) + 7М(3,р), M(ql&) < 31M(q) + 558A(q) + 15M(3,p).
Далее используются также следующие обозначения: I(q) - сложность инвертирования, S(q) - сложность возведения в квадрат, D(I(q)) - глубина схемы инвертирования, D(S(q)) - глубина схемы возведения в квадрат, D(M(C,q)) - глубина схемы умножения на константу С в поле GF(q), M{2s,q) = тах{М(С, q) : С = 2s, s = 1,2,3,... }, D{M(2S, q)) = max{D{M{C, q)) : С = 2s, s = 1,2,3,... }.
Теорема 4.4.1. В поле GF(p2m),p = 216 + 1, существует схема для инвертирования, у которой сложность рекуррентно оценивается как
I2m = /2m_: + 652т-і + 12М2т-і + 15Л2т-і + 5М(3,р) + М(6,р)+
+(2т-1-1)М(2,Р),
где Ik есть сокращение для I(pk), и аналогично определяются М/., Sk,Ak. Глубина этой схемы рекуррентно оценивается как
D{I2m) = D(I2m-i) + 2D{M2m-i) + D(S2m-i) + 2{D{A{p)) + D(M(3,p)).
Теорема 4.4.2. Для инвертирования в поле GF(q16), q = рп, п — 2т, р = 216 4- 1, может быть построена схема сложности
I(q) + 410M(q) + 245(g) + 2173Л(д) + 735M(2S, q) + 119М(3,р) + М(6,р).
Если D{M(q)) + 2{D(A(p)) + D(M(3,p))) < D(I(q)), то глубина этой схемы не больше
D{I{q)) + 4D{M{q)) + D(S(q)) + 19D{A(p)) + lOD{M(2s,p)) + 3D(M{3,p)).
В противном случае она не превосходит
5D{M{q)) + D{S{q)) + 21D(A{p)) + \0D(M{2s,p)) + 5D(M(3,p)).
Теорема 4.5.1. Умножение в поле GF(qn) для q = р2, р = 213 — 1, п = 5m, га = 1,2, имеет оценку сложности
M(q5) < 27М(р) + 121А(р), M{q25) < U62A(p) + 243М(р).
Теорема 4.5.2. Инвертирование в поле GF(q5), где q = р2п, р = 1 (mod 10п), может быть выполнено схемой, имеющей оценку сложности
I{q5) < I(q) + 28M{q) + U3nA(p) + (16n + 2)M{a0,p) +
+6n{M(u5,p) + М(ш2,р) + M{u>lp) + M{ujIp)), aQ Є GF(p).
Теорема 4.5.3. Инвертирование в поле GF(pWn), р = 1 (mod 10n), может быть выполнено схемой, имеющей оценку сложности
I(pWn) < 1(рп) + иЬпА(р) + 76М{рп) + ММ(а0,р)+
+6п(М(и5,р) + М{шІр) + М(и>1,р) + М(Ч4,р)), а0 Є GF(p).
Теорема 4.5.4. Умножение в поле GF(p2n) для р = 2к — 1 при п < 2fc_1, имеющем только простые нечетные делители, делящие р — 1, может быть выполнено с помощью схемы, имеющей оценку сложности
М(р2п) < (15 2т"2 + 9(2т-1(т - 2) + 1))М(р) +
+ ((12т + 7)2т-х + 9(2то"1(т - 2) + 1))А(р),
где 2т~1 < 2п - 2 < 2т, т < к. Если 2п - 2 = 2т, т < к, тогда к указанной оценке сложности прибавляется М{р2) + А{р2).
Указанными во введении обозначениями будем пользоваться в дальнейшем изложении.
Некоторые частные случаи метода Тоома
Для умножения столбиком двух n-разрядных натуральных чисел, представленных в позиционной двоичной системе счисления, требуется приблизительно Сп2 алгебраических операций умножения и сложения, где С - некоторая постоянная. Назовём этот способ школьным методом. Метод Карацубы, начиная с некоторого п, позволяет умножать быстрее.
Соотношение (1.1.10) позволяет найти нечётные значения п при которых хотя бы один ход рекурсивного метода Карацубы с последующим переходом в вычислениях на школьный метод оказывается проще непосредственного применения школьного метода. Этажи рекурсии в алгоритме умножения устроены следующим образом: вначале дважды применяется метод Тоома, в котором множители разбиваются на 4 части, затем трижды применяется метод Карацубы, а потом школьный метод. В чистом методе Карацубы согласно 1.1.13 получается оценка сложности То(п) 2 810 633 (вдвое хуже 1.2.27). В оптимизированном варианте метода Карацубы согласно 1.1.16 получается оценка Г,(п) 1 546 547 (на 21% хуже 1.2.27).
Для умножения в нормальных базисах используется схема Месси-Омура [37]. Ее сложность равна п(Св+п—1), а глубина равна [log2 п] + 1, где Св — сложность базиса, т.е. число единиц в некоторой п х п матрице, связанной с базисом («таблице умножения» для этого базиса). Если С в = 0(п2), то сложность умножения в таком базисе будет 0(п3). Существуют т.н. оптимальные нормальные базисы, т.е. базисы с минимальной возможной сложностью (см. [38]), которая равна 2п — 1. В дальнейшем было доказано, что других оптимальных базисов, кроме указанных в [38] не существует, но найдены методы построения базисов низкой сложности, т.е. таких, что Св = 0(п). Для таких базисов сложность умножения равна 0(п2). Оптимальные нормальные базисы, и нормальные базисы низкой сложности существуют не при любом п. Таблицы значений п, при которых существуют оптимальные нормальные базисы, имеются в [34]. В работе [48] был предложен метод умножения в нормальных базисах сложности п(Св + Зп — 2)/2. В применении к оптимальному нормальному базису первого типа он дает оценку 2п2 — 1.
Для практического построения схем для умножения и инвертирования в полях GF(2n) произвольной размерности можно разложить п на множители, равные степеням простых чисел, построить эти схемы для полей, размерности которых равны указанным множителям, сводя их построение к построению схем для полей простой размерности, а потом применить метод построения схем для полей составной размерности при условии взаимной простоты сомножителей. Для инвертирования в полях простой размерности применяется метод [24]. Вместо простых чисел, при возможности, можно применять размерности, для которых существуют оптимальные нормальные базисы, или гауссовы базисы малой сложности.
В [27, 28] алгоритм из [25] для быстрого вычисления спаривания в эллиптических кривых у2 = хъ —х±1 над полем GF(3n) был усовершенствован и перенесен на гиперэллиптические кривые Сь : у2 = хр—x+b, b — ±1, определенные над полем к = GF(pn), где п и 2р взаимно просты и р = 3 (mod 4). Эти кривые рассматриваются также над расширениями поля к, а именно над F = GF{ppn) и К = GF(p2pn). Рассматриваемые кривые являются обобщениями эллиптических кривых Ез,ь у2 = х3 — х + Ь. В первоначальном варианте алгоритма [27, 28], кроме обычных арифметических операций, использовалась операция извлечения кубических корней в поле GF(3n). Вариант этого алгоритма без использования этой операции был предложен в [29] (там также был дан вариант этого алгоритма для суперсингулярных кривых над полем GF(2n)). В [26] введено так называемое г/— спаривание и показано, что для его вычисления можно уменьшить вдвое длину выполняемого цикла в алгоритме Дуурсма-Ли. Известно, что в вычислении г]— спаривания можно обойтись без извлечения кубических корней. Известно, что можно ускорить алгоритм финального экспоненцирования при вычислении г/— спаривания. Во всех этих алгоритмах используется арифметика в поле GF(36n).
О схемах для умножения и инвертирования в композитных полях GF(2n)
К достаточно 2р раз возвести в степень р в поле к и выполнить не более p2logp сложений в этом же поле (при р = 3,7 достаточно р(р — 1) сложений). В силу указанного вида коэффициентов д при применении школьного алгоритма число умножений в поле G уменьшается до р((р +1)/2) (причем р((р —1)/2) из них являются умножениями вида к х G), и меньшего числа сложений в том же поле. Отсюда получаем оценку сложности умножения / на д в виде р(р + 2)М{к) +р{р + 12)А(к), где М(к), А(к) — сложность умножения и сложения-вычитания в поле к = GF{pn). В [30] предлагаются алгоритмы для спариваний на гиперэллиптических кривых, в которых используется умножение произвольных элементов в поле К. Поэтому далее будут предложены схемы для умножения в этом поле элементов общего вида. Поле GF(p2) есть квадратичное расширение поля GF{p), оно представляет собой множество упорядоченных пар элементов из GF(p), сложения и умножения которых определяются аналогично полю комплексных чисел. Тогда значения /у (а,-) для данного г, г = 1,..., 2р — 1, щ Є GF(p2), и данного j, j = 1,2, можно вычислить с помощью (р — 1) сложения в поле G и (р— 1) умножения в этом поле на элементы вида а или ста, где а Є GF(p) по схеме Горнера. Схемы для вычитания получаются путем навешивания отрицаний па биты, составляющие вычитаемое число. Поэтому сложность и глубина схемы для вычитания такие же, как у схемы сложения. В алгоритме Дуурсма-Ли на самом деле используется не умножение произвольных многочленов степени р — 1 над полем GF(p2n), а многочлена степени р — 1 на многочлен степени (р + 1)/2, у которого старший коэффициент равен 1. Представляя последний в виде суммы х р+1 2 и многочлена степени (р—1)/2, получаем, что такое умножение сводится к умножению многочлена степени р— 1 на многочлен вдвое меньшей степени и р — 1 сложениям в поле GF(p2n). При р = 7 умножается многочлен степени 6 на многочлен степени 3.
Теорема 3.2.2. Умножение в поле GF(7Un) элемента f, представи-мого многочленом степени 6, на элемент д, представимый многочленом степени 4 с единичным старшим коэффициентом, имеет сложность не выше lOM(GF(72n)) -f 17бпЛ(7). Глубина схемы не превосходит 13D(A(7))+D(M(GF(72n))). В частности, при п = 31, сложность умножения не превосходит 557 392, а глубина схемы не превосходит ЗШ(У4(7)) + D(M(7)) = 253. Ухудшив оценку сложности, можно получить оценку для глубины 129.
Конечные поля возникли в исследованиях Гаусса [15] и Галуа [16]. Современное изложение теории появилось в работах Мура [40] и Диксона [41], а также в работах других авторов, например [4, 34, 50, 51]. Схемы для арифметических операций в конечных полях используются в криптографии, кодировании, цифровой передаче сигналов и других областях. В указанных применениях использовались поля сравнительно малой размерности (п 32) [20], однако с развитием криптографии с открытым ключом поля большой размерности (п 1000) нашли применение во многих криптографических протоколах, основанных на предположении о трудности задачи дискретного логарифмирования ([52, 53]). Благодаря развитию криптографии на эллиптических кривых появилась возможность использовать поля размерности порядка двухсот ( [6, 23, 42, 43]).
Теория сложности схем для булевых функций была развита в работах К. Э. Шеннона (см., например, [9]) и О. Б. Лупанова (см., например, [10], там же можно найти определение схемы, её сложности и глубины). Схемы обычно строятся из элементов, реализующих двуместные булевы функции. Под сложностью схемы понимается количество составляющих схему функциональных элементов. Понятие схемной сложности по существу совпадает с понятием битовой сложности. При конструировании логических схем стремятся уменьшить не только их сложность, но и глубину — максимальное число элементов в любой цепи, соединяющей входы схемы с её выходами, так как практически важно увеличить быстродействие схемы. Операции сложения и вычитания просты, поэтому наибольший интерес представляет умножение и инвертирование ненулевых элементов (инвертирование элемента поля есть нахождение мультипликативного обратного ему элемента в этом поле). Деление сводится к инвертированию и умножению. Умножение элементов конечного поля в стандартном базисе сводится к умножению представляющих эти элементы многочленов по модулю некоторого неприводимого многочлена, поэтому существенное значение имеет разработка эффективных схем для умножения многочленов над конечными полями.
Схемы для умножения в поле GF(7Un)
Основной целью диссертации является получение эффективных верхних оценок сложности и глубины схем из двухвходовых булевых элементов для арифметики в некоторых башнях конечных полей, а также для умножения многочленов в некоторых конечных полях. Построенная в диссертации схемная реализация арифметики в конечных полях может найти применение в кодировании, криптографии, цифровой обработке сигналов, а также может быть использована в программной реализации арифметических операций в конечных полях в компьютерной алгебре.
Краткое содержание диссертации опубликовано работах автора [54, 55, 56, 57, 58]. Работы [54, 55] выполнены в соавторстве. Автору диссертации принадлежат доказательства всех основных результатов. В работах [56, 57, 58] соавторов нет. Работы [54, 55, 56] опубликованы в журналах, рекомендованных ВАК для публикаций диссертационных материалов.
Первая глава служит предисловием к основной тематике и посвящена оптимизации метода Карацубы [7] и некоторых случаев метода Тоома [2, 8] для умножения n-битовых целых чисел с целью получения эффективных числовых оценок схемной сложности умножения для реально используемых на практике диапазонов изменения п. Методы синтеза схем для умножения целых чисел с некоторыми изменениями могут быть перенесены на умножение многочленов над конечными полями, что в свою очередь может быть использовано для эффективного схемного умножения элементов конечных полей.
Показано, что метод Карацубы умножения n-битовых чисел можно схемно реализовать с рекуррентной оценкой сложности Т(2п) ЗТ(п) + 52п - 9. Этот метод эффективнее школьного метода для всех п 16. На каждом шаге рекурсии в нем n-битовые сомножители эффективно разбивать на блоки длины [] и [J бит. В методе Карацубы эффективно производить не полную рекурсию, а при s = 3, п = 2s = 8 перейти на школьный метод. Сложность оптимизированного варианта метода Карацубы для п = 2s, s 4, оценивается сверху как п1о 3-52п + 4,5. 27 Приблизительно это вдвое лучше неоптимизированного варианта. Показано, что метод Тоома умножения n-битовых чисел для п = 4s, s 4, в котором множители на каждом шаге рекурсии разбиваются на q = 4 части равной длины, можно схемно реализовать с рекуррентной оценкой сложности Г(4п) 7Г(п) + 662п + 1085. В методе Тоома для q = 4 эффективно производить не полную рекурсию, а при 5 = 3, п — 4s = 64 перейти на оптимизированный вариант метода Карацубы. Сложность оптимизированного варианта метода Тоома для 5 = 4, п = 4s, s 4 оценивается сверху как Апп г ,м 7 662 1085 402,5nlog47- —п —. 3 о Приблизительно это в 4,5 раза лучше неоптимизированного варианта. В частности, Т(1024) 1 279 651, а стандартный (школьный) метод умножения имеет оценку сложности выше шести миллионов. Метод Тоома умножения n-битовых целых двоичных чисел для п = 8s, s 5, в котором множители на каждом шаге рекурсии разбиваются на q = 8 частей равной длины, можно схемно реализовать с рекуррентной оценкой сложности Г(8п) 152» + 5762п + 63589. В методе Тоома для q = 8 эффективно производить не полную рекурсию, а при s = 4, п = 8s = 4 096 перейти на оптимизированный вариант метода Тоома для q = 4. Сложность оптимизированного варианта метода Тоома умножения целых двоичных чисел для q = 8, п = 8s, s 5 оценивается сверху как Т(п) 257,05nlogs15 - 823п - 4542. Это приблизительно в 21 раз лучше неоптимизированного варианта. Во второй главе изучается сложность и глубина схем для арифметики в некоторых башнях конечных полей характеристики два. Методы умножения в конечных полях зависят от типа базисов, используемых для представления элементов поля. Чаще всего используются стандартные полиномиальные базисы, в которых элементы поля размерности п представляются в виде многочленов степени п — 1, операции над которыми выполняются по модулю данного неприводимого многочлена. Очевидные оценки сложности и глубины таких схем равны 0(п2), O(logn). Методом Карацубы можно для тех же базисов построить схемы сложности 0(nlog23). Вопросы практического использования метода Карацубы для умножения в поле GF(2n) рассмотрены, в частности в диссертации К.Паара [36].
Известно (см. [22], [23]), что при использовании стандартных базисов в полях GF(2n) сложность схемы для умножения равна 0(п log п log log п). Для инвертирования в компьютерных вычислениях можно использовать быстрый алгоритм Евклида с оценкой сложности О(п log2 п log log п) (см. [22], [47]). Однако мультипликативная константа в этой оценке велика (несколько сотен), и при актуальных для приложений значениях п стандартный алгоритм Евклида лучше. Кроме того, этот алгоритм затруднительно применить при построении схемы для инвертирования. Известно, что можно построить такую схему сложности 0(n +1 2log2ri), где UJ — экспонента матричного умножения (см. [49]). Но величина мультипликативной константы здесь с трудом поддается оценке, также трудно оценить глубину этой схемы. Можно построить схему для инвертирования сложности 0(nlog2V (log2n)log28/7) и глубины 0(\ogln), где мультипликативные константы сравнительно невелики (см. [19]), но и эта схема при реальных значениях п представляется неэффективной.
Схемы для умножения в башнях псевдомерсенновских полей
При использовании в поле GF(2n) нормального базиса можно построить схему для умножения сложности 0(n2/logn) (см. [1]). Если для инвертирования применить метод [24], основанный на методе Шольца-Брауэра [2], то можно построить схему сложности 0(М (п) logn) = 0(п2) с небольшой мультипликативной константой в оценке, где Мдг(п) — сложность умножения в данном базисе. Для некоторых специальных нормальных базисов (существующих не при всех п) можно построить более эффективные схемы для умножения, и как следствие, для инвертирования. В [1] показано, что для оптимальных нормальных базисов первого типа можно построить схемы для умножения сложности М(п) + 0(п), где М(п) - сложность умножения двоичных многочленов степени п — 1. Для оптимальных нормальных базисов второго типа в [1] указана оценка ЗМ(п)) +у log2 п+0(п) и показано, что если п = тк, т,к пс, С 1/2, (т, к) = 1, то для некоторого нормального базиса сложность умножения равна 0(п(т + к)/logn) = 0(n2 c/logn), откуда следует, что если п — достаточно гладкое число, то для некоторого нормального базиса сложность умножения равна 0(п2 с) при С О, характеризующем гладкость числа п. Во второй главе диссертации построены схемы для умножения и инвертирования в башнях конечных полей вида GF(2n), п = ms. Далее приводятся формулировки результатов при помощи следующих обозначений: L(M(n)), М(п) - сложность схемы для умножения, L(I(n)), 1(п) -сложность схемы для инвертирования, L(S(n)) - сложность схемы для возведения в квадрат, D(M(n)) - глубина схемы для умножения, D(I(n)) -глубина схемы для инвертирования, D(S(n)) - глубина схемы для возведения в квадрат в конечном поле GF(2").
Далее приводятся формулировки некоторых результатов главы при помощи следующих обозначений: GF{q) - конечное поле порядка q, п -произвольное натуральное число, р - простое, M(G) - схемная сложность умножения, D(M(G)) - глубина схемы умножения в поле G, А(р) - сложность сложения, D(A(p)) - глубина схемы сложения , D(M(p)) - глубина схемы умножения в поле в поле GF(p), М(п) - сложность умножения многочленов степени меньшей п над GF(72). Теорема 3.2.1. Умножение элементов поля GF(7Un) может быть выполнено схемой сложности M(GF(7Un)) 13M(OF(72n))+258nA(7) и глубины D{M{GF{7Un))) l\D{A{7)) + D{M(GF(72n))). В частности, при п = 31, M(GF(714-31)) 698 554. Следующая теорема может использоваться для оптимизации сложности алгоритма Дуурсма-Ли эффективнее, чем предыдущая теорема, так как указанная в ней оценка учитывает особенности этого криптоалгоритма. Теорема 3.2.2. Умножение в поле GF(7Un) элемента f, представи-мого многочленом степени 6, на элемент д, представимый многочленом степени 4 с единичным старшим коэффициентом, имеет сложность не выше lOM(GF(72n)) + 176пЛ(7). Глубина схемы, не превосходит 13D(A(7))+D[M(GF(72n))). В частности, при п = 31, сложность умножения не превосходит 557 392, а глубина схемы не превосходит ЗШ(Л(7)) + D(M(7)) — 253. Ухудшив оценку сложности, можно получить оценку для глубины 129. Выбор приведенных выше конкретных примеров мотивируется тем, что порядок поля GF(714 31) приблизительно равен 21000 и является минимально возможным, при котором обеспечивается необходимый уровень криптографической надёжности согласно современным стандартам. В следующей теореме указывается асимптотическая оценка сложности умножения многочленов произвольной степени над GF(72). Теорема 3.3.1. Многочлены степени п— 1 над GF{72) могут быть умножены со сложностью М(п) 6098707 nlog57.
Для случаев, когда характеристика поля является числом Мерсен-на или Ферма, в четвёртой главе диссертации предлагается несколько лучшая реализация арифметики в башнях полей некоторых типов. В отличие от цитированной работы в диссертации рассматривалась не программная, а схемная реализация. Но приведённые результаты (за исключением касающихся глубины) можно интерпретировать и в терминах программной реализации. Сравнения с результатом цитированной работы указаны в тексте четвёртой главы в виде замечаний.
