Схемы для целочисленной арифметики и арифметики конечных полей тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Бурцев, Алексей Анатольевич

• Бурцев, Алексей Анатольевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Бурцев, Алексей Анатольевич

1 О СХЕМАХ УМНОЖЕНИЯ ЦЕЛЫХ ЧИСЕЛ

1.1 Оптимизация метода Карацубы.

1.2 Некоторые частные случаи метода Тоома

2 О СЛОЖНОСТИ СХЕМ ДЛЯ АРИФМЕТИКИ В НЕКОТОРЫХ БАШНЯХ КОНЕЧНЫХ ПОЛЕЙ

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

2.2 О схемах для умножения и инвертирования в композитных полях GF{2п).

3 О СХЕМАХ УМНОЖЕНИЯ МНОГОЧЛЕНОВ В НЕКОТОРЫХ КОНЕЧНЫХ ПОЛЯХ

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

3.2 Схемы для умножения в поле GF(7Un)

3.3 Некоторые эффективные схемы умножения многочленов над полем GF{72).

4 О СХЕМАХ ДЛЯ АРИФМЕТИКИ В КОМПОЗИТНЫХ ПОЛЯХ БОЛЬШОЙ ХАРАКТЕРИСТИКИ

4.1 Схемная сложность операций в псевдомерсенновских полях

4.2 Схемы для умножения в башнях псевдомерсенновских полей

4.3 Умножение в полях GF(p2k), р = 216 + 1.

4.4 О глубине инвертирования в поле GF(pu), р = 216 +

4.5 Умножение и инвертирование в поле GF(p2n).

Введение диссертации (часть автореферата) на тему «Схемы для целочисленной арифметики и арифметики конечных полей»

В данной работе изучается реализация арифметических операций в некоторых конечных полях схемами из функциональных элементов.

Конечные поля возникли в исследованиях Гаусса [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, оценивается сверху как nlog2 3 - 52п + 4,5.

27

Приблизительно это вдвое лучше неоптимизированного варианта.

Показано, что метод Тоома умножения n-битовых чисел для п = 4s, s > 4, в котором множители на каждом шаге рекурсии разбиваются на q = 4 части равной длины, можно схемно реализовать с рекуррентной оценкой сложности

Т(4п) < 7Г(п) + 662п + 1085.

В методе Тоома для q = 4 эффективно производить не полную рекурсию, а при 5 = 3, п — 4s = 64 перейти на оптимизированный вариант метода

Карацубы. Сложность оптимизированного варианта метода Тоома для 5 = 4)n = 4s,s>4 оценивается сверху как г w 7 662 1085

402,5ng4 - — п--—.

3 6

Приблизительно это в 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,05nlog815 - 823п - 4542.

Это приблизительно в 21 раз лучше неоптимизированного варианта.

Во второй главе изучается сложность и глубина схем для арифметики в некоторых башнях конечных полей характеристики два. Методы умножения в конечных полях зависят от типа базисов, используемых для представления элементов поля. Чаще всего используются стандартные полиномиальные базисы, в которых элементы поля размерности п представляются в виде многочленов степени п — 1, операции над которыми выполняются по модулю данного неприводимого многочлена. Очевидные оценки сложности и глубины таких схем равны 0(п2), O(logn). Методом Карацубы можно для тех же базисов построить схемы сложности 0(nlog23). Вопросы практического использования метода Карацубы для умножения в поле GF(2n) рассмотрены, в частности в диссертации К.Паара [36].

Известно (см. [22], [23]), что при использовании стандартных базисов в полях GF(2") сложность схемы для умножения равна 0(п log п log log n). Для инвертирования в компьютерных вычислениях можно использовать быстрый алгоритм Евклида с оценкой сложности 0(nlog2 п log log п) (см. [22], [47]). Однако мультипликативная константа в этой оценке велика (несколько сотен), и при актуальных для приложений значениях п стандартный алгоритм Евклида лучше. Кроме того, этот алгоритм затруднительно применить при построении схемы для инвертирования. Известно, что можно построить такую схему сложности log2 п), где и — экспонента матричного умножения (см. [49]). Но величина мультипликативной константы здесь с трудом поддается оценке, также трудно оценить глубину этой схемы. Можно построить схему для инвертирования сложности 0(nlog2v^(log2n)log28/7) и глубины 0(\ogln), где мультипликативные константы сравнительно невелики (см. [19]), но и эта схема при реальных значениях п представляется неэффективной.

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

Во второй главе диссертации построены схемы для умножения и инвертирования в башнях конечных полей вида GF{2"), п = 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 при любом т для п = ms и s > s£ можно указать в поле GF(2") базис, для которого можно построить схему умножения сложности M(ms) < п1+£и схему инвертирования сложности I(ms) < п1+е.

Результаты этой теоремы в специальном случае п = 2 • 3fc усиливает следующая

Теорема 2.1.2. При п = 2 • 3fc в поле GF(2") можно указать некоторый базис, для которого можно построить схемы для умножения сложности М(п) = n(log3n)(loS2log3n^2+0^' и схемы для инвертирования сложности 1(п) = 0(М(п)).

В работе [5] были указаны рекуррентные верхние оценки сложности и глубины схем для умножения и деления в некоторых базисах полей GF(24™), GF(26™) при нечетном п и п, взаимно простом с б, соответственно. Во второй главе диссертации получены подобные оценки для схем в некоторых нормальных базисах тех же полей, а также для схем в некоторых базисах полей GF(28п) при нечетном п и некоторых других композитных полей. Далее приводятся формулировки полученных результатов.

Теорема 2.2.1. Для расширения GF((2™)4) поля GF(2n) при нечетном п и выборе в поле GF(24) нормального базиса а, а2, а4, а8}, 1 + а + а2 + о? + а4 = О, и произвольного нормального базиса в поле GF(2"), можно построить схемы для умножения и инвертирования со следующими рекуррентными оценками сложности и глубины

L{M{An)) < \ЩМ{п)) + 21 п, D{M(4n)) < D(M(n)) + 3,

L(/(4n)) < L(/(n)) + 19L(M(n)) + 13n, D(I{An)) < 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((2")6) поля GF(2n), где п взаимно просто с б, при выборе в подполе GF(26) нормального базиса of, а2, а\ а8, а16, a32}, 1 + а + а4 + а5 + а6 = О, и произвольного нормального базиса в поле GF(2"), можно построить для умножения и инвертирования схемы со следующими рекуррентными оценками сложности и глубины

L(M(6n)) < 21 L(M(n)) + 60n, D(M(6n)) < D{M(n)) + 4,

L(I(Qn)) < L(I(n)) + 42L{M(n)) + 65n, D(I(6n)) = 4 D(M(n)) + 4 + max{D(/(n)), 4}.

Теорема 2.2.3. В башне расширений GF(((271)4)2) поля GF(2П) при нечетном п справедливы следующие рекуррентные оценки сложности и глубины умножения и возведения в квадрат:

ЦМ(8п)) < 27Ь(М{п)) + 80п, D(M(8n)) < D{M{n)) + 7,

L(S(8n)) < 10п + 4L(S(n)), D{S{8n)) < 5 + D(S(4n)).

Если в поле GF(2n) выбрать нормальный базис, то для инвертирования справедливы следующие рекуррентные оценки сложности и глубины:

L(I(8n)) < L(I(n)) + 45L(M(n)) + 101та, D(I(8n)) < 4D{M(n)) + 8 + max{D(/(ra)), 6}.

Теорема 2.2.4. В башне расширений GF(((2п)4)2) поля GF(2") при нечетном п и выборе нормального базиса в поле GF(2n) справедливы следующие рекуррентные оценки слоэ/сности и глубины умножения и инвертирования:

Ь(М(8п)) < Ш{М{п)) + 82п, D(M(8n)) < D{M(n)) + 5,

L(/(8n)) < L(I{n)) + 52L(M(n)) + 88n, D(I(8n)) < 4D(M(n)) + 6 + max{£>(/(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, п -произвольное натуральное число, р - простое, М(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))+258пА(7) и глубины D(M(GF(714п))) < UD(A(7)) + D{M(GF(72п))). В частности, при п = 31, M{GF(714'31)) < 698 554.

Следующая теорема может использоваться для оптимизации сложности алгоритма Дуурсма-Ли эффективнее, чем предыдущая теорема, так как указанная в ней оценка учитывает особенности этого криптоалгоритма.

Теорема 3.2.2. Умножение в поле GF(7Un) элемента f, представи-мого многочленом степени 6, на элемент д, представимый многочленом степени 4 с единичным старшим коэффициентом, имеет сложность не выше 10M(GF(72n)) + 176пЛ(7). Глубина схемы не превосходит l3D(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(q2k) имеет рекуррентную верхнюю оценку сложности

M(q2k) < 3kM(q) + 5(3* - 2k)A(q) + ^(3* - 1 )М(а0, q), где многочлен х2 — а0 неприводим над GF(q), а0 е GF(q). Умножение в башне полей GF{qz ) имеет рекуррентную верхнюю оценку сложности

M{q3k) < 6kM(q) + 5(6fc - 3k)A{q) + f (6* - l)M(a0,q), 5 где многочлен хь — a0 неприводим над GF(q), а0 € GF(q).

Для случаев, когда характеристика поля является числом Мерсен-на или Ферма, в четвёртой главе диссертации предлагается несколько лучшая реализация арифметики в башнях полей некоторых типов. В отличие от цитированной работы в диссертации рассматривалась не программная, а схемная реализация. Но приведённые результаты (за исключением касающихся глубины) можно интерпретировать и в терминах программной реализации. Сравнения с результатом цитированной работы указаны в тексте четвёртой главы в виде замечаний.

Далее приводятся формулировки полученных результатов с использованием следующих обозначений: Wk - примитивный корень к-ой степени из единицы в GF(q), е = w3; n, ki - неотрицательные целые, р -простое.

Теорема 4.2.1. Умножение в башне полей GF(q3), q = рп, имеет оценку сложности

M(q3) < 5M(q) + 21 A(q) + 6М(2, q)+

2(М(4, q) + M(l/2, q) + М (1/6, q)) + 2 М(а0,р) в предположении, что q — 1 кратно 3, двучлены хп — а0 и я3™ ~ ао неприводимы над GF(p).

Теорема 4.2.2. Умножение в башне полей GF(q4), q = рп, имеет оценку сложности

M{q4) < 7M(q) + 6М(ш3, q) + 54A(q) + 6M(l/6, q) + 3M(a0,p) в предположении, что q — 1 кратно 12 и многочлены х11 -а0 и ж4п — а0 неприводимы над GF{p).

Теорема 4.2.3. При q = pn,p = 213 - 1, п = 2fc° ■ 3fel • 5*2 ■ 7кз ■ 13к\ ко = 0,1, умножение в башне полей GF(q5) имеет оценку сложности M(q5) < 77A(q) + UM{q).

Теорема 4.2.4. Умножение в башне полей GF(q6), q = рп, имеет оценку сложности

M{q6) < 12M{q) + 121 A{q) + 6М{а0,р) + M(l/12, q)+

2(М(—3/2, q) + M(£-^:q) + М (-1/8, q) + q))+ 2

2{M{ua, q) + M(-3w4/2, g) + ?))+ 2

9) + М(-Ш4/8,9) + g) в предположении, что q — 1 кратно 12, многочлены xn — a0 и x6n — a0 неприводимы над GF(p).

Теорема 4.2.5. Умножение в поле GF(q7), q = рп, р = 213 — 1, имеет оценку сложности M(q7) < 13M(q)+ 344A(q)+ 6А(р) в предположении, что п = 2*° • • 5fc2 • 7ki ■ 13*4, kQ = 0,1.

Теорема 4.2.6. Умножение в поле GF(q9),q = pn,p = 217 — 1, имеет оценку сложности M(q9) < 17M(q)+ 57SA(q) +6А(р) в предположении, что п = 2*° • 3kl ■ 5к2 ■ 17кз, к0 = 0,1.

Теорема 4.2.7. Умножение в поле GF(q13), q = рп, р = 213 — 1 имеет оценку сложности М(д13) < 26M(q) + 1026A(q) + 12А(р) в предположении, что п = 2ko- З*1 ■ 5к2 ■ 7кз ■ \Зк\ к0 = 0,1.

Теорема 4.2.8. Умножение в поле GF(qu), q — рп, р = 213 — 1 имеет оценку сложности M(qu) < 26M(q) + 1032Л(д) + 13А(р) в предположении, что п = 2ко ■ 3fcl • 5fc2 • 7кз ■ 13к\ к0 = 0,1.

Теорема 4.2.9. Умножение в поле GF(qls), q = рп, р = 217 — 1, имеет оценку сложности M(q18) < 35M(q) + 1825A(q) + 17А(р) в предположении, что п = 2ко • 3kl • 5fe2 • 17кз, к0 = 0,1.

Теоремы 4.3.2-4. Умножение в поле GF(q2k), к < 4, q = рп, п — 2т, р = 216 + 1, имеет оценки сложности

M{q4) < 7М(д) + 59A{q) + 3M(3,p),

M(qs) < 15M{q) + 193A(q) + 7М(3,р), M(q1&) < 3lM(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) = maх{М(С, q) : С = 2s, 5 = 1,2,3,. }, D{M{2s, q)) = max{D{M{C, qj) : С = 2s, s = 1,2,3,. }.

Теорема 4.4.1. В поле GF(p2m),p = 216 + 1, существует схема для инвертирования, у которой сложность рекуррентно оценивается как

12т = /2т: + 652т-1 + 12М2т-1 + 15Л2т-1 + 5М(3,р) + М(б,р)+

2т-1-1)М(2,р), где Ik есть сокращение для I(pk), и аналогично определяются Мь, S^, А/-. Глубина этой схемы рекуррентно оценивается как

D{I2m) = D(I2m-1) + 2D(M2rn-l) + D(S2m-1) + 2{D{A{p)) + D(M(3,p)).

Теорема 4.4.2. Для инвертирования в поле GF(q16), q = рп, п — 2т, р = 216 + 1, может быть построена схема сложности

I(q) + 410M(g) + 24 S(q) + 2173 A(q) + 735M(2S, q) + 119M(3,p) + M(6,p).

Если D(M(q)) + 2{D(A(p)) + D(M(3,p))) < D(I(q)), то глубина этой схемы не больше

D(I(q)) + 4D(M(q)) + D(S(q)) +19 D{A(p)) + 10D{M(2s,p)) + 3D(M{3, p)).

В противном случае она не превосходит

5 D(M(q)) + D(S(q)) + 2 lD(A{p)) + 10L>(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) < 1462А(р) + 243М(р).

Теорема 4.5.2. Инвертирование в поле GF(qb), где q = р2п, р — 1 (mod 10п), может быть выполнено схемой, имеющей оценку сложности

I(q5) < I(q) + 28M{q) + U3nA(p) + (16n + 2)M(aQ,p) + +6n{M(u5,p) + M(u2,p) + M{ulp) + МЦ,р)), aQ 6 GF(p).

Теорема 4.5.3. Инвертирование в поле GF(pWn), р = 1 (mod 10n), может быть выполнено схемой, имеющей оценку сложности

I(pWn) < I(pn) + UbnA(p) + 1Ш{рп) + 34М(а0,р)+ +6п(М(и5,р) + М(ш1,р) + М{ш1,р) + М(Ч4,р)), а0 е GF(p).

Теорема 4.5.4. Умножение в поле GF(p2n) для р = 2k — 1 при п < имеющем только простые нечетные делители, делящие р — 1, может быть выполнено с помощью схемы, имеющей оценку сложности

М(р2п) < (15 • 2т~2 + 9(2т1(т - 2) + 1 ))М(р) + ((12т + 7)2т~1 + 9(2т1(т - 2) + 1 ))А(р), где 2тх < 2п - 2 < 2т, т < к. Если 2п - 2 = 2т, т < к, тогда к указанной оценке сложности прибавляется М(р2) + А(р2).

Указанными во введении обозначениями будем пользоваться в дальнейшем изложении.

Список литературы диссертационного исследования кандидат физико-математических наук Бурцев, Алексей Анатольевич, 2007 год

1. Болотов А.А., Гашков С.Б. О быстром умножении в нормальных базисах конечных полей.Дискретная математика, т.13, N 3 (2001). С. 3-31.

2. Кнут Д. Искусство программирования, т.2, 2-е изд., 2000.

3. Гашков С.Б. Замечания о быстром умножении многочленов, преобразовании Фурье и Хартли.Дискретная математика, т.12, N 3 (2000). С. 124-153.

4. Лидл Р., Нидеррейтер X. Конечные поля. Мир, Москва, 1988.

5. Гашков С. Б., Хохлов Р. А. О глубине логических схем для операций в полях GF{2").Чебышевский сборник, т. 4, вып. 4(8), 2003. С. 59-71.

6. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Элементарное введение в эллиптическую криптографию: алгебраические и алгоритмические основы и протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006.

7. Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах. // ДАН СССР. 1962. - Т. 145(2). - С. 293-294.

8. Тоом А.Л. О сложности схемы из функциональных элементов, реализующей умножение целых чисел // ДАН СССР. — 1963. — Т. 150. С. 496-498.

9. Шеннон К.Э., Избранные работы по теории информации и кибернетике, ИЛ, Москва (1963).

10. Лупанов О. Б., Асимптотические оценки сложности управляющих систем. Изд. МГУ, Москва, 1984.

11. Barreto P.S.M.L., Galbraith S., О hEigeartaigh C. and Scott M. Efficient pairing computation on supersingular abelian varieties Cryptology ePrint Archive, Report 2004/375. http://eprint.iacr.org/2004/375

12. Duursma I. and Lee H.-S. Tate pairing implementation for hyperelliptic curves y2 = xv x + d. Asiacrypt-2003, LNCS 2894(2003), 111-123.

13. Duursma I. and Lee H.-S. Tate pairing implementation for tripartite key agreement. Cryptology ePrint Archive, Report 2003/053. http://eprint.iacr.org/2003/053

14. Kwon S. Efficient Tate pairing computation for supersingular elliptic curves over binary fields. Cryptology ePrint Archive, Report 2004/303. http://eprint.iacr.org/2004/303.

15. Eunjeong Lee, Huang-Sook Lee and Yoonjin Lee. Fast computation of Tate pairing on general divisors for hyperelliptic curves of genus 3. Cryptology ePrint Archive, Report 2006/125. http://eprint.iacr.org/2006/125

16. Kerins Т., Marname W.P., Popovici E.M., and Barreto P.S.L.M. Efficient hardware for Tate pairing calculation in characteristic three. CHES-2005.

17. Page D., Smart N.P. Hardware implementation of finite fields of characteristic three, CHES-2002, LNCS, 2002.

18. Bailey D.V., Paar C. Efficient arithmetic in finite field extensions with application in elliptic curve cryptography. J. of Cryptology 14:3(2001), 156- 173.

19. D. Jungnickel, Finite fields. Structure and arithmetic. Wissenschaftsverlag, Mannheim, Leipzig, Wien, Zurich, 1993.

20. I. Blake, G. Seroussi, N. Smart Elliptic curves in cryptography. Cambridge University Press, 1999.

21. C. Paar, Effective VLSI architectures for bit paralel computation in Galois fields, Ph. D. Thesis, Universitat GH Essen, Germany, 1994.

22. J.L. Massey, J.K. Omura, Apparatus for finite fields computation, US patent 4587627, 1986.

23. R.C. Mullin, I.M. Onyszchuk, S.A. Vanstone, R.M Wilson, "Optimal normal bases in GF(pn)", Discrete Applied Mathematics, vol. 22, pp. 149-161, 1988/89.

24. Itoh Т., Tsujii S., A fast algorithm for computing multiplicative inverses in GF(2n) using normal basis. // Inform, and Сотр. — 1988. — 78. — P. 171-177.

25. Moore Е.Н.,Л double-infinite system of simple groups Bull. New York Math.Soc. 3 (1983), 73-78.

26. Dickson L.E., Proof of the existence of the Galois field of order pr, Bull.Amer.Math.Soc., 6 (1900) 203-204.

27. Menezes A., Elliptic curve public key cryptosystems, Cluwer Academic Publishers (1993).

28. Bailey D., Paar C., Optimal extension fields for fast arithmetic in public-key algoritms , CRYPTO-98, (1998), 472-485.

29. Paar C., Fan J.L. Efficient inversion in tower fields of characteristic two, ISIT, Ulm, Germany, 1997.

30. Blake I.,Seroussi G., Smart N. Advances in elliptic curve cryptograhy, Cambridge University Press, 2005.

31. Granger R., Page D., Starn M. Hardware and software normal basis arithmetic for pairing based cryptography in characteristic three. IEEE Trans, on Сотр. v.54, No 7 (2005), 852-860.

32. J.E. Savage, The complexity of computing. Wiley-Intersicence publication, 2nd ed., 1987.

33. A.Reyhani-Masoleh, M.A. Hasan, "On effective normal basis multiplication", IndiaCRYPT,(2000).

34. Dickson L.E., Proof of the existence of the Galois field of order pr.

35. Menezes A., Application of finite fields, Cluwer Academic Publishers (1993).

36. Jungnickel D., Finite fields. Structure and arithmetic, Wissenschaftsverlag, Mannheim, Leipzig, Wien, Zurich (1993).

37. Diffie W., Hellman M., New directions in cryptography, IEEE Trans. Inform. Theory, IT-22, (1976).

38. Coppersmith D., Fast evaluation of logarithms infields of characteristic two, IEEE Trans.Inform. Theory, IT30, 4,(1984), 587-594.Публикации автора по теме диссертации

39. Бурцев А. А., Гашков И. Б., Гашков С. Б. О сложности булевых схем для арифметики в некоторых башнях конечных полей // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2006. №5. С. 10 16.

40. Бурцев А. А., Гашков С. Б. О схемах для арифметики в композитных полях большой характеристики // Чебышевский сборник. Том 7. Выпуск 2 (2006). С. 186 204.

41. Бурцев А. А. О схемах для умножения и инвертирования в композитных полях // Чебышевский сборник. Том 7. Выпуск 2 (2006). С. 172 185.

42. Бурцев А. А. О булевых схемах умножения в конечных полях нечётной характеристики. // Материалы VI молодёжной научной школы по дискретной математике и её приложениям (Москва, 16-21 апреля 2007 г.) Часть I. С. 13 16.

43. Бурцев А. А. О булевых схемах для арифметики в псевдомерсеннов-ских полях. // Материалы IX Международного научного семинара «Дискретная математика и её приложения». (Москва, 18-23 июня 2007 г.) С. 66 68.