Центральный Дом Знаний - Алгоритм Берлекампа

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2688

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Алгоритм Берлекампа

Алгоритм Берлекампа, данный алгоритм предназначен для факторизации полиномов, позволяет разлагать полиномы на неприводимые сомножители. Алгоритм был разработан Элвином Берлекэмпом в 1967 году. Следует различать алгоритм Берлекэмпа и алгоритм Берлекэмпа — Мэсси, предназначенный для нахождения реккурентных зависимостей в последовательностях. 

Алгоритм состоит в основном из матрицы сокращения и вычисления многочлена НОД. В качестве входных параметров в алгоритме Берлекэмпа используются полином f(x) степени n над полем F, без повторяющихся множителей. На выходе получаем неприводимые множители на которые разлагается полином f(x). Все возможные множители полинома f(x) составляют кольцо:

R = \frac{\mathbb{F}_q[x]}{\langle f(x) \rangle}.

Алгоритм вычисляет полиномы g(x) \in R удовлетворяющие условию

g(x)^q \equiv g(x) \pmod{f(x)}.

Эти полиномы образуют алгебру R, также называемую алгеброй Берлекэмпа, которую можно рассматривать как n-мерное векторное пространство \mathbb{F}_q). Полиномы g(x) удовлетворяют условию:

f(x) = \prod_{s \in \mathbb{F}_q} \gcd(f(x),g(x)-s).

В общем случае не каждый НОД (gcd) в данной формуле будет нетривиальным множителем для f(x) Алгоритм Берлекэмпа позволяет находить мономы g(x), тем самым вычисляя базисные множители алгебры Берлекэмпа (R). Это возможно при рассмотрении алгебры Берлекэмпа как матрицы размером n \times n из \mathbb{F}_q что есть матрица полиномов, называемая \mathcal{Q}. Если \mathcal{Q}=[q_{i,j}] то qi,j — коэффициенты при j -й степени в выражении xiq mod f(x). То есть

x^{iq} \equiv q_{i,n}x^n + q_{i,n-1}x^{n-1} + \ldots + q_{i,0} \pmod{f(x)}

g(x) \in R Положим:g(x) = g_nx^n+g_{n-1}x^{n-1} + \ldots + g_0,  мы можем сопоставить вектор :g = (g_0, g_1, \ldots, g_n).  Нетрудно заметить, что вектор g\mathcal{Q} соответствует g(x)q modf(x). g(x) \in R тогда и только тогда, когда g(\mathcal{Q}-I)=0 (где I матрица размера n \times n) Вычислив матрицу \mathcal{Q}-I потом построим искомые полиномы g(x)

Лит.: Berlekamp, Elwyn R. (1967). «Factoring Polynomials Over Finite Fields». Bell Systems Technical Journal 46: 1853–1859. Later republished in: Berlekamp Elwyn R. Algebraic Coding Theory — McGraw Hill, 1968.

Loading

Календарь

«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24