Скачать 75.94 Kb.
|
АЛГОРИТМЫ УМНОЖЕНИЯ В КОЛЬЦАХ 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, задающий коэффициенты произведения полиномов.
В данном алгоритме используются обозначения: «⊕» - операция сложения восьми разрядных машинных слов по модулю 2 «T[X,Y]» - операция адресации по таблице умножения T. Метод КарацубыДанный метод умножения был предложен А. Карацубой в 1962. Основу метода составляет следующее соотношение: , где , ,. Это соотношение дает возможность определить рекурсивный алгоритм умножения. Вход: A,B – многочлены степени n-1 (если степени многочленов не совпадают, или не являются степенью двойки, то старшие разряды дополняются нулями до ближайшей степени двойки) Выход: С – многочлен степени 2*n-1, который является произведением многочленов A и B.
Для получения асимптотической оценки метода докажем следующее утверждение. Утверждение: пусть 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).
В алгоритме используются следующие обозначения: «<<�» - сдвиг в сторону старших разрядов на указанное количество разрядов, «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 смещений ненулевых элементов вектора В.
Алгоритм приведения с использованием предварительно заполненного списка сдвигов: Вход: вектор А, длины n, степень многочлена В, списки сдвигов l, t, длины m. Выход: вектор res длины n, задающий коэффициенты многочлена r(x)=A mod B.
В приведенных выше алгоритмах используются следующие обозначения: «<<�» - сдвиг в сторону старших разрядов на указанное количество разрядов, «deg(B)» - функция получения индекса старшего ненулевого разряда вектора-операнда, «<>» - логическая операция сравнения (если два операнда не равны, выражение принимает значение «истина»), «» - операция сложения по модулю 2, «>>» - операция сдвига в сторону младших разрядов, «&» - операция поразрядного логического «И», «~» - операция поразрядного логического отрицания. Данный алгоритм позволяет выполнять операцию приведения по модулю многочленов определённого вида (по модулю многочленов малого веса) за пренебрежимо малое, по сравнению с операцией умножения время. Контрольные вопросы:
Литература:
|
Уравнения и алгоритмы К 89 Кузьмин, Д. В. Моделирование динамики мехатронных систем. Уравнения и алгоритмы: монография / Д. В. Кузьмин. – Архангельск:... |
Методы и алгоритмы многокритериальной оПтимизации стандартных... Методы и алгоритмы многокритериальной оПтимизации стандартных ячеек в субмикронных технологиях проектирования сбис |
||
Заметки на полях "имени розы" заглавие и смысл Напоминаю у Абеляра пример "nulla rosa est"s использован для доказательства, что язык способен описывать и исчезнувшие и несуществующие... |
Литература: Е. А. Никулин, Компьютерная геометрия и алгоритмы машинной графики Реализовать алгоритм растеризации треугольника. (Залитый, по 2 координаты на вершину) |
||
Наска: гигантские рисунки на полях Приобщение к тайне Примерно в четырех с половиной сотнях километров к югу от Лимы, современной столицы Перу, и в сорока километрах от побережья Тихого... |
«Умножение положительных и отрицательных чисел» Цель урока: знать правила умножения чисел с разными знаками, умножение двух отрицательных чисел |
||
Программа, реализующая операцию умножения извлечения квадратного... Во второй части курсового проекта необходимо разработать микропрограмму извлечения квадратного корня для процессора на базе комплекта... |
Программах в аннотация. В Далее переходим к обсуждению как его искать, какие модели или представления программ полезны и какие алгоритмы на них используются.... |
||
Четвертый Информация для планирования, управления и измерения показателей функционирования Быть определен при помощи оценивания общего объема реализации на рынке за отчетный период и умножения полученной оценки на целевую... |
Ф. Уоссермен Нейрокомпьютерная техника В книге американского автора в общедоступной форме излагаются основы построения нейрокомпьютеров. Описаны структура нейронных сетей... |
Поиск на сайте Главная страница Литература Доклады Рефераты Курсовая работа Лекции |