Алгоритмы умножения в gf(2n) и gf(pn) - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Алгоритмы умножения в gf(2n) и gf(pn) - страница №1/1

Алгоритмы умножения в GF(2n) и GF(pn)


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

Описание исследуемых алгоритмов в GF(2n):

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


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

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

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

  1. res:=0

  2. i:=0

  3. пока i

    1. j:=0

    2. пока j<n/8

      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 зависит от типа используемой в вычислениях машины, частоты процессора, объема и скорости оперативной памяти и размера кэша.

Классический алгоритм приведения


По определению привести многочлен 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:=resB

    2. B:=B>>1

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

    1. res:=resB


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

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

«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<m

      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<m

    1. если tj<=0





    2. иначе





    3. j:=j+1

  7. Ai:=Ai&(~mask)


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

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

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

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

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

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

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

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

Переход к алгоритмам в GF(2n)


Для перехода к реализации операции умножения над полем GF(pn), где 2
(1),

где ai – коэффициенты при соответствующих степенях x. Положим k – количество элементов поля GF(p), которые могут быть расположены в одном машинном слове. Обозначим l – количество бинарных разрядов, которые необходимы для представления одного элемента поля GF(p), тогда l=log2p. И m – количество бинарных разрядов в машинном слове. Тогда, k=m/l, например, в случае 8 разрядного машинного слова при реализации операций в GF(3), k=4, а при реализации операций в GF(7), k=2. Таким образом, для умножения в GF(pn) используются те же алгоритмы умножения в GF(2n), при этом все элементарные операции над многочленами в GF(pk), где log2p*k≤8, табулируются. Необходимость табулирования элементарных операций в GF(p) накладывает существенные ограничения на размер машинного слова m. Так для выполнения операции сложения или вычитания двух 8 разрядных машинных слов, необходима таблица размером в 65К, а для умножения 128К. Дальнейшее увеличение размера машинного слова не имеет смысла т.к. для выполнения операции сложения двух 16 разрядных машинных слов требуется таблица размером в 4ГБ, что неприемлемо. Однако для некоторых элементарных операций, таких, как обнуление и присваивание возможно использование машинных слов большего размера.


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


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

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

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

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

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

  6. Каково ограничение на характеристику поля в рассматриваемой реализации?

Литература:


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

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

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