Введение к работе
Актуальность темы
Теория конечных полей была построена в работах Ферма, Эйлера, Лежандра, Гаусса, Галуа, Диксона и других выдающих ученых, и до последней четверти 20-го века развивалась как область чистой математики, но в связи с потребностями кодирования и криптографии в настоящее время активно развиваются прикладные аспекты теории. Вопросам эффективной реализации арифметики в конечных полях посвящено много работ и несколько специальных книг, в основном зарубежных авторов.
Особенность вычислений в конечном поле состоит в необходимости выбора представления элементов — от него существенно зависит способ реализации (и, как следствие, сложность и глубина логической схемы). Потенциально возможны (и описаны в теоретических работах) разные представления, но практически используются в основном два, а именно представления в стандартных и нормальных базисах, а также производные от них.
Наиболее широко используемым является представление в стандартном базисе — элементы поля в нем представляются многочленами, арифметические операции с которыми выполняются по модулю неприводимого многочлена, определяющего этот базис.
Умножение многочленов выполняется аналогами числовых методов, наиболее известные из которых были разработаны А. А. Карацубой1, А. Л. Тоомом2, А. Шёнхаге и Ф. Штрассеном3'4 в 60-70-е годы. На последнем методе достигаются одновременно наилучшие по порядку известные оценки схемной глубины O(logn) и сложности 0(nlognloglogn), где п — разрядность сомножителей (или их степень, в случае если это многочлены).
Иначе дело обстоит с делением (или инвертированием, т.к. деление сводится к инвертированию и умножению). Асимптотически быстрые ал-
^^Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах. // Доклады АН СССР. - 1962. - Т. 145(2). - С. 293-294.
2Тоом А. Л. О сложности схемы из функциональных элементов, реализующей умножение целых чисел. // Доклады АН СССР. - 1963. - Т. 150(3). - С. 496-498.
3Schonhage A., Strassen V. Schnelle multiplikation grofier zahlen. // Computing. — 1971. — V. 7. — P. 271-282. [Русский перевод: Шёнхаге А., Штрассен Ф. Быстрое умножение больших чисел. // Кибернетический сборник. Вып. 10. М.: Мир, 1973. С. 87-98.]
Schonhage A. Schnelle multiplikation von polynomen iiber korpern der charakteris-tik 2. II Acta Inf. - 1977. - V. 7. - P. 395-398.
горитмы деления чисел основаны на методе С. Кука5 и имеют такую же по порядку сложность, как и умножение. Однако логарифмический порядок схемной глубины на этих методах не достигается — наилучшая известная оценка глубины O(lognloglogn) для таких схем получена Дж. Рейфом и С. Тейтом6. Для сложности схем с глубиной O(logn) известна оценка 0(гг1+е), полученная И. Хаастадом и Т. Лейтоном7.
Упомянутые методы деления переносятся на степенные ряды, но не приложимы прямо к делению в конечном поле. Один из способов деления (инвертирования) в конечном поле состоит в применении расширенного алгоритма Евклида — наилучшая известная для него оценка сложности 0(nlog2 nloglogn) достигается в методе, предложенном для чисел А. Шёнхаге8, а для многочленов Ф. Штрассеном9. Для глубины соответствующих схем можно указать оценку 0(п). Схема сложности 0(nw logn), где w < 1,667 — экспонента умножения матриц размера у/п х у/п и у/п х п, может быть построена методом, основанным на использовании аддитивных цепочек А. Брауэра10. Глубина этой схемы оценивается как 0(log2n).
Схемы логарифмической глубины (и полиномиальной сложности) для инвертирования в конечном поле впервые были построены Б. Литоу и Дж. Давида11, а также X. фон цур Гатеном12 в конце 80-х годов. Сложность этих схем оценивалась авторами как п0<у1\ а глубина — как O(logn). Анализ показывает, что для сложности и глубины предложенных схем нельзя привести лучшие оценки, чем 0(п5) и 151og2 п соответственно. Улучшение этого результата являлось стимулом для настоящей работы.
В представлении конечного поля с помощью нормальных базисов можно быстро выполнять возведение в степени определенного вида, од-
5Cook S. On the minimum computation time of functions. Ph. D. Thesis. Harvard Univ., 1966.
6Reif J., Tate S. Optimal size integer division circuits. // SIAM J. Comput. — 1990. — V. 19, №5. - P. 912-925.
7Hastad J., Leighton T. Division in O(logn) depth using 0(n1+e) processors. 1986. . nada.kth. se/ ~yohanh/paraldivision.ps.
8Schonhage A. Schnelle berechnung von kettenbruchentwicklungen. // Acta Inf. — 1971. — V. 1. — P. 139-144.
9Strassen V. The computational complexity of continued fractions. // SIAM J. Comput. - 1983. - V. 12, №1. —P.l-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 in Сотр. Sci. — 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. Получена новая верхняя оценка сложности инвертирования в стандартном базисе конечного поля при реализации схемами логарифмической глубины из функциональных элементов.
13Kaltofen Е., Shoup V. Subquadratic-time factoring of polynomials over finite fields. // Math. Comput. - 1998. - V. 67, №223. - P. 1179-1197.
14Болотов А. А., Гашков С. Б. О быстром умножении в нормальных базисах конечных полей. // Дискретная математика. — 2001. — Вып. 13, №3. — С. 3-31.
Получена новая верхняя оценка схемной глубины инвертирования в конечном поле характеристики два.
Получены новые верхние оценки сложности перехода между стандартными и нормальными базисами конечных полей в общем случае, в том числе, для реализации схемами логарифмической глубины.
Как следствие, получены новые верхние оценки сложности умножения в нормальном базисе, проверки базисности нормальной системы в стандартном базисе и некоторых других операций в конечных полях.
Теоретическая и практическая ценность
Работа носит теоретический характер. Результаты работы могут найти применение в прикладных разработках по теории кодирования и компьютерной алгебре.
Апробация результатов
Результаты диссертации докладывались на семинаре «Синтез управляющих систем» под руководством академика РАН О. Б. Лупанова в 2005 г., на семинаре «Многозначная логика и ее приложения» под руководством СБ. Гашкова и А. Б. Угольникова в 2005 г., на научном семинаре отдела теоретической кибернетики Института прикладной математики имени М.В. Келдыша РАН в 2006 г., на XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 23-28 мая 2005 г.), на XVI Международной школе-семинаре «Синтез и сложность управляющих систем» (Санкт-Петербург, 26-30 июня 2006 г.), на Ломоносовских чтениях в 2006 г. в МГУ.
Публикации
Основные результаты диссертации опубликованы в трех работах автора, перечисленных в конце автореферата [1-3].
Структура и объем работы
Диссертация состоит из пяти глав, разбитых на параграфы (первая глава является вводной). Текст диссертации изложен на 96 страницах. Список литературы включает 93 наименования.
