7317

Розв’язування систем лінійних алгебраїчних рівнянь над скінченними полями

Лекция

Математика и математический анализ

Ю.Д. Жданова. Лекції з ВГПМ. М2 ТЧ обчислювальні алгоритми. Лекція № 7 10 Тема: Розв’язування систем лінійних алгебраїчних рівнянь над скінченними полями План лекції: Алгоритм знаходження всіх цілочислових розв’язків лінійного а...

Украинкский

2013-01-20

184.63 KB

14 чел.

Ю.Д.Жданова. Лекції з ВГПМ. М2 ТЧ обчислювальні алгоритми. Лекція № 7  10

Тема: Розв’язування систем лінійних алгебраїчних рівнянь

над скінченними полями

План лекції:

  1.  Алгоритм знаходження всіх цілочислових розв’язків лінійного алгебраїчного рівняння.
  2.  Алгоритм знаходження всіх цілочислових розв’язків довільної системи лінійних алгебраїчних рівнянь.
  3.  Алгоритм Відемана знаходження всіх розв’язків довільної системи лінійних алгебраїчних рівнянь над скінченним полем.

Системи лінійних алгебраїчних рівнянь над скінченними полями виникають в алгоритмах факторизації і дискретного логарифмування, що використовують факторні бази. В алгоритмах факторизації це розріджені системи лінійних рівнянь над полем . В алгоритмах дискретного логарифмування за простим модулем – це системи лінійних рівнянь над кільцем лишків , проте їх розв’язування зводиться до розв’язування систем лінійних рівнянь над скінченним простим полем.

Розглянемо алгоритми розв’язування системи лінійних алгебраїчних рівнянь над кільцем цілих чисел. За суттю ці алгоритми є узагальненнями алгоритму Евкліда.

1. Алгоритм знаходження всіх цілочислових розв’язків лінійного алгебраїчного рівняння

Розглянемо випадок, коли система складається з одного рівняння:

        (1)

де . Треба знайти всі розв’язки (1) в цілих числах .

Складемо матрицю

розмірності , в першому рядку якої стоять коефіцієнти рівняння (1), а під ними записана одинична матриця розмірності .

Алгоритм знаходження всіх цілочислових розв’язків лінійного алгебраїчного рівняння (1) полягає у наступних діях:

  1.  Вибираємо в першому рядку матриці найменший за абсолютною величиною ненульовий елемент .
  2.  Вибираємо номер такий, що .
  3.  Ділимо з остачею: , .
  4.  Віднімаємо з -го стовпця матриці  -й стовпець, помножений на .

В результаті цих дій вийде нова матриця , у якої на місці елементу з'явиться або 0 (якщо ), елемент, який буде менше модуля найменшого за абсолютною величиною ненульового елементу першого рядка у попередньої матриці .

Очевидно, що після декількох виконань дій 1-4 алгоритму, початкова матриця перетвориться на матрицю

,

де , . Якщо , то рівняння (1) не має розв’язків в цілих числах. Якщо ж , то загальний розв’язок рівняння (1) в цілих числах має вигляд

,

де , а вектори – це стовпці матриці .

Приклад. Розв’язати в цілих числах рівняння

.

Розв’язання. Складемо матрицю

Йдемо за алгоритмом знаходження всіх цілочислових розв’язків лінійного алгебраїчного рівняння:

Вибираємо в першому рядку матриці найменший за абсолютною величиною ненульовий елемент .

Ненульові елемент  і ділимо з остачею на :

 , .

Віднімаємо з 2-го стовпця матриці  1-й стовпець, помножений на –2, а з 3-го стовпця матриці  – 1-й, помножений на 1. В результаті цих дій вийде нова матриця , у якої на місці елементів і з'являться елементи, які будуть менше модуля елемента .

Повторюємо кроки алгоритму:

.

Оскільки , то загальний розв’язок заданого рівняння в цілих числах має вигляд

,

де , а вектори – це стовпці матриці . Покладаючи, наприклад, , знаходимо

.

Відповідь: .

Перевірка: .

2. Алгоритм знаходження всіх цілочислових розв’язків довільної системи лінійних алгебраїчних рівнянь

Розглянемо довільну систему лінійних алгебраїчних рівнянь , або

  (2)

де . Треба знайти всі розв’язки системи (2) в цілих числах .

Складемо матрицю системи розмірності і матрицю розмірності , в якій під матрицею стоїть одинична матриця розмірності , а під стовпцем , протилежним стовпцю вільних членів, стоїть нульовий стовпець розмірності :

,

Над першими стовпцями матриці (над першими рядками) можна робити наступні дії:

  1.  Переставляти;
  2.  Віднімати з одного стовпця (рядка) інший, помножений на ціле число.

В результаті цих дій матриця буде перетворена до частково-трикутного вигляду :

  

при деякому , , і ,…,. Елементи – перестановка елементів , яка виникла при перестановці перших рядків матриці .

Щоби привести матрицю до вигляду , треба спочатку в першому рядку матриці без останнього елемента обнулити всі елементи, крім одного (як в попередньому алгоритмі), а потім стовпець, який містить цей ненульовий елемент, поставити на перше місце. Потім так само обійтися з другим рядком отриманої матриці (без першого стовпця) і т.д.

Після того, як матриця побудована, її треба перетворити до вигляду:

 

Для цього треба помножити перші стовпців матриці на цілі числа і послідовно додати їх до останнього стовпця. Точніше, спочатку треба додати перший стовпець , помножений на число , яке повинно бути цілим, до останнього стовпця і отримати 0 в першому елементі -го стовпця. Потім за допомогою другого стовпця і елемента отримати 0 в другому елементі -го стовпця і т.д.

Якщо перехід від матриці до матриці неможливий, то система (2) не має розв’язків в цілих числах. Якщо ж матрицю знайдено, то загальний розв’язок системи (2) в цілих числах має вигляд:

,

де .

Приклад. Розв’язати в цілих числах систему лінійних алгебраїчних рівнянь

Розв’язання. Складемо матрицю системи

і матрицю розмірності , в якій під матрицею стоїть одинична матриця розмірності :

Перетворимо матрицю до частково-трикутного вигляду. Спочатку переставимо перший і другий рядки.

Вибираємо в першому рядку матриці найменший за абсолютною величиною ненульовий елемент . Йдучи за попереднім алгоритмом знаходження всіх цілочислових розв’язків лінійного алгебраїчного рівняння, будемо мати

    

Перетворимо матрицю :

 

  

Розв’язок системи в цілих числах має вигляд:

.

Отримали точний розв’язок, тому що матриця системи квадратна і невироджена.

3. Алгоритм Відемана знаходження всіх розв’язків довільної

системи лінійних алгебраїчних рівнянь над скінченним полем

Нехай треба розв’язати систему лінійних алгебраїчних рівнянь

 ,      (3)

над скінченним полем . Припустимо, що матриця розряджена, квадратна порядку і невироджена.

Матриця задає невироджене лінійне відображення (яке ми також позначаємо ) на просторі . Розглянемо простір , породжений множиною векторів , і покладемо – лінійне відображення на . Позначимо – мінімальний многочлен , тобто ненульовий многочлен найменшого степеня, такий, що – нульове відображення . Ми вважаємо нормалізованим таким чином, що його вільний член дорівнює 1. Відзначимо, що якщо , то – нульове відображення тоді і тільки тоді, коли . Крім того, ділить многочлен , і тому .

Позначимо , , де – коефіцієнти . Якщо ми зможемо знайти , то знайдемо і розв’язок системи (3): оскільки і , то

      (4)

Нехай – деякий фіксований вектор з ; (·, ·) – стандартне білінійне відображення в ,

  .

Оскільки , то послідовність

    ,     (5)

задовольняє лінійному рекурентному співвідношенню, характеристичний многочлен якого дорівнює . Нехай – мінімальний многочлен для послідовності (тобто характеристичний многочлен найкоротшого рекурентного співвідношення). Тоді . Дійсно, якщо ми поділимо з остачею

 ,   ,

то з рівностей

 ,

 ,

і мінімальності випливає, що . Оскільки вільний член дорівнює 1, ми можемо вважати, що і вільний член дорівнює 1.

Мінімальний многочлен для послідовності (5) може бути побудований за допомогою алгоритму Берлекемпа-Мессі за першими її членами. Тому можливий наступний метод розв’язування (3): вибрати випадковий вектор , побудувати і в припущенні, що , знайти за формулою (4).

Розглянемо інший підхід до розв’язування (3). Нехай , для деякого вектора . Якщо вектор , то ми знаходимо за формулою (4) (оскільки тоді ). Якщо ж , то повторюємо процедуру, тобто вибираємо випадковий вектор і будуємо мінімальний многочлен для послідовності . Якщо , то і ми знаходимо розв’язок за формулою (4), інакше вибираємо вектор і так далі.

Формалізуємо сказане у вигляді алгоритму 1. Для довільного многочлена ми будемо позначати .

Алгоритм 1.

1 крок. Присвоїти ,, , .

2 крок. Якщо , то розв’язок (3) дорівнює , і алгоритм завершує роботу.

3 крок. Вибрати випадковий вектор , .

4 крок. Обчислити перші членів послідовності , .

5 крок. За допомогою алгоритму Берлекемпа-Месси обчислити мінімальний многочлен послідовності кроку 4, нормалізований так, щоб його вільний член дорівнював одиниці.

6 крок. Присвоїти

,

,

.

7 крок. Присвоїти і повернутися на крок 2.

Кінець алгоритму.

Тепер опишемо детермінований алгоритм 2.

Алгоритм 2.

1 крок. Обчислити , .

2 крок. Присвоїти , .

3 крок. Присвоїти (одиниця стоїть на( k + 1)-му місці).

4 крок. Використовуючи результати 1-го кроку, обчислити послідовність ,

5 крок. Обчислити послідовність

, .

(тут можна використовувати дискретне перетворення Фур'є).

6 крок. Знайти (за допомогою алгоритму Берлекемпа-Мессі) мінімальний многочлен для послідовності, отриманої на5-му кроці (вільний член дорівнює 1).

7 крок. Присвоїти .

8 крок. Присвоїти . Якщо і , то йти на крок 3.

9 крок. Для многочлена за допомогою знайдених на 1 кроці значень знайти розв’язок системи (3) за формулою (4).

Зауваження. Алгоритм 2 працює так само як алгоритм 1, тільки вектори обираються не випадково, а за допомогою перебору одиничних векторів .


 

А также другие работы, которые могут Вас заинтересовать

47172. Ремонт поверхностей деталей. Способ дополнительных ремонтных деталей, способ замены части детали. Ремонт корпусных деталей 73.28 KB
  Способ дополнительных ремонтных деталей способ замены части детали. Ремонт корпусных деталей. В ремонтной практике применяют несколько способов восстановления деталей.
47173. Возникновение Австро-Венгрии 73.5 KB
  Административнотерриториальное деление Цислейтания земли австрийской короны королевства: Богемия Далмация Галиция и Лодомерия; эрцгерцогства: Нижняя Австрия Верхняя Австрия; герцоргства: Буковина Каринтия Крайна Зальцбург Штирия Верхняя и Нижняя Силезия; маркграфства Моравия Истрия; княжеские округа: Тироль Горица и Градишка; земля Форарльберг; Австрийское Приморье; город Триест Транслейтания земли венгерской короны королевства: Венгрия Хорватия и Славония; город Фиуме Босния и Герцеговина с 1908 года ...
47174. Информационное обеспечение менеджмента 73.5 KB
  Инвестиции: определение виды Инвестиции в объекты предпринимательской деятельности осуществляются в различных формах. По объектам вложения денежных средств выделяют реальные и финансовые инвестиции. Реальные инвестиции авансирование денег в материальные и нематериальные активы. Финансовые инвестиции вложения средств в ценные бумаги: долевые акции и долговые облигации.
47175. Ймовірність складних подій 73.5 KB
  Знайти: а імовірність того що деталь яку вилучили з третоьго ящика буде стандартною; б імовірність того що деталь яку вилучили з третього ящика належала першому ящику коли вона виявилась стандартною.93856 Задача 6 1 деталь 1 деталь а Для розвязання цієї задачі скористаємося формулою повної ймовірності. Позначимо через А подію “з третього ящика вилучена стандартна детальâ€. Шукана ймовірність того що з третьої...
47177. Профессиональные объединения издателей. Международная роль ассоциаций. Специализированные ассоциации 74.5 KB
  Профессиональные объединения издателей На Западе ассоциации союзы занимают важное место в общей системе издательского дела. Вопросов которыми занимаются ассоциации издателей довольно много: осуществление связи с правительственными органами имеющими отношение к книгоизданию представительство интересов издательского дела как отрасли перед правительством; осуществление связей с книготорговой и полиграфической отраслями с профессиональными объединениями книготорговцев и полиграфистов; разработка юридических вопросов касающихся...
47178. КЛЕТКА КАК ОТКРЫТАЯ СИСТЕМА 74.5 KB
  Для поддержания сложной динамической структуры живой клетки требуется непрерывная затрата энергии. Так же энергия необходима для осуществления большинства функций клетки. Различают: Анаболизм ассимиляция эндотермический процесс уподобления поступающих в клетку веществ веществам самой клетки.
47179. Субъекты и объекты природопользования 74.68 KB
  Бринчука 1 может выступать в двух основных качествах: а как возможный по закону обладатель такого права пользования и б как обладатель субъективного права пользования природными ресурсами носитель установленных законом прав и обязанностей который является субъектом правоотношений пользования землей ее недрами водами и лесами объектами животного мира и атмосферным воздухом. В качестве субъекта права общего природопользования выступают граждане Российской Федерации иностранцы и лиц без гражданства поскольку они обладает...