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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ „ ИМЕНИ М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519 7

Сергеев Игорь Сергеевич

О РЕАЛИЗАЦИИ НЕКОТОРЫХ ОПЕРАЦИЙ В КОНЕЧНЫХ ПОЛЯХ СХЕМАМИ ЛОГАРИФМИЧЕСКОЙ ГЛУБИНЫ

01.01 09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

МОСКВА - 2007

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

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

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

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

профессор В Б Алексеев,-

кандидат физико-математических наук, доцент А Е. Жуков

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

государственный университет

Защита диссертации состоится 12 октября 2007 г в 16 ч 15 мр на заседании диссертационного совета Д 501 001 84 в Московском государственном университете имени M В. Ломоносова по адресу 119991, Российская Федерация, Москва, ГСП-1, Ленинские горы, МГУ имени М. В. Ломоносова, Механико-математический факультет, ауд. 1408

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж)

Автореферат разослан 12 сентября 2007 г

Ученый секретарь

диссертационного совета

Д.501 001 84 в МГУ

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

профессор

В H Чубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

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

Особенность вычислений в конечном поле состоит в необходимости выбора представления элементов — от него существенно зависит способ реализации (и, как следствие, сложность и глубина логической схемы) Потенциально возможны (и описаны в теоретических работах) разные представления, но практически используются в основном два, а именно представления в стандартных и нормальных базисах, а также производные от них

Наиболее широко используемым является представление в стандартном базисе — элементы поля в нем представляются многочленами, арифметические операции с которыми выполняются по модулю неприводимого многочлена, определяющего этот базис

Умножение многочленов выполняется аналогами числовых методов, наиболее известные из которых были разработаны А А Карацубой1, A JI Тоомом2, А Шенхаге и Ф Штрассеном3'4 в 60-70-е годы На последнем методе достигаются одновременно наилучшие по порядку известные оценки схемной глубины О (log п) и сложности 0(п log п log log n), где п — разрядность сомножителей (или их степень, в случае если это многочлены)

Иначе дело обстоит с делением (или инвертированием, тк деление сводится к инвертированию и умножению) Асимптотически быстрые ал-

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

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

3 Schonhage А , Strassen V Schnelle multiplikation großer zahlen // Computing — 1971 — V 7 — P 271-282 [Русский перевод Шенхаге А , Штрассен Ф Быстрое умножение больших чисел // Кибернетический сборник Вып. 10 М Мир, 1973 С 87-98]

4Schonhage А Schnelle multiplikation von polynomen über korpern der Charakteristik 2 // Acta Inf - 1977 - V 7 - P. 395-398

горитмы деления чисел основаны на методе С Кука5 и имеют такую же по порядку сложность, как и умножение Однако логарифмический порядок схемной глубины на этих методах не достигается — наилучшая известная оценка глубины О (log п log log п) для таких схем получена Дж Рейфом и С Тейтом6 Для сложности схем с глубиной 0(log п) известна оценка 0(п1+£), полученная Й Хаастадом и Т Лейтоном7

Упомянутые методы деления переносятся на степенные ряды, но не приложимы прямо к делению в конечном поле Один из способов деления (инвертирования) в конечном поле состоит в применении расширенного алгоритма Евклида — наилучшая известная для него оценка сложности 0(п log2 п log log п) достигается в методе, предложенном для чисел А Шенхаге8, а для многочленов Ф Штрассеном9 Для глубины соответствующих схем можно указать оценку 0(п) Схема сложности 0(nwlogn), где w < 1,667 — экспонента умножения матриц размера у/п х л/ri и \[п х п, может быть построена методом, основанным на использовании аддитивных цепочек А Брауэра10 Глубина этой схемы оценивается как О (log2 п)

Схемы логарифмической глубины (и полиномиальной сложности) для инвертирования в конечном поле впервые были построены Б Литоу и Дж Давида11, а также X фон цур Гатеном12 в конце 80-х годов Сложность этих схем оценивалась авторами как а глубина — как

O(logn) Анализ показывает, что для сложности и глубины предложенных схем нельзя привести лучшие оценки, чем 0(п5) и 151og2n соответственно Улучшение этого результата являлось стимулом для настоящей работы

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

5 Cook S On the minimum computation time of functions Ph D Thesis Harvard Umv , 1966

6ReifJ,TateS Optimal size integer division circuits //SIAMJ Comput —1990 — V. 19, X«5 - P 912-925

7Hastad J , Leighton T Division m O(logn) depth using 0(n1+c) processors 1986 http //www nada kth se/~yohanh/paraldtmsion ps

8Schonhage A Schnelle berechnung von kettenbruchentwicklungen // Acta Inf — 1971 - V 1 -P 139-144

9 Strassen V The computational complexity of continued fractions // SIAM J Comput - 1983 - V 12, № -P1-27

10Brauer A On addition chains // Bull AMS - 1939 - V 45 - P 736-739

nLitow В , Davida G O(logn) parallel time finite field inversion // Proc Aegean Workshop on Computing Lecture Notes m Comp Sei — 1988 — V 319 — P 74-80

12von zur Gathen J Inversion in finite fields using logarithmic depth // J Symb Comput - 1990 — V 9 - P 175-183

нако другие операции (в частности, умножение) выполняются существенно сложнее, чем в стандартных базисах (речь идет об общем случае, поскольку на практике используются конкретные базисы, в которых необходимые операции реализуются эффективно) В самое последнее время ряд исследователей (Э Калтофен, В Шауп13, А А. Болотов, С В Гаш-ков14 и др ) высказали идею о том, что для ускорения реализации многих операций в нормальном представлении, и возможно некоторых операций в стандартном представлении, целесообразно (как с практической точки зрения, так и для получения теоретических оценок) использовать быстрые переходы между нормальными и стандартными базисами Оценки вида 0(па), а < 2, для сложности перехода в общем случае, по-видимому, до сих пор не были известны Получение таких оценок также являлось стимулом для данной работы

Цель работы

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

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

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

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

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

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

13KaItofen Е , Shoup V Subquadratic-time factoring of polynomials over finite fields // Math Comput - 1998 - V 67, №223 - P 1179-1197

14Болотов A A , Гашков GBO быстром умножении в нормальных базисах конечных полей // Дискретная математика — 2001 — Выл 13, №3 — С 3-31

2. Получена новая верхняя оценка схемной глубины инвертирования в конечном поле характеристики два

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

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

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

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

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

Результаты диссертации докладывались на семинаре «Синтез управляющих систем» под руководством академика РАН О Б Лупанова в 2005 г, на семинаре «Многозначная логика и ее приложения» под руководством С Б. Гашкова и А Б Угольникова в 2005 г, на научном семинаре отдела теоретической кибернетики Института прикладной математики имени М В Келдыша РАН в 2006 г, на XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 23-28 мая 2005 г.), на XVI Международной школе-семинаре «Синтез и сложность управляющих систем» (Санкт-Петербург, 26-30 июня 2006 г.), на Ломоносовских чтениях в 2006 г в МГУ

Публикации

Основные результаты диссертации опубликованы в трех работах автора, перечисленных в конце автореферата [1-3]

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

Диссертация состоит из пяти глав, разбитых на параграфы (первая глава является вводной) Текст диссертации изложен на 96 страницах Список литературы включает 93 наименования

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В главе 2 даются основные определения и сведения вспомогательного характера

Полем называется кольцо с единицей, ненулевые элементы которого образуют абелеву группу относительно операции умножения. Эта группа называется мультипликативной группой поля Конечным полем называется поле, содержащее конечное число элементов — это число называется порядком поля Порядок конечного поля может быть только степенью простого числа (которое является характеристикой поля), и при этом все поля одного порядка изоморфны Мультипликативная группа конечного поля — циклическая Единственное с точностью до изоморфизма конечное поле порядка q обозначается ОР{ц)

Конечное поле GF(gn) можно рассматривать как расширение поля С^(^) (или векторное пространство над степени п — все элемен-

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

При реализации операций в конечном поле С?^(дп) используется два основных представления стандартное (или полиномиальное), в котором элементы поля рассматриваются как многочлены степени не выше п — 1, а операции производятся по модулю некоторого неприводимого над СР(д) многочлена тпп(Ь) степени п, и нормальное, когда элементы поля рассматриваются как линейные комбинации над СР(д) с базисными элементами

а,а9, а®2, ,ач" \

где а — порождающий элемент (или генератор) базиса В обоих случаях элементы поля кодируются набором коэффициентов в разложении по соответствующему базису

В качестве модели для реализации операций в конечном поле &Р(дп) рассматриваются схемы над ОР(ц), которые определяются аналогично схемам из функциональных элементов, т е как ориентированные графы без ориентированных циклов с вершинами-входами, которым приписаны символы переменных или константы, и функциональными элементами в других вершинах, некоторые вершины являются выходами Входы и выходы элементов схемы принимают значения в СР(о), а сами функци-

ональные элементы реализуют функции над GF(q) Понятие схемы над GF(2) тождественно понятию булевой схемы

В качестве основного схемного базиса выбирается (функционально полный) базис бинарных арифметических операций сложения, вычитания, умножения и деления, а также констант Дополнительно при простом q используется функция минимума или максимума двух элементов поля (как чисел от 0 до q — 1), а в общем случае — бинарные арифметические операции в Z? (при наличии соответствия между элементами GF(q) и Ъч можно считать, что соответствующие элементы реализуют некоторые функции над GF(q))

Как обычно, сложность и глубина схемы S обозначаются через L(S) и D(S) соответственно

В главе 3 рассматриваются различные подходы к построению схем га-кратного умножения по модулю многочлена степени п над конечным полем с глубиной 0(log(mn)) Целью является минимизация порядка сложности таких схем относительно п Основной результат главы формулируется следующим образом

Теорема 3.4 Пусть j, 2, г € N, j < flog2log2 m] Тогда т-кратное умножение многочленов над GF(q) по модулю многочлена степени п выполняется схемой Mm n сложности и глубины

ЦМт,„) = О (ZaJm1+H3-è+M)n1+^ (2"J log(mn) loglog(mn) + ¿2)) ,

D(Mm,n) = О ((I + j) log m + r(l + l/У) logn),

где a = 81, если q четно, и a = 8, иначе

Оценки теоремы 3 4 используются при выводе основных результатов о схемной реализации инвертирования

В главе 4 изучается вопрос о построении схем для инвертирования в конечном поле GF{qn) с глубиной О (logn)

В конечном поле GF(qn) инвертирование эквивалентно возведению в степень qn — 2 Методом аддитивных цепочек строится схема сложности 0(n*"logn) и глубины О (log2 п), где w < 1,667 — экспонента умножения матриц размера -Jn х у/п и л/п х п Такая схема состоит из 0(log п) подсхем, реализующих умножения и операции Фробениуса (возведения в степень вида qk) в поле GF{qn). В предложенном параллельном алгоритме инвертирования также используются многократные умножения Доказана

Теорема 4.3 Пусть г € N Тогда инвертирование в стандартном базисе поля GF(qn) реализуется схемой 1п сложности и глубины

L(In) = 0(rn1/r(nw + П1'5 logn log logn)), D(In) = O(rlogn)

Из теоремы 4 3 вытекает, что можно построить схему для инвертирования сложности 0(п1,667) и глубины О (logn) В частном случае г ~ logn получаются оценки из метода аддитивных цепочек

Для стандартного базиса, допускающего сравнительно несложный переход к нормальному базису и обратно (под переходом подразумевается соответствующее преобразование координат), т. е имеющего низкую транзитивную сложность, оценка теоремы 4 3 может быть улучшена Теорема 4.4 Пусть R е N, R = o(logn/loglogn) Пусть схемы Т' и Т" реализуют соответственно прямой и обратный переходы между нормальным и стандартным базисами поля GF(qn) Тогда для инвертирования в любом из указанных базисов можно построить схему 1п сложности и глубины

L(In) = 0{Rhn1+2'R) + 0{R%fc){L(T') + L(T")),

D(In) = 0(i?(log n + D(T') + D(T"))),

где b — (4/3) log2 3, если q четно, и b = 1, если q нечетно

Из теоремы 4 4 следует, что в базисах с почти линейной транзитивной сложностью инвертирование также выполняется с почти линейной сложностью При этом, если соответствующие переходы между базисами выполняются с глубиной О (logn), то строящаяся схема инвертирования также имеет глубину О (logn) В качестве примера можно рассмотреть гауссовы нормальные базисы (ГНБ)

ГНВ k-го типа существует в поле GF(qn), если число кп + 1 — простое, и порождается элементом

а = С + С7+ +Ск'\

где — примитивный корень степени кп + 1 в поле GF(qkn), а 7 — при-' митивный корень степени к в поле вычетов Zfcn+1, который вместе с q порождает всю мультипликативную группу ^ы+х \ {0} Утверждение 4.2 Пусть к = o(logn) и е > 0, е = О (log logn/ logn). Тогда можно построить схему инвертирования в ГНВ к-го типа поля GF(qn) сложности 0(е~ьп1+е) и глубины 0(e~l log п), где b — из теоремы 4 4.

Далее в работе выясняется вопрос о минимизации глубины схемы инвертирования в полях характеристики два Показано, что инвертирование в произвольном базисе поля GF(2n) можно реализовать схемой глубины асимптотически (3 + a) log2 п, где а — константа глубины многократного сложения, которая определяется как наименьшее число, такое, что существует схема сложения п одноразрядных чисел, имеющая

глубину (er + о(1)) log2 n (известно, что а < 3,44) Сложность построенной схемы инвертирования равна 0(п4) Данный результат вытекает из следующей теоремы о сложности и глубине реализации возведения в произвольную степень в конечном поле

Теорема 4.5 Пусть т — количество ненулевых разрядов в двоичной записи числа Е Тогда можно построить схему Ет>п, реализующую операцию возведения в степень Е в поле GF(2n), со сложностью и глубиной (при б > 0)

ЦЕп,т) < (1 + 0(l))l0gtg^n?(£) mW +

£>(Еп,т) < (2 + с) log2 п + 4,44 log2 то + О (log2 log n) + С2(е),

где Ci — некоторые ограниченные на любом отрезке интервала (0,1] функции

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

Основным результатом главы является следующая Теорема 5.2 Переход между двумя любыми нормальными или стандартными базисами поля GF(qn) может быть выполнен схемой сложности 0(71") и глубины O(logn), где

и > min max{w((T, 1 - er, 1), Ц(1 + cr)/2, (1 + ег)/2,1)}, сте[о, 1]

а ш{а, ß, 7) — экспонента умножения матриц размера па х та'3 ип^х п7 Из данной теоремы следует (при подстановке известных оценок для матричных экспонент), что для сложности построенных схем справедлива оценка 0(п1,806) Как следствие, умножение или инвертирование в произвольном нормальном базисе поля GF{qn) может быть реализовано схемой сложности 0(п1,806) и глубины O(logn) Это примеры операций, которые выполняются асимптотически быстрее посредством перехода к стандартному базису, чем специально разработанными для нормальных базисов алгоритмами

В качестве примера операции в стандартном базисе, которая может быть выполнена быстрее за счет перехода к нормальному представлению, приводится тест на базисность нормальной системы, т е. задача проверки, порождает ли заданный элемент ß нормальный базис в поле GF(qn), иначе говоря, является ли нормальная система {/?, ßq, , ßqn~ } линейно независимой над GF(q) Показано, что эта операция также реализуется схемой сложности 0(п1,806) и глубины O(logn)

При дополнительных ограничениях оценки сложности теоремы 5 2 можно улучшить. Например, нормальные базисы, в которых быстро выполняется умножение стандартным алгоритмом (Месси—Омура), допускают быстрый переход к стандартным базисам и обратно

Стандартный метод умножения в нормальном базисе В поля GF(qn) имеет сложность 0(Свп), где Св — сложность базиса В — понятие, вытекающее из структуры этого алгоритма Сложность нормального базиса с генератором а определяется как суммарное количество ненулевых коэффициентов в разложении элементов

0° а1 о"-1

аач , аач , ,аа4

в этом базисе Для любого базиса В выполнено 2п — 1 < Св < п2 Справедлива

Теорема 5.3 Переход от стандартного базиса к нормальному базису В в поле GF(qn) может быть реализован схемой сложности 0{у/пСв) + 0(п1,667), а обратный переход можно выполнить схемой сложности 0(п1,667) + 0(п1'5 log q log п log log n)

Метод умножения в нормальных базисах, вытекающий из теоремы 5 3, предназначен для полей с малым основанием q

В заключение автор выражает глубокую благодарность научному руководителю С. Б Гашкову за постановку задач, а также коллективам кафедры дискретной математики механико-математического факультета Московского государственного университета имени М В Ломоносова и отдела теоретической кибернетики Института прикладной математики имени М В Келдыша РАН за всесторонние помощь и поддержку

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

1 Сергеев И С Об инвертировании в конечных полях характеристики 2 с логарифмической глубиной // Вестник МГУ Серия 1 Математика. Механика — 2007 — №1 — С 28-33

2. Сергеев И С О схемах логарифмической глубины для инвертирования в конечных полях характеристики два // Математические вопросы кибернетики Вып 15 — М Физматлит, 2006 — С 35-64.

3 Сергеев И С О реализации некоторых операций конечных полей характеристики 2 схемами логарифмической глубины // Материалы XVI Международной школы-семинара «Синтез и сложность управляющих систем» (Санкт-Петербург, 26-30 июня 2006 г) — М Изд-во мех -матем факультета МГУ, 2006 — С. 101-103

Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова Подписано в печать

Формат 60 х 90 1/16 Уел печ л

Тираж 100 экз Заказ

1 Введение

1.1 История вопроса.

1.2 Краткое содержание работы.

2 Основные определения и вспомогательные сведения

2.1 Конечные поля.

2.2 Схемы над GF(q)

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

2.4 Линейные операции

2.5 Умножение матриц.

2.6 Арифметика чисел и многочленов. f 3 Многократное умножение

3.1 Числовое и модулярное многократное умножение.

3.2 Применение дискретного логарифмирования.

3.3 Применение китайской теоремы об остатках

3.4 Применение ДПФ

3.4.1 Дискретное преобразование Фурье.

3.4.2 Умножение над полем характеристики

3.4.3 Умножение над полем нечетной характеристики

3.4.4 Умножение с логарифмической глубиной.

3.5 О применении метода Д. Кантора.

4 Инвертирование

4.1 Метод аддитивных цепочек.

4.1.1 Аддитивные цепочки.

4.1.2 Метод Брауэра. 4.2 К построению параллельных схем.

4.2.1 О методах Литоу—Давида и фон цур Гатена.

4.3 Инвертирование в базисах с низкой транзитивной сложностью

4.3.1 Оптимальные нормальные базисы.

4.3.2 Гауссовы нормальные базисы.

4.4 Глубина инвертирования в поле GF(2n).

4.4.1 Дискретное логарифмирование.

4.4.2 Выбор вспомогательного поля

5 Переход между нормальными и стандартными базисами

5.1 Метод Брента—Кунга.

5.2 Переход к нормальному базису.

5.3 Переход к стандартному базису.

5.4 Уточнение оценки сложности.

5.5 Дополнение.

5.5.1 О методе Калтофена—Шаупа.

5.5.2 О вычислениях в произвольном стандартном базисе

5.5.3 Об умножении в нормальных базисах.

5.5.4 О реализации всех автоморфизмов Фробениуса

5.5.5 О проверке линейной независимости нормальной системы

1.1 История вопроса

Схема из функциональных элементов является, по существу, параллельной моделью вычислений — ее быстродействие определяется задержкой в цепочке между входом и выходом, а не суммарным временем выполнения всех элементарных операций, как в последовательной модели. В теоретических работах анализ задержки обычно заменяется анализом глубины, когда все элементы имеют единичную задержку и игнорируется задержка на участках цепей между элементами. Но даже в этих допущениях, как показал В. М. Храпченко [32], глубина (максимальное число элементов в цепочке схемы) может существенно отличаться от задержки в ее физическом смысле (минимальное время, исчисляемое в единичных задержках, необходимое для установления окончательного результата на выходах схемы).

Интерес к оптимизации глубины схем для выполнения арифметических операций рос по мере развития схемотехники и уже в 60-е годы отразился в классических работах [25, 14, 31] о реализации сложения и умножения чисел. В целом же, вопросы сложности всегда имели приоритет над вопросами глубины ввиду распространения последовательных моделей вычисления, какими, например, являются компьютерные программы (из теории можно в качестве примера привести одноленточные машины Тьюринга).

Сложность, хоть она явным образом и не влияет на быстродействие схемы, все же является важной характеристикой, определяющей площадь (объем) и, как следствие, потребляемую мощность,1 которые в реальности накладывают серьезные ограничения на способ синтеза. Поэтому если такая постановка задачи, как оптимизация сложности без учета глубины, выглядит естественной (при использовании последовательной модели вычислений, для которой глубина безразлична), то при оптимизации по глубине практически обусловленной является сопутствующая оптимизация (или хотя бы анализ) сложности.

Теоретически оптимизация по глубине с учетом сложности рассматривается в двух основных постановках: (1) заданную арифметическую операцию реализовать схемой с возможно меньшим порядком глубины и наилучшим известным порядком сложности, либо (2) построить схему с возможно меньшим порядком сложности и наилучшим известным порядком глубины. Первой постановке следует, например, обзор [40, гл. 4], а второй — рабо

1Хотя, как выяснил О. М. Касим-Заде, связь между сложностью и мощностью не настолько однозначна, см., например, [15]. та [64]. В ряде случаев наилучшие известные решения совпадают для обеих постановок (как, например, для умножения). Отметим, что для операции, которая реализуется схемой с логарифмическим (относительно числа входов) порядком глубины, вторая постановка может быть переформулирована более конкретно как минимизация сложности схемы с логарифмической глубиной.

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

Теория конечных полей была заложена в работах Ферма, Эйлера, Ле-жандра, Гаусса, Галуа, Диксона и других выдающих ученых, и до последней четверти 20-го века развивалась как область чистой математики, но в связи с развитием криптографии, как отмечается в [5], к настоящему времени превратилась едва ли не в прикладной раздел. Сегодня вопросам эффективной реализации арифметики в конечных полях посвящено несколько специальных книг (в основном зарубежных, см. [5]).

Особенность вычислений в конечном поле состоит в необходимости выбора представления элементов — от него существенно зависит способ реализации (и, как следствие, сложность и глубина схемы). При работе с числами или многочленами этот вопрос как будто бы не стоит. Несмотря на то, что потенциально возможны (и описаны в теоретических работах) разные представления, практически используются два, стандартное и нормальное, а также производные от них.

Наиболее универсальным является стандартное представление — элементы поля в нем представляются многочленами, основные арифметические операции с которыми реализуются достаточно просто.

Умножение многочленов выполняется аналогами числовых методов, наиболее известные из которых были разработаны А. А. Карацубой [14], A. JL Тоомом [29] (уточнен Куком [48]), Шёнхаге и Штрассеном [84] в 60-е годы. На последнем методе достигаются одновременно наилучшие по порядку известные оценки глубины O(logn) и сложности О(п log п log log п), где п — разрядность сомножителей.2

Иначе дело обстоит с делением (или инвертированием, т.к. деление сводится к инвертированию и умножению). Асимптотически быстрые алго

2Недавно Фюрер [55] показал, что умножение чисел можно выполнять со сложностью n2°('og n' logn и глубиной 0(lognlog* п), где log*п определяется из соотношения log2. log2 nj = 1.

4-ч,-' log* П ритмы деления чисел3 основаны на методе Кука [48] и имеют такую же но порядку сложность, как и умножение. Однако логарифмический порядок глубины на этих методах не достигается — наилучшая известная оценка глубины таких схем имеет вид O(lognloglogn) [79]. Для сложности схем с глубиной O(logn) известна оценка 0(п1+£) из работы [64].

Упомянутые методы деления переносятся на степенные ряды, но не при-ложимы прямо к делению в конечном поле (когда деление производится по модулю неприводимого многочлена, результат вычисляется точно). Быстрый способ деления (инвертирования) в конечном поле состоит в применении алгоритма Евклида — наилучшая известная для него оценка сложности, 0(п log2 п log log п), достигается в методе Кнута—Шёнхаге [81]. Для глубины соответствующей схемы можно указать оценку О (п). Схема сложности 0(nw logn), где w < 1,667 — экспонента умножения матриц размера у/п х у/п и у/Б х п, может быть построена методом аддитивных цепочек (приведенная оценка вытекает из работ [42, 44, 67]). Глубина в этом методе оценивается как 0(log2n).

Схемы логарифмической глубины для инвертирования в конечном поле впервые были построены в работах [73, 57] в конце 80-х годов. Сложность этих схем оценивалась авторами как а глубина — как O(logn). Анализ показывает, что для сложности и глубины предложенных схем нельзя привести лучшие оценки, чем 0(п5) и 15Iog2n соответственно. Улучшение этого результата являлось стимулом для настоящей работы.

В нормальном представлении конечного поля можно быстро выполнять возведение в степень определенного вида, однако другие основные операции (прежде всего, умножение) в специально разработанной для нормальных базисов технике выполняются существенно сложнее, чем в стандартных базисах (речь идет об общем случае, поскольку на практике используются конкретные базисы, в которых необходимые операции реализуются эффективно). В последнее время (например, [70, 4]) была высказана идея о том, что для ускорения реализации многих операций в нормальном представлении, а также некоторых операций в стандартном, целесообразно (как с практической точки зрения, так и для получения теоретических оценок) использовать переходы между нормальными и стандартными базисами. Оценки вида 0{па), а < 2, для сложности перехода в общем случае, по-видимому, до сих пор не были известны. Получение таких оценок также являлось стимулом для данной работы.

З3адача деления двух чисел состоит в нахождении частного с некоторой точностью (обычно с той же, с которой заданы делимое и делитель).

1. Алексеев В. В., Сложность умножения матриц. // Кибернетический сборник. Вып. 25. - М.: Мир, 1988. - С. 189-236.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Проектирование и анализ вычислительных алгоритмов. — М.: Мир, 1979.

3. Берлекемп Э. Алгебраическая теория кодирования. — М.: Мир, 1971.

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

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

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

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

8. Гашков С. Б. Замечание о минимизации глубины булевых схем. // Вестник МГУ. Серия 1. Математика. Механика. — 2007. — №2.

9. Гашков С. Б., Гашков И. Б. О сложности вычисления дифференциалов и градиентов. // Дискретная математика. — 2005. — Вып. 17, №3. — С. 45-67.

10. Гашков С. Б., Гринчук М. И., Сергеев И. С. О построении схем сумматоров малой глубины. // Дискретный анализ и исследование операций. Серия 1. 2007. - Том 14, №1. - С. 27-44.

11. Гашков С. Б., Кочергин В. В. Об аддитивных цепочках векторов, вентильных схемах и сложности вычисления степеней. // Методы дискретного анализа в теории графов и сложности. — 1992. — Том 52. — С. 22-40.

12. Гашков С. Б., Сергеев И. С. О применении метода аддитивных цепочек к инвертированию в конечных полях. // Дискретная математика. — 2006. Вып. 18, т. - С. 56-72.

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

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

15. Касим-Заде О. М. Об одной мере сложности схем из функциональных элементов. // Проблемы кибернетики. Вып. 38. — М.: Наука, 1981. — С. 117-179.

16. Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы. — М.: Вильяме, 2004.

17. Коблиц Н. Курс теории чисел и криптографии. — М.: ТВП, 2001.

18. Коновальцев И. В. Об одном алгоритме решения линейных уравнений в конечных полях. // Проблемы кибернетики. Вып. 19. — М.: Наука, 1967. С. 269-274.

19. Лидл Р., Нидеррайтер X. Конечные поля. — М.: Мир, 1988.

20. Ложкин С. А. О связи между глубиной и сложностью эквивалентных формул и о глубине монотонных функций алгебры логики. // Проблемы кибернетики. Вып. 38. М.: Наука, 1981. - С. 269-271.

21. Лупанов О. Б. О вентильных и контактно-вентильных схемах. // Доклады АН СССР. 1956. - Т. 111(6). - С. 1171-1174.

22. Лупанов О. Б. О синтезе некоторых классов управляющих систем. // Проблемы кибернетики. Вып. 10. — М.: Физматлит, 1963. — С. 63-97.

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

24. Ноден П., Китте К. Алгебраическая алгоритмика. — М.: Мир, 1999.

25. Офман Ю. П. Алгоритмическая сложность дискретных функций. // Доклады АН СССР. 1962. - Т. 145(1). - С. 48-51.

26. Пан В. Я. О схемах вычисления произведений матриц и обратной матрицы. // Успехи мат. наук. 1972. - 27, №5. - С. 249-250.

27. Серпинский В. 250 задач по элементарной теории чисел. — М.: Просвещение, 1968.

28. Столяров Г. К. Способ параллельного умножения в цифровых вычислительных машинах и устройство для осуществления способа. Авт. свид-во кл. 42 т 14, №126668, 1960.

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

30. Хохлов Р. А. Реализация логическими схемами операций умножения и инвертирования в конечных полях характеристики два. — Канд. дисс., МГУ, 2005.

31. Храпченко В. М. Об асимптотической оценке времени сложения параллельного сумматора. // Проблемы кибернетики. Вып. 19. — М.: Наука, 1967. С. 107-120.

32. Храпченко В. М. Различие и сходство между задержкой и глубиной. // Проблемы кибернетики. Вып. 35. — М.: Наука, 1979. — С. 141-168.

33. Яблонский С. В. Введение в дискретную математику. — М.: Высшая школа, 2002.

34. Agnew G. В., Beth Т., Mullin R. С., Vanstone S. A. Arithmetic operations in GF(2m). // J. of Crypt. 1993. - V. 6. - P. 3-13.

35. Ash D., Blake I., Vanstone S. Low complexity normal bases. // Discrete Applied Math. 1989. - V. 25. - P. 191-210.

36. Eberly W. Very fast parallel polynomial arithmetic. // SIAM J. Comput. — 1989. V. 18, №5. - P. 955-976.

37. Feisel S., von zur Gathen J., Shokrollahi M. A. Normal bases via general Gauss periods. // Math. Comput. 1999. - V. 68, №225. - P. 271-290.

38. Fiduccia С. M. On the algebraic complexity of matrix multiplication. — Ph. D. thesis, Brown Univ., 1973.

39. Fiirer M. Faster integer multiplication. — 2007. — http://www.cse.psu.edu/~furer/Papers/mult.pdf.

40. Grove E. Proofs with potential. Ph.D. thesis, U.C. Berkeley, 1993.

41. Hastad J., Leighton T. Division in O(logn) depth using 0(n1+e) processors. — 1986. — http://www.nada.kth.se/~yohanh/paraldivision.ps.

42. Hoover H., Klawe M., Pippenger N. Bounding fan-out in logical networks. // J. ACM. 1984. - V. 31, M. - P. 13-18.

43. Hopcroft J. E., Kerr L. R. On minimizing the number of multiplications necessary for matrix multiplication. // SIAM J. Appl. Math. — 1971. — V. 20, M. P. 30-36.

44. Huang X., Pan V. Fast rectangular matrix multiplication and applications. // J. Complexity. 1998. - V. 14. - P. 257-299.

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

46. Jungnickel D. Finite fields: structure and arithmetics. — Mannheim: Wissenschaftsverlag, 1995.

47. Kaltofen E., Shoup V. Subquadratic-time factoring of polynomials over finite fields. // Math. Comput. 1998. - V. 67, №223. - P. 1179-1197.

48. Kaltofen E., Singer M. Size efficient parallel algebraic circuits for partial derivatives. // IV ICCAPR Conf. (Singapore, 1991). P. 133-145.

49. Knuth D. The analysis of algorithms. // Proc. Intern. Congress of Math. (Nice, France). 1970. - V. 3. - P. 269-274.

50. Litow В., Davida G. O(logn) parallel time finite field inversion. // Proc. Aegean Workshop on Computing. Lecture Notes in Сотр. Sci. — 1988. — V. 319. P. 74-80.

51. Massey J. L., Omura J. K., Apparatus for finite fields computation. //US patent application. 1986. - №4587627.

52. Moenk R. Fast algorithm of GCD's. // Proc. 5th Ann. ACM Symp. on Theory of Computing. 1973. - P. 142-151.

53. Mullin R., Onyszchuk I., Vanstone S., Wilson R. Optimal normal bases in GF(pn). // Discrete Applied Math. 1988/89. - V. 22. - P. 149-161.

54. Pan V. Y. Complexity of parallel matrix computations. // Theor. Сотр. Sci. 1987. - V. 54. - P. 65-85.

55. Paterson M., Zwick U. Shallow circuits and concise formulae for multiple addition and multiplication. // Comput. Complexity. — 1993. — V. 3. — P. 262-291.

56. Reif J., Tate S. Optimal size integer division circuits. // SIAM J. Comput. 1990. - V. 19, №5. - P. 912-925.

57. Rosser J., Schoenfeld L. Approximate formulas for some functions of prime numbers. // 111. J. Math. 1962. - V. 6 - P. 64-94.

58. Schdnhage A. Schnelle berechnung von kettenbruchentwicklungen. // Acta Inf. 1971. - V. 1. - P. 139-144.

59. Schonhage A. A lower bound for the length of addition chains. // Theor. Сотр. Sci. 1975. - V. 1. - P. 1-12.

60. Schonhage A. Schnelle multiplikation von polynomen iiber korpern der charakteristik 2. // Acta Inf. 1977. - V. 7. - P. 395-398.

61. Schonhage A., Strassen V. Schnelle multiplikation grofier zahlen. // Computing. — 1971. — V. 7. — P. 271-282. Русский перевод: Шёнхаге A., Штрассен В. Быстрое умножение больших чисел. // Кибернетический сборник. Вып. 10. М.: Мир, 1973. С. 87-98.]

62. Strassen V. Gaussian elimination is not optimal. // Numer. Math. — 1969. B. 13, №4. - P. 354-356. Русский перевод: Штрассен Ф. Алгоритм Гаусса не оптимален. // Кибернетический сборник. Вып. 7. М.: Мир, 1971. С. 67-70.]

63. Strassen V. Die berechnungskomplexitat von elementarsymmetrischen funktionen und von interpolationskoeffizienten. // Numer. Math. — 1973. B. 20 - P. 238-251.

64. Strassen V. Vermeidung von divisionen. // J. reine u. angew. Math. — 1973. V. 264. - P. 182-202.

65. Strassen V. The computational complexity of continued fractions. // SIAM J. Comput. 1983. - V. 12. - P. 1-27.

66. Takagi N., Yoshiki J., Takagi K. A fast algorithm for multiplicative inversion in GF(2n) using normal basis. // IEEE Trans, on Сотр. — 2001. V. 50, №5. - P. 394-398.

67. Yao A. C. On the evaluation of powers. // SIAM J. Comput. 1976. -V. 5. - P. 100-103.Работы автора по теме диссертации

68. Сергеев И. С. Об инвертировании в конечных полях характеристики 2 с логарифмической глубиной. // Вестник МГУ. Серия 1. Математика. Механика. 2007. - №1. - С. 28-33.

69. Сергеев И. С. О схемах логарифмической глубины для инвертирования в конечных полях характеристики два. // Математические вопросы кибернетики. Вып. 15. — М.: Физматлит, 2006. — С. 35-64.