О реализации некоторых операций в конечных полях схемами логарифмической глубины

• Автор: Сергеев, Игорь Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 96 с.

1 Введение

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

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

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

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

2.2 Схемы над СПДд)

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

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

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

2.6 Арифметика чисел и многочленов

* 3 Многократное умножение

3.1 Числовое и модулярное многократное умножение
3.2 Применение дискретного логарифмирования
3.3 Применение китайской теоремы об остатках
3.4 Применение ДПФ
3.4.1 Дискретное преобразование Фурье
3.4.2 Умножение над полем характеристики 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.1 История вопроса
Схема из функциональных элементов является, по существу, параллельной моделью вычислений — ее быстродействие определяется задержкой в цепочке между входом и выходом, а не суммарным временем выполнения всех элементарных операций, как в последовательной модели. В теоретических работах анализ задержки обычно заменяется анализом глубины, когда все элементы имеют единичную задержку и игнорируется задержка на участках цепей между элементами. Но даже в этих допущениях, как показал В. М. Храпченко [32], глубина (максимальное число элементов в цепочке схемы) может существенно отличаться от задержки в ее физическом смысле (минимальное время, исчисляемое в единичных задержках, необходимое для установления окончательного результата на выходах схемы).
Интерес к оптимизации глубины схем для выполнения арифметических операций рос по мере развития схемотехники и уже в 60-е годы отразился в классических работах [25, 14, 31] о реализации сложения и умножения чисел. В целом же, вопросы сложности всегда имели приоритет над вопросами глубины ввиду распространения последовательных моделей вычисления, какими, например, являются компьютерные программы (из теории можно в качестве примера привести одноленточные машины Тьюринга).
Сложность, хоть она явным образом и не влияет на быстродействие схемы, все же является важной характеристикой, определяющей площадь (объем) и, как следствие, потребляемую мощность,1 которые в реальности накладывают серьезные ограничения на способ синтеза. Поэтому если такая постановка задачи, как оптимизация сложности без учета глубины, выглядит естественной (при использовании последовательной модели вычислений, для которой глубина безразлична), то при оптимизации по глубине практически обусловленной является сопутствующая оптимизация (или хотя бы анализ) сложности.
Теоретически оптимизация по глубине с учетом сложности рассматривается в двух основных постановках: (1) заданную арифметическую операцию реализовать схемой с возможно меньшим порядком глубины и наилучшим известным порядком сложности, либо (2) построить схему с возможно меньшим порядком сложности и наилучшим известным порядком глубины. Первой постановке следует, например, обзор [40, гл. 4], а второй — рабо1Хотя, как выяснил О. М. Касим-Заде, связь между сложностью и мощностью не настолько однозначна, см., например, [15].

операций Фробениуса (и многократные умножения с такой суммарной кратностью). Покажем по индукции, что основание системы счисления можно подобрать таким образом, что указанная величина не превосходит
2г у/п/2 + О(г) = (2г — 1п4 + 0(1/г))у/п + О(г).
В случае г = 1 утверждение очевидно. Предположим, что оно доказано для всех г < к. Рассмотрим случай г = к + 1.
Положим тк = р П — 1 — ткГ1 + Пк,
где также выполнены неравенства щ < ц тк-1{тк-2(- • • (гп1П0 + щ)...) + пк-2) + Щ-,

к—1 к 1 л» гГ
ТП1 + пх< Тку/п!/2 + О (к) < ■ + О (к),
(=1 1=0
откуда следует
к — ( 2 к —
+ < (2[1 + -=)уЪ + 0(г).
1=1 г=0 ' V /*
При условии /1 > 0 величина в скобках достигает своего наименьшего значения 2г/ Основным результатом параграфа является следующая теорема, уточняющая вывод предшествующих работ [73, 57]:
Теорема 4.3 Пусть г € N. Тогда инвертирование в стандартном базисе поля СТР1^") реализуется схемой 1п слооюности и глубины
Ь(1п) = 0(т^Т(пи} + я1,5к^пк^к^я)), П(1п) - 0(г к^я),
где и> — экспонента матричного умножения Т^
Доказательство. Такая схема строится методом леммы 4.1, в котором операции Фробениуса реализуются схемами сложности 0(яш + у/пМ(п)) и глубины О(к^я), а т-кратные умножения — схемами из следствия 3.4 сложности 0(тпапь), где а + Ь < 2,5, и глубины 0{[og{mn)). Поскольку яг<яиш>1,5, в оценке сложности доминируют операции Фробениуса.
Из доказанной теоремы, в частности, вытекает, что можно построить схему сложности 0(я1,667) и глубины 0(logn).