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

На правах рукописи

Бурцев Алексей Анатольевич

СХЕМЫ ДЛЯ ЦЕЛОЧИСЛЕННОЙ АРИФМЕТИКИ И АРИФМЕТИКИ КОНЕЧНЫХ ПОЛЕЙ

01 01 09 - Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Нижний Новгород - 2007

003176442

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета имени М. В Ломоносова

Научный руководитель. доктор физико-математических наук,

профессор С. Б Гашков

Официальные оппоненты, доктор физико-математических наук,

профессор В М Галкин,

кандидат физико-математических наук, доцент Н Ю Золотых

Ведущая организация Московский энергетический институт

(МЭИ).

Защита диссертации состоится 13 декабря 2007 г. в 14 ч. 40 мин. на заседании диссертационного совета Д 212 166.06 в Нижегородском государственном университете имени Н. И. Лобачевского по адресу: 603950, Российская Федерация, г. Нижний Новгород, проспект Гагарина, 23, корпус 2, конференц-зал ННГУ.

С диссертацией можно ознакомиться в фундаментальной библиотеке Нижегородского государственного университета имени Н. И. Лобачевского С текстом автореферата можно ознакомиться на официальном сайте ННГУ имени Н. И. Лобачевского http //www.unn ru в разделе «Наука и инновации» - «Объявления о защите диссертаций» - «Физико-математические науки»

Автореферат разослан « 8 » « ноября » 2007 г.

Ученый секретарь диссертационного совета Д 212 166.06

кандидат физико-математических наук, ^

доцент ^Ои В И Лукьянов

Общая характеристика работы

Актуальность темы

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

Конечные поля возникли в исследованиях Гаусса и Галуа Современное изложение теории появилось в работах Мура и Диксона Схемы для арифметических операций в конечных полях используются в криптографии, кодировании, цифровой передаче сигналов и других областях В указанных применениях в основном использовались поля сравнительно малой размерности (п < 32), но с развитием криптографии с открытым ключом поля большой размерности (п > 1000) нашли применение в криптографических протоколах, основанных на предположении о трудности задачи дискретного логарифмирования1'2 Благодаря развитию криптографии на эллиптических кривых появилась возможность использовать поля размерности порядка двухсот3,4.

Теория сложности схем для булевых функций была развита в работах К Э Шеннона и О Б Лупанова Схемы обычно строятся из элементов, реализующих двухместные булевы функции Под сложностью схемы понимается количество составляющих схему функциональных элементов Понятие схемной сложности по существу совпадает с понятием битовой сложности При конструировании логических схем стремятся уменьшить не только их сложность, но и глубину — максимальное число элементов в любой цепи, соединяющей входы схемы с ее выходами, так как практически важно увеличить быстродействие схемы Операции сложения и вычитания просты, поэтому наибольший интерес представляет умножение и инвертирование ненулевых элементов (инвертирование есть нахождение мультипликативного обратного) Деление сводится к инвертированию и умножению Умножение элементов конечного поля в стандартном базисе сводится к умножению представляющих эти элементы многочленов по модулю некоторого неприводимого многочлена, поэтому существенное значение имеет разработка эффективных схем для умножения многочленов над конечными полями

'Diffie W , Hellman М , New directions in cryptography, IEEE Trans Inform Theory, IT-22, (1976)

2Coppersmith D, Fast evaluation of logarithms m fields of characteristic two, IEEE Trans Inform Theory, IT30, 4,(1984), 587-594

3МШег V , Uses elliptic curves m cryptography , CRYPTO-85, (1986), 417-426

•■Koblitz N , Elliptic curve cryptosystems , Mathematics of computation, 48 (1987), 203-209

Цель работы

Получение эффективных верхних оценок сложности и глубины схем из двухвходовых булевых элементов для арифметики в некоторых башнях конечных полей, а также для умножения многочленов в некоторых конечных полях

Основные методы исследования

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

Научная новизна

Результаты диссертации являются новыми и состоят в следующем

1 Показано, что для любых положительного е и натурального тп > 1 для любого п = тп3, где натуральное в > можно указать в поле 2") базис и построить схему умножения в нем сложности, не превосходящей п1+£^2 и схему инвертирования сложности, не превосходящей п1+е.

2 Показано, что при п = 2 • Зк в поле можно указать базис, для которого можно построить схему для умножения сложности М(тг) = п(к^3 п)(1о&1о8зп)/2+0(1) и схему дЛЯ инвертирования сложности 0(М(п))

3 Получены новые эффективные рекуррентные верхние оценки сложности и глубины схем из функциональных элементов для умножения и инвертирования в некоторых нормальных базисах полей С>Р(24"), др(28п), при нечетном пип, взаимно простом с 6, соответственно

4 Построены новые эффективные схемы для умножения в полях вида

714п)) НОД(п, 14) = 1. Построены новые эффективные схемы для умножения многочленов над

5 Получены новые эффективные рекуррентные верхние оценки слож-

ности умножения в некоторых башнях конечных полей большой

характеристики

6 Получены новые эффективные рекуррентные верхние оценки сложности и глубины умножения и инвертирования в полях видаС/^р2*), р = 216 + 1

Теоретическая и практическая ценность

Работа носит теоретический характер Построенная в ней схемная реализация арифметики в конечных полях может найти применение в кодировании, криптографии, цифровой обработке сигналов и других областях, а также может быть использована для программной реализации арифметических операций в конечных полях в компьютерной алгебре

Апробация результатов

Результаты диссертации докладывались на научной конференции «Ломоносовские чтения» в Московском государственном университете имени М В Ломоносова (механико-математический факультет, кафедра дискретной математики) в апреле 2007 г., на научной конференции «Ломоносовские чтения» в Московском государственном университете имени М В Ломоносова (механико-математический факультет, кафедра дискретной математики) в апреле 2006 г, на VI молодежной научной школе-семинаре «Дискретная математика и ее приложения» (Москва, Институт прикладной математики им М.В Келдыша РАН) в апреле 2007 г, на IX Международном научном семинаре «Дискретная математика и ее приложения» (Московский государственный университет имени М В Ломоносова, механико-математический факультет) в июне 2007 г, на Нижегородском городском научном семинаре «Дискретная математика и ее приложения» (Нижегородский государственный университет имени Н И Лобачевского, факультет ВМК, кафедра математической логики и высшей алгебры) в октябре 2007 г

Публикации

Основное содержание диссертации опубликовано в 5 работах [1-5], список которых приведен в конце автореферата Работы [1-2] написаны в соавторстве Автору диссертации принадлежат доказательства всех основных результатов В работах [3-5] соавторов нет Работы [1-3] опубликованы в журналах, рекомендованных ВАК для публикаций диссертационных материалов

Структура и объем работы

Диссертация состоит из введения, четырех глав и списка литературы Полный объем диссертации составляет 128 страниц Список литературы содержит 58 наименований

Краткое содержание диссертации

Во введении излагается история вопроса, формулируются постановка задачи и основные цели работы, кратко описывается ее содержание, а также вводятся основные обозначения

Первая глава служит предисловием к основной тематике и посвящена оптимизации метода Карацубы5 и некоторых случаев метода Тоо-ма6'7 для умножения n-битовых целых чисел с целью получения эффективных числовых оценок схемной сложности умножения для реально используемых на практике диапазонов изменения п Методы синтеза схем для умножения целых чисел с некоторыми изменениями могут быть перенесены на умножение многочленов над конечными полями, что в свою очередь может быть использовано для эффективного схемного умножения элементов конечных полей

Показано, что метод Карацубы умножения n-битовых чисел можно схемно реализовать с рекуррентной оценкой сложности

Т(2п) < 3Т(п) + 52п - 9.

Этот метод эффективнее школьного метода для всех п > 16 На каждом шаге рекурсии в нем n-битовые сомножители эффективно разбивать на блоки длины [|] и |JJ бит Сложность оптимизированного варианта метода Карацубы для п = 2s, s > 4, оценивается сверху как

п1о&г3 — 52га + 4,5

27

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

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

Т(4га) < 7Т{п) + 662п + 1085

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

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

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

Сложность оптимизированного варианта метода Тоома для п — 4s, s > 4, оценивается сверху как

г 1ог 7 662 1085 402,5п 54 - — п--—

Приблизительно это в 4,5 раза лучше неоптимизированного варианта В частности, Т(1024) < 1 279 651, а стандартный (школьный) метод умножения имеет оценку сложности выше шести миллионов

Метод Тоома для п = 8s, s > 5, можно схемно реализовать с рекуррентной оценкой сложности Т(8п) < 15Т(п)+5762п + 63589 Сложность оптимизированного варианта метода Тоома для п = 8s, s > 5, оценивается сверху как 257,05nlog»15 — 823п — 4542 Это приблизительно в 21 раз лучше неоптимизированного варианта

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

0(ni°g23) Вопросы практического использования метода Карацубы для умножения в поле GF(2") рассмотрены, в частности, в диссертации К Паара8. Известно9,10, что при использовании стандартных базисов в полях GF{2") сложность схемы для умножения равна О(n log п log log n) Для инвертирования в компьютерных вычислениях можно использовать быстрый алгоритм Евклидй,9 с оценкой сложности 0(п log2 n log logn) Однако мультипликативная константа в этой оценке велика (несколько сотен), и при актуальных для приложений значениях п стандартный алгоритм Евклида лучше Кроме того, этот алгоритм затруднительно применить при построении схемы для инвертирования

Во второй главе диссертации построены схемы для умножения и инвертирования в башнях конечных полей вида GF{2"), п = ms Далее приводятся формулировки результатов при помощи следующих обозначений L(M(n)), М(п) - сложность схемы для умножения, L(I(n)),

8C Paar, Effective VLSI architectures for bit paralel computation m Galois fields, Ph D Thesis, Universität GH Essen, Germany, 1994

9von zur Gathen J , Gerhard J Modern computer algebra Cambridge University Press, 1999 '"Schonhage A Schnelle Multiplication von Polynomen ueber Koerpern der Charakteristik 2 Acta Informática (1977), vol 7, 395-398

I(n) - сложность схемы для инвертирования, L(S(n)) - сложность схемы для возведения в квадрат, D(M(n)) - глубина схемы для умножения, D{I{n)) - глубина схемы для инвертирования, D(S(n)) - глубина схемы для возведения в квадрат в конечном поле GF{2n).

Теорема 2.1.1. Для любого е > 0 при любом тп для п = ms и s > se можно указать в поле GF(2") базис, для которого можно построить схему умножения сложности М{т") < п1+£/2, и схему инвертирования сложности 1(тп3) < п1+е

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

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

В работе11 были указаны рекуррентные верхние оценки сложности и глубины схем для умножения и деления в некоторых базисах полей GF( 24n), GF( 26") при нечетном nun, взаимно простом с 6, соответственно Во второй главе диссертации получены подобные оценки для схем в некоторых нормальных базисах тех же полей, а также для схем в некоторых базисах полей GF(28п) при нечетном п и некоторых других композитных полей. Далее приводятся формулировки полученных результатов (теоремы 2.2.1 - 2.2.4).

Для расширения GF((2")4) поля GF(2n) при нечетном п и выборе в поле GF(24) нормального базиса

{а, а2, а4, а8}, 1 + а + а2 + а3 + а4 = О,

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

L(M(4n)) < 10L(M(n)) + 21 n, D(M(An)) < D(M(n)) + 3,

L(I(4ri)) < L(I(n)) + 19L{M(n)) + 13n, D(I(4n)) < 3D(M(n)) + 2 + max{£>(/(n)), 2} Можно также построить схемы для инвертирования с оценками

L(I(4n)) < L(I(n)) + 18L(M(n)) + 15n,

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

Я(1(4п)) < 3£>(М(п)) + 2 + тах{П(1(п)), 3}

Для расширения 2")6) поля <3^(2"), г<?е п взаимно просто с 6, при выборе в подполе СР(26) нормального базиса

{а, а2, а4, а8, а16, а32}, 1 + а + а4 + а5 + а6 = О,

и произвольного нормального базиса в поле можно построить

для умножения и инвертирования схемы со следующими рекуррентными оценками сложности и глубины

1(М(6п)) < 21£(М(п)) + бОп, £>(М(6п)) < Я(М(п)) + 4,

Щ(6п)) < Ц1(п)) + 42Ь(М(п)) + 65тг, ОДбп)) = 4£)(М(п)) + 4 + тах{£(/(п)),4}

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

ЦМ(8п)) < 27Ь(М{п)) + 80п, Л(М(8п)) < £(М(тг)) + 7,

¿(5(8п)) < 10п + 4ВДп)), Д(£(8п)) < 5 + /?(5(4п))

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

Ц1(8п)) < Ь(1(п)) + 45Ь(М(п)) + 101п,

Л(1(8п)) < 4£>(М(п)) + 8 + шах{£>(/(п)), 6}

В башне расширений С?.Р(((2п)4)2) поля 2") при нечетном тг можно выбрать базис так, что справедливы следующие рекуррентные оценки сложности и глубины умножения и инвертирования.

Ь(М(8п)) < 30ДМ(п)) + 82п, £>(М(8тг)) < ДМ(п)) + 5,

адвп)) < ВДп)) + 52Ь(М(п)) + 88п, ОД8п)) < 4£>(М(п)) + б + тах(ОДп)), 2}

В третьей главе изучаются схемы для умножения многочленов в некоторых конечных полях малой нечетной характеристики и схемы для умножения в этих полях. Особое внимание уделяется полям GF(714п), НОД(п, 14) = 1, имеющим приложения в криптографии на эллиптических кривых В ней обычно применяются кривые или над простыми полями, или над полями характеристики два Последние наиболее удобны для реализации в виде электронных схем12,13,14. В связи с открытием возможности использования в криптографии так называемых билинейных спариваний (введенных в работах Вейля, Тейта и Лихтенбаума), для конструирования новых криптоалгоритмов начали применяться эллиптические и гиперэллиптические кривые над полями характеристики три15,16. Как следствие, появился интерес к реализации арифметики в этих и других полях нечетной характеристики17'18'19 В частности, поля GF(p2pn), где НОД(п, 2р) = 1, р = 3 (mod 4), появляются в алгоритме Дуурсма-Ли20, а поля GF(714") - в работе21, но вопросы эффективной реализации арифметики в этих полях там не затрагиваются

Далее приводятся формулировки некоторых результатов главы, используются следующие обозначения GF(q) - конечное поле порядка q, п - произвольное натуральное число, р - простое, M(G) - схемная сложность умножения, D(M(G)) - глубина схемы умножения в поле G, А{р) -сложность сложения, D{A(p)) - глубина схемы сложения , D(M(p)) -глубина схемы умножения в поле в поле GF(p), М(п) - сложность умножения многочленов степени меньшей п над GF{72).

12I Blake, G Seroussi, N Smart Elliptic curves m cryptography Cambridge University Press, 1999

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

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

15Barreto Р S L М , Kim Н Y , Lynn В , Scott М Efficient algorithms for pairing-based cryptosystems Crypto-2002, LNCS 2442(2002), 354-368

l6Barreto PSML, Galbraith S, OhEigeartaigh С and Scott M Efficient pairing computation on supersingular abelian varieties Cryptology ePnnt Archive, Report 2004/375 http //epnnt lacr org/2004/375

17Kenns T , Marname W P, Popovici E M , and Barreto P S L M Efficient hardware for Tate pairing calculation ш characteristic three CHES-2005

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

"Granger R, Page D , Stam M Hardware and software normal basis arithmetic for pairing based cryptography in characteristic three IEEE Trans on Comp v 54, No 7 (2005), 852-860

MDuursma I and Lee H -S Tate pairing implementation for hyperelliptic curves у2 = xp - x + d Asiacrypt-2003, LNCS 2894(2003), 111-123

21Eunjeong Lee, Huang-Sook Lee and Yoonjm Lee Fast computation of Tate pairing on general divisors for hyperelliptic curves of genus 3 Cryptology ePrint Archive, Report 2006/125 http //epnnt lacr org/2006/125

Теорема 3.2.1. Умножение элементов поля GF(7.14") может быть выполнено схемой сложности M(GF(714n)) < 13M(GF(72n))+258nA(7) « глубины D(M(GF(714"))) < 11£>(Л(7)) + D(M(GF(72"))). В частности, при п = 31, М(ОР(71431)) < 698 554

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

Теорема 3.2.2. Умножение в поле GF(714") элемента /, предстпа-вимого многочленом степени 6 над полем GF(72n), на элемент g, пред-ставимый многочленом степени 4 с единичным старшим коэффициентом над полем GF(72"), имеет сложность не выше 10M(GF(72")) + ï76nA(7) Глубина схемы не превосходит UD{A{7)) + D(M(GF(72"))) В частности, при п = 31, сложность умножения не превосходит 557 392, а глубина схемы не превосходит 31£>(Л(7)) + D(M(7)) = 253 Ухудшив оценку сложности, можно получить оценку для глубины 129

Выбор приведенных выше конкретных примеров мотивируется тем, что порядок поля G F {7й 31) приблизительно равен 21000 и является минимально возможным, при котором обеспечивается необходимый уровень криптографической надежности согласно современным стандартам В следующей теореме указывается асимптотическая оценка сложности умножения многочленов произвольной степени над GF(72)

Теорема 3.3.1. Многочлены степени п— 1 HadGF(72) могут быть умножены со сложностью М(п) < 6098707 п1о&7

В четвёртой главе изучаются схемы для арифметики в полях большой характеристики Интерес к эффективной реализации арифметики в таких полях также возник в связи с возможными применениями в криптографии на эллиптических кривых С этой целью было предложено в работе22 использовать поля с характеристикой, относительно мало отличающейся от степени двойки (такие простые числа названы ней псевдо-мерсенновскими), в которых существуют полиномиальные базисы, соответствующие неприводимым двучленам (такие представления этих полей названы в указанной работе оптимальными расширениями простых полей) В работе23 среди таких расширений выделены расширения размерности 2", 3™ и представлены в виде башен полей, построенных из

"Bailey D V, Paar С Efficient arithmetic ш finite field extensions with application in elliptic curve cryptography J of Cryptology 14 3(2001), 156- 173

23S Baktir, В Sunar Optimal tower fields IEEE Trans Comp v 53 N 10 (2004), 1231-1243

квадратичных и кубических расширений С использованием этих башен (названных оптимальными башнями полей) в этой работе была указана для оптимальных расширений эффективная реализация операций умножения и инвертирования

Далее для формулирования результатов используются следующие обозначения: M(q) - сложность умножения в GF(q), A{q) - сложность сложения в GF(q), М(С, q) - сложность умножения на константу С в GF{q). В цитированной работе получен результат, который можно сформулировать следующим образом

Умножение в башне полей GF(q2k) имеет рекуррентную верхнюю оценку сложности

M(q2') < 3kM{q) + 5(3fc - 2*)A(q) + l-{3k - 1 )M(a0, ?),

где многочлен x2— ао неприводим HadGF(q), ао € GF(q) Умножение в башне полей GF(q3lc) имеет рекуррентную верхнюю оценку сложности

M(q3k) < 6kM(q) + 5(6* - 3k)A(q) + - 1)М(а0> q),

где многочлен х3 - ао неприводим над GF(q), ао € GF(q).

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

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

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

M{qz) < 5M{q) + 2lA(q) + 6М(2, q)+

+2(М(4, q) + М( 1/2, q) + M(l/6, q)) + 2 М{а0,р)

в предположении, что q — 1 кратно 3, двучлены х" — а0 и х3п - ао неприводимы nadGF(p).

Умножение в башне полей д = рп, умеет оценку сложно-

сти

М(д4) < 7М(д) + 6М(и3, д) + 5Щд) + 6М( 1/6, д) + ЗМ(а0,р)

в предположении, что д — 1 кратно 12 и многочлены хп — с*о и х4п — ао неприводимы над

Умножение в башне полей (У/'Хд6), д = рп, имеет оценку сложности

М(д6) < 12М(д) + 121 А(д) + 6М(а0,р) + М(1/12,д)+ 2 2 +2(М(—3/2, д) + д) + М (-1/8, д) + д))+

2

+2(М(и;4, д) + М(- Зи4/2, д) + д))+

?) + д) + д)

в предположении, что д — 1 кратно 12, многочлены я" — ао и х6" — ао неприводимы над

Для д = рп,р = 213— 1, п = 2к°-3к1-5к2-7кз-131к*, к0 = 0,1, умножение в поле СР{дь) имеет оценку сложности М(д5) < 77А(д) + 11М(д), умножение в поле ОГ(д7) имеет сценку сложности М(д7) < 13М(д) + 344Л (д) + бЛ(р), умножение в поле (З.Р(д13) умеет оценку сложности М(д13) < 26М(д)+1026А(д)+12А(р), умножение в поле СР(ди) имеет оценку сложности М(ди) < 2Ш{д) + 1032А(д) + 13Л(р)

Для д - рп, р = 217 - 1, п = 2к° Зк» • Ък2 17кз, ко = 0,1, умножение в поле имеет оценку сложности М(д9) < 17М(д) + 578А(д) +

бА(р), умножение в поле С?.Р(д18) имеет оценку сложности М(д18) < 35М(д) + 1825А(д) + 17Д(р)

Умножение в поле СР(д2к), к < 4, д = рп, п = 2т, р = 216+1, имеет оценки сложности

М{дА) < 7М(д) + 59А(д) + ЗМ(3,р),

М(д8) < 1ЪМ{д) + 193Л(д) + 7М(3,р), М(д16) < 31М(д) + 558А(д) + 15М(3,р)

Далее используются также следующие обозначения I(q) - сложность инвертирования, S(q) - сложность возведения в квадрат, D(I(q)) - глубина схемы инвертирования, D(S(q)) - глубина схемы возведения в квадрат, D(M(C,q)) - глубина схемы умножения на константу С в поле GF{q), M(2S, q) = max{M{C, g) С = 2s, s = 1,2,3, .}, D(M(2s, g)) = max{D(M(C,q)) C = 2s,s = 1,2,3, }

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

I2m = /2т-1 + 652т-1 + 12М2т-1 + 15i42m-l + 5М(3, р) + М(б,р) +

+{2т~1 - 1)М(2,р),

где Д есть сокращение для1(рк), и аналогично определяются Mi, Sk, Ak Глубина этой схемы рекуррентно оценивается как

D{Iv*) = ОД-О + 2£>(М2т-0 + D(52m-i) + 2(£>(А(р)) + Я(М(3,р))

Для инвертирования в поле GF(qm), g = р", n = 2т, р — 216 + 1, может быть построена схема сложности

1(g)+410М (?) + 245(g) + 2173A(g) + 735M(2S, q) + 119М(3, р) + М(6, р)

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

D(I(q))+4D(M(q))+D(S(q))+19D(A(p))+10D(M(2s,p))+3D(M(3,p)) В противном случае она не превосходит

5 D{M{q)) + D(S(q)) + 21 D(A(p)) + 10D(M(29,p)) + 5D(M (3,p))

Инвертирование в поле GF(p10n), p = 1 (mod Юп), может быть выполнено схемами, имеющими оценки сложности

1(р10п) < 1{р2п) + 28М(р2п) + 143пЛ(р) + (16п + 2)М(а0,р)+

+6п(М(и>5,р) + M(wlp) + М{<4,р) + МЦ,р)), Т(р10п) < 7(р") + 445пА(р) + 76М(р") + 34М(а0,р)+ +6п(М(и5,р) + М(ш1,р) + M(wlp) + М(ш$,р)), а0 G GF{p)

Умножение в поле GF(qn) для q = р2, р — 213 — 1, n = 5m, т = 1,2, имеет оценку сложности

M(q5) < 27М(р) + 121 Л(р), М(д25) < 1462Л(р) + 243М(р)

Умножение в поле GF(jp2n) для р = 2fc — 1 при п < 2fc_1, имеющем только простые нечетные делители, делящиер— 1, может быть выполнено с помощью схемы, имеющей оценку сложности

М(р2п) < (15 2т~2 + 9(2т-1(т - 2) + 1 ))М(р)+

+((12т + 7)2т_1 + 9(2т-1(т - 2) + 1))Л(р),

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

Публикации автора по теме диссертации

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

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

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

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

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

Подписано в печать 01 11 07 Формат 60 х 84 '/16 Бумага офсетная Печать офсетная Уч-изд л 1,0 Тираж 100 экз Заказ 846

Нижегородский государственный технический университет им Р Е Алексеева Типография НГТУ 603950, Нижний Новгород, ул Минина, 24

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).

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

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.