Схемы для целочисленной арифметики и арифметики конечных полей

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

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

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

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

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

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

2.2 О схемах для умножения и инвертирования в композитных полях £?Е(2'1)

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

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

3.2 Схемы для умножения в поле СЕ(714п)

3.3 Некоторые эффективные схемы умножения многочленов

над полем 6Е(72)

4 О СХЕМАХ ДЛЯ АРИФМЕТИКИ В КОМПОЗИТНЫХ ПОЛЯХ БОЛЬШОЙ ХАРАКТЕРИСТИКИ
4.1 Схемная сложность операций в псевдомерсенновских полях
4.2 Схемы для умножения в башнях псевдомерсенновских полей
4.3 Умножение в полях СД^р2*), р = 216 +
4.4 О глубине инвертирования в поле 4.5 Умножение и инвертирование в поле СД^р2")
Литература

сигналов, а также может быть использована в программной реализации арифметических операций в конечных полях в компьютерной алгебре.
Краткое содержание диссертации опубликовано работах автора [54, 55, 56, 57, 58]. Работы [54, 55] выполнены в соавторстве. Автору диссертации принадлежат доказательства всех основных результатов. В работах [56, 57, 58] соавторов нет. Работы [54, 55, 56] опубликованы в журналах, рекомендованных ВАК для публикаций диссертационных материалов.
Первая глава служит предисловием к основной тематике и посвящена оптимизации метода Карацубы [7] и некоторых случаев метода Тоома [2, 8] для умножения п-битовых целых чисел с целью получения эффективных числовых оценок схемной сложности умножения для реально используемых на практике диапазонов изменения п. Методы синтеза схем для умножения целых чисел с некоторыми изменениями могут быть перенесены на умножение многочленов над конечными полями, что в свою очередь может быть использовано для эффективного схемного умножения элементон конечных полей.
Показано, что метод Карацубы умножения п-битовых чисел можно схемно реализовать с рекуррентной оценкой сложности
Т(2п) < ЗТ(п) + 52п - 9.
Этот метод эффективнее школьного метода для всех п > 16. На каждом шаге рекурсии в нем п-битовые сомножители эффективно разбивать на блоки длины [|] и [и бит. В методе Карацубы эффективно производить не полную рекурсию, а при й = 3, п = 2е = 8 перейти па школьный метод. Сложность оптимизированного варианта метода Карацубы для п — 23, 5 > 4, оценивается сверху как
■ п1о&2 3 - 52п + 4,5.
Приблизительно это вдвое лучше неоптимизированного варианта.
Показано, что метод Тоома умножения п-битовых чисел для п = 45, 5 > 4, в котором множители на каждом шаге рекурсии разбиваются на д = 4 части равной длины, можно схемно реализовать с рекуррентной оценкой сложности
Т(4п) < 7Т(п) + 662п + 1085.
В методе Тоома для д = 4 эффективно производить не полную рекурсию, а при я = 3, п = 45 = 64 перейти на оптимизированный вариант метода

где М(а1а2,4п) — это умножение на константу аха2 в поле СН(24га). Оценки для возведения в квадрат имеют вид
Ь(3(8п) < 21/(5(47г)) + 4п + Ь(М(а12,4гг)),
ОД8п) < Х?(5(4п)) + 1 + 1)(М(а1а2,4п)).
Из тождества
тоцстг — (А0 + ^1(*2)(а1а2) = Ха + (Ао + X)а
следует, что
Ь(М(о!1а2,47г)) = 2п + Ь(М(ац,2п)) + Ь(М(а, 2п)) = 4 п,
0(М(аха2,4тг)) = тах{1)(М(аь 2п)) + 1, Б(М{а, 2п))} = 2, так как Ь(М(а1,2п)) = п,0(М(а,2п)) = 1 в силу равенств
(ж»! + = ха + уа — х + уа. = + (х + у)а.
Возведение в квадрат в поле 24п) задается формулами
(Ао + X 1а2)2 = Ар + А^от + А^а2,
и ^(5(2тг)) = 21/(5(п)), Д(5(2п)) = 1)(5(п)), поэтому
1(5(4п)) < 21,(5(2п)) + 2п + £,(АГ(аь 2п)) = Зп + 4А(5(п)),
£>(5(4п)) < Д(5(2п)) + 1 + £»(М(аь 2п)) = 2 + £>(5(п)). Рассмотрим автоморфизм поля СА(4п)
а(т) = <т(Ао + Аха2) = т(Ао) + т(Ах)а2 = (г(Ао) + т(Ах)ах) + т(Ах)а2,
где т(Ах) = т(х2{а1 + х2х+ха|) = т2;+1 от + х2ха'х — автоморфизм поля др(22п) над подполем СА(2П). Норма элемента х в рассматриваемом расширении равна А4(х) = ха(х)а2(х)а3(х) и принимает значения в подполе (АР(2П). Пусть т = А0 4- А'хйз,
Ах = ЖххСкх + Х^+хОх + Т4Х-х2а1а2 + Ялй-ЗО^г £ 24),:Гг € СН(;‘).
Рассмотрим отображение
£(ж) = С(Ао + Ахаз) = а(А0)+сг(Ах)аз = (ст(Ао) -Ро^Ах^хагг) + <т(Ах)а3.