Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n)




Скачать 75.94 Kb.
НазваниеАлгоритмы умножения в кольцах gf(2)[X] и полях gf(2n)
Дата публикации09.06.2014
Размер75.94 Kb.
ТипДокументы
literature-edu.ru > Информатика > Документы

АЛГОРИТМЫ УМНОЖЕНИЯ В КОЛЬЦАХ GF(2)[X]

И ПОЛЯХ GF(2n)


При использовании полиномиального базиса результат умножения в поле GF(2n) может быть получен из результата умножения в кольце GF(2)[X] как его остаток от деления на неприводимый многочлен f(X), порождающий поле. При этом операцию вычисления остатка принято называть приведением по модулю. В данном разделе изучаются алгоритмы умножения в кольце GF(2)[X] и алгоритмы приведения по модулю. При этом многочлены представляются бинарными векторами их коэффициентов, записываемыми в порядке убывания степеней переменных, к которым относятся коэффициенты.

1.Описание исследуемых алгоритмов в кольце GF(2)[X]:

Алгоритм сдвигов и сложений


Данный метод имеет асимптотическую сложность O(n2) и напоминает алгоритм умножения чисел, который изучался в школе. Существует несколько широко распространенных реализаций данного алгоритма, каждая из которых имеет те или иные преимущества. В данной работе исследуется алгоритм сдвигов и сложений с использованием таблицы умножения. Алгоритм умножения в поле GF(2n) приведен ниже:

Вход: векторы A,B длины n, для простоты полагаем что n – кратно 8, в противном случае вектору справа приписывается необходимое количество нулевых старших разрядов.

Выход: вектор res длины 2n, задающий коэффициенты произведения полиномов.

  1. res:=0

  2. i:=0

  3. пока i

    1. j:=0

    2. пока j

      1. Z:=T[Aj,Bi]

      2. resi +j := resi +j ⊕Z0

      3. resi+j+1 := resi+j +1 ⊕Z1

      4. j:=j+1

    3. i:=i+1


В данном алгоритме используются обозначения:

«⊕» - операция сложения восьми разрядных машинных слов по модулю 2

«T[X,Y]» - операция адресации по таблице умножения T.

Метод Карацубы


Данный метод умножения был предложен А. Карацубой в 1962.

Основу метода составляет следующее соотношение:

, где

,

,.

Это соотношение дает возможность определить рекурсивный алгоритм умножения.

Вход: A,B – многочлены степени n-1 (если степени многочленов не совпадают, или не являются степенью двойки, то старшие разряды дополняются нулями до ближайшей степени двойки)

Выход: С – многочлен степени 2*n-1, который является произведением многочленов A и B.


  1. если степень многочлена A равна степени многочлена B и равна 1, то вычислить произведение с использованием аппаратных функций (операции логического «И») и вернуть результат.

  2. Иначе:

    1. Выделить старшие и младшие части многочленов А и В (А1, В1 –старшие части, А00 –младшие части)

    2. Вычислить F1=A1-A0

    3. Вычислить F2=B0-B1

    4. Вычислить 3 произведения, рекурсивно вызывая данную функцию.

      1. D=A1*B1

      2. E=F1*F2

      3. G=A0*B0

    5. Записать результат в виде:


Для получения асимптотической оценки метода докажем следующее утверждение.

Утверждение: пусть a,b,c – некоторые неотрицательные числа, тогда решение рекуррентных уравнений



где n – степень числа с, имеет вид:



Доказательство:

Для простоты будем полагать, что n – степень числа c, тогда

,

где r=a/c.

Если aсходится, и, следовательно, T(n)=O(n).

Если a=c, то каждый член ряда равен 1, а всего членов O(log(n)).

Если a>c, то

,

то есть или, что то же, .

Что и требовалось.

В частности из этой теоремы следует, что сложность метода Карацубы есть .

Отсутствие арифметических операций над байтами делает затруднительным применение рекурсивного разложения для многочленов степени меньшей 8 в GF(2n), поэтому данное условие используется для остановки рекурсии, а для выполнения умножения на последнем шаге используется таблица.

Совмещенный алгоритм школьного метода и метода Карацубы (комбинированный метод). В данной модификации помимо входных данных в метод умножения передается параметр, который используется в условии остановки рекурсии в методе Карацубы. Так например, если для некоторой малой степени умножаемых многочленов m заранее известно, что метод сдвигов и сложений выполняется быстрее метода Карацубы, то при умножении многочленов степени n=m*k, исходный метод Карацубы можно ускорить, используя параметр m в условии остановки рекурсии и выполняя умножение многочленов степени m более быстрым (только для этой степени) алгоритмом. В общем случае значение параметра m зависит от типа используемой в вычислениях машины, частоты процессора, объема и скорости оперативной памяти и размера кэш-памяти.



2. Алгоритмы приведения по модулю


Классический алгоритм приведения. По определению, привести многочлен a(x) по модулю многочлена b(x) значит найти многочлен r(X), такой, что

a(X)=q(X)*b(X)+r(X), где deg(r(X))
Производя вычисления, используя это определение, получим алгоритм, который заключается в выравнивании многочленов по старшему разряду и выполнении последовательности операций сдвигов и сложений. Сложность классического метода есть O(n2).
Вход: векторы A,B длины n коэффициентов полиномов-сомножителей, для простоты полагаем что n – кратно разрядности базового слова.

Выход: вектор res длины n, задающий коэффициенты полинома r(x).

  1. res:=A

  2. B:=B<<(deg(res)-deg(B))

  3. пока B0<>1

    1. если deg(res)=deg(B)

      1. res:=resB

    2. B:=B>>1

  4. если deg(res)=deg(B)

    1. res:=resB


В алгоритме используются следующие обозначения:

«<<» - сдвиг в сторону старших разрядов на указанное количество разрядов,

«deg(B)» - функция получения индекса старшего ненулевого разряда вектора - операнда,

«<>» - логическая операция сравнения (если два операнда не равны, выражение принимает значение «истина»),

«» - операция сложения по модулю 2,

«>>» - операция сдвига в сторону младших разрядов,
Алгоритм приведения по модулю многочлена малого веса. Данный алгоритм дает преимущество, если многочлен В, по модулю которого выполняется приведение, имеет малое количество ненулевых коэффициентов. Причем предполагается, что s коэффициентов, идущих за старшей степенью многочлена нулевые. То есть bdeg(b(x))-1=0, bdeg(b(x))-2=0,…, bdeg(b(x))-s=0, в противном случае алгоритм неприменим.

В алгоритме на этапе предварительных вычислений формируется два списка смещения степеней относительно старшей степени многочлена В.

Первый список задает смещение в машинных словах, а второй – смещение в битах (количество разрядов, на которое нужно сдвинуть слово с ненулевым разрядом, чтобы ненулевой разряд оказался в той же позиции, что ненулевой и разряд старшей степени многочлена). Иначе, положив, что L=(r1,r2,…rm) – список степеней ненулевых коэффициентов многочлена В, списки сдвигов можно определить следующим образом:

, i=1,2,…m

, i=1,2,…m

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

Алгоритм заполнения списка сдвигов:
Вход: вектор В, длины n.

Выход: списки l, t смещений ненулевых элементов вектора В.

  1. i:=0

  2. j:=0

  3. mask:=231

  4. пока i

    1. если Bi<>0

      1. k:=0

      2. пока k<32

        1. если ((Вi)&(mask))<>0

          1. если (j=0)

            1. lj:=i

            2. tj:=k

          2. иначе

            1. lj:=i-l0

            2. tj=k-t0

          3. j:=j+1

        2. Bi:=Bi<<1

        3. k:=k+1

    2. i:=i+1


Алгоритм приведения с использованием предварительно заполненного списка сдвигов:
Вход: вектор А, длины n, степень многочлена В, списки сдвигов l, t, длины m.

Выход: вектор res длины n, задающий коэффициенты многочлена r(x)=A mod B.

  1. i:=1

  2. пока i

    1. j:=1

    2. пока j

      1. если tj<=0





      2. иначе





      3. j:=j+1

    3. Ai:=0

    4. i:=i+1

  3. mask:=~0

  4. mask:=mask<<(32-t0-1)

  5. j:=1

  6. пока j

    1. если tj<=0





    2. иначе





    3. j:=j+1

  7. Ai:=Ai&(~mask)


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

«<<» - сдвиг в сторону старших разрядов на указанное количество разрядов,

«deg(B)» - функция получения индекса старшего ненулевого разряда вектора-операнда,

«<>» - логическая операция сравнения (если два операнда не равны, выражение принимает значение «истина»),

«» - операция сложения по модулю 2,

«>>» - операция сдвига в сторону младших разрядов,

«&» - операция поразрядного логического «И»,

«~» - операция поразрядного логического отрицания.
Данный алгоритм позволяет выполнять операцию приведения по модулю многочленов определённого вида (по модулю многочленов малого веса) за пренебрежимо малое, по сравнению с операцией умножения время.

Контрольные вопросы:


  1. Какова асимптотическая сложность классического алгоритма умножения?

  2. Какова асимптотическая сложность алгоритма Карацубы?

  3. Какова асимптотическая сложность классического алгоритма приведения?

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

  5. В чем заключается смысл совмещения алгоритма Карацубы и классического алгоритма умножения?

Литература:


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

  2. Кнут Д.Э. Искусство программирования (том 2). // М.: Вильямс, 2000.

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

Добавить документ в свой блог или на сайт

Похожие:

Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n) iconУравнения и алгоритмы
К 89 Кузьмин, Д. В. Моделирование динамики мехатронных систем. Уравнения и алгоритмы: монография / Д. В. Кузьмин. – Архангельск:...

Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n) iconМетоды и алгоритмы многокритериальной оП­­­тимизации стандартных...
Методы и алгоритмы многокритериальной оП­­­тимизации стандартных ячеек в субмикронных технологиях проектирования сбис

Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n) iconЗаметки на полях "имени розы" заглавие и смысл
Напоминаю у Абеляра пример "nulla rosa est"s использован для доказательства, что язык способен описывать и исчезнувшие и несуществующие...

Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n) iconЛитература: Е. А. Никулин, Компьютерная геометрия и алгоритмы машинной графики
Реализовать алгоритм растеризации треугольника. (Залитый, по 2 координаты на вершину)

Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n) iconНаска: гигантские рисунки на полях Приобщение к тайне
Примерно в четырех с половиной сотнях километров к югу от Лимы, современной столицы Перу, и в сорока километрах от побережья Тихого...

Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n) icon«Умножение положительных и отрицательных чисел»
Цель урока: знать правила умножения чисел с разными знаками, умножение двух отрицательных чисел

Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n) iconПрограмма, реализующая операцию умножения извлечения квадратного...
Во второй части курсового проекта необходимо разработать микропрограмму извлечения квадратного корня для процессора на базе комплекта...

Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n) iconПрограммах в аннотация. В
Далее переходим к обсуждению как его искать, какие модели или представления программ полезны и ка­кие алгоритмы на них используются....

Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n) iconЧетвертый Информация для планирования, управления и измерения показателей функционирования
Быть оп­ределен при помощи оценивания общего объема реализации на рынке за отчетный период и умножения полученной оценки на целевую...

Алгоритмы умножения в кольцах gf(2)[X] и полях gf(2n) iconФ. Уоссермен Нейрокомпьютерная техника
В книге американского автора в общедоступной форме излагаются основы построения нейрокомпьютеров. Описаны структура нейронных сетей...

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции