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, тільки вектори обираються не випадково, а за допомогою перебору одиничних векторів .


 

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

48127. ОСНОВИ ЕТИКИ 1.18 MB
  Тим часом чим гостріші проблеми постають перед нами чим непевне ніші перспективи на майбутнє тим невідворотніше прагнення сучасної людини знайти якийсь твердий грунт піл ногами те заради чого варто було б жити. Предметом виступають моральноетичні аспекти світогляду сучасної людини. Науку про етичні чесноти особистісні якості достоїнства характеру людини Аристотель назвав ethice {етика. За аналогією у латинській мові від терміна mos moris крій одягу й мода звичай і порядок вдача і характер людини давньоримський...
48128. Основи менеджменту та маркетингу 1.28 MB
  Поняття про організації. Всі організації мають загальні характеристики. 1 всі організації використовують чотири основних види ресурсів: людські ресурси; фінансові ресурси; фізичні ресурси сировина устаткування тощо; інформаційні ресурси. розподіл праці в організації.
48129. ОСНОВИ НАУКОВИХ ДОСЛІДЖЕНЬ 954 KB
  У студентів має сформуватися система знань про загальнонаукові і специфічні методи наукового дослідження основні категорії і принципи наукового пізнання. Метою вивчення дисципліни є формування у студентів системи знань про загальнонаукові і специфічні методи наукового дослідження про основні категорії і принципи наукового дослідження закріплення поглиблення розширення і систематизація знань отриманих під час аудиторних занять; самостійне оволодіння новим навчальним матеріалом формування умінь і навичок самостійної розумової праці...
48130. Реклама і звязки з громадськістю 655.5 KB
  Очевидно, що діяльність зі звязків з громадськістю передбачає багатосторонню та складну роботу, що вимагає від фахівців в цій області широкого комплексу знань і навичок
48132. Теорія держави і права 1.45 MB
  Відомо, що держава існувала не завжди, а її утворенню передував первіснообщинний устрій, який являв собою стародавній тип колективного виробництва і був результатом слабкості окремої людини перед навколишнім природним середовищем. З моменту виникнення колективної праці труд окремої людини стає частиною спільної праці всього колективу общини, яка по суті була економічною формою організації людей
48133. Держава і право 892 KB
  Основи конституційного права України 6 Загальна характеристика конституційного права як провідної галузі права України 2 2 7 Правовий статус особи в Україні 8 Конституційноправові форми народовладдя в Україні 2 9 Конституційна система органів державної влади України. Окремі галузі права 10 Цивільне та сімейне право України 6 2 11 Основи трудового права 2 12 Основи адміністративного права України 2 2 13 Основи кримінального права 2 Всього 22 10 Лекція 2. Після проголошення незалежності України 1991 р. концепція громадянського суспільства...
48134. ОСНОВЫ ПРАВА 2.29 MB
  Это провозглашено в качестве важнейшей основы конституционного строя Республики Беларусь и должно найти отражение при изучении основ права. В отличие от других социальных идей и политических ориентаций демократическое правовое государство при верховенстве правового закона и приоритете прав человека и гражданина практически воспринято обществом как будущее конституционного строя Республики Беларусь. Целью преподавания дисциплины Основы права является изучение системы законодательства Республики Беларусь ознакомление с важнейшими...
48135. Основные виды гражданско-правовых договоров 209.5 KB
  С другой стороны договор розничной куплипродажи наиболее распространенный вид договора куплипродажи. 396 ГК а также часто может позиционироваться в качестве договора присоединения ст. Элементы договора розничной куплипродажи. Необходимость приобретения товаров предназначенных для использования в предпринимательской деятельности может быть обеспечена посредством заключения договора поставки где покупателем является лишь субъект предпринимательства.