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


 

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

27763. ПЕДАГОГИЧЕСКАЯ ЗАПУЩЕННОСТЬ 21.67 KB
  Изучение учащихся выявление трудных подростков и детей группы риска организация индивидуальной учебно воспитательной работы с ними. На этом этапе работы необходимо выявление трудных учащихся основных достоинств и недостатков их личности склонностей способностей интересов которые могут быть использованы для воспитания или перевоспитания подростков; изучение условий жизни и воспитания их в семье их ближайшего окружения личных связей организация учета трудных учащихся; планирование индивидуальной работы с ними проверка эффективности...
27764. Работа социального педагога в условия учреждения для детей-сирот и детей, оставшихся без попечения родителей 30.2 KB
  На основании выше перечисленного деятельность социального педагога детского дома строится по следующим направлениям: Защита материальных жилищных и социальных прав воспитанников определение социального статуса воспитанников оно предполагает лишение или ограничение родителей в родительских правах признание их через суд безвестно отсутствующими оформление инвалидности и гражданства воспитанникам; работа с документацией формирование личных дел воспитанников сбор недостающих в личном деле воспитанника документов и сведений о родителях...
27765. Дети улицы 21.39 KB
  Основными причинами формирования таких личностей являются: потеря родителей в результате несчастного случая когда ребенку своевременно не была оказана помощь службами опеки и попечительства; если ребенок брошен родителями; родители лишенные или находящиеся в процессе лишения родительских прав; жестокое обращение с ребенком в семье; агрессивная обстановка в семье создающая для ребенка дискомфорт и побуждающая его искать более благоприятные условия для самовыражения; одиночество ребенка отсутствие внимания к нему когда родители...
27766. Коррекция активно-волевых дефектов (слабоволие – причина многих отклонений поведения) 14.26 KB
  через насыщение любимым делом подойти к личному удовлетворению и к выполнению нелюбимой работы; соблюдение дозировки всякой работы и постепенное увеличение нагрузки на ребенка; интересно обставленный труд с желательным достижением поставленной цели и как следствие самовоспитание и самообладание; формирование стойкости и мужества перед естественными неудачами жизни. физическое воспитание: естественные движения подвижные игры танцетворчество физическое оздоровление и исправление слабости характера развитие выносливости выдержки...
27767. Функции социального педагога 18.81 KB
  Коррекционная: осуществление коррекции всех воспитательных влияний оказываемых на детей и подростков как со стороны семьи так и социальной среды в том числе и неформальной; усиление позитивных влияний и нейтрализация или переключение негативных влияний социальной среды. Социально профилактическая и реабилитационная: организация системы профилактических мер по предупреждению отклоняющегося девиантного и преступного делинквентного поведения детей и подростков; влияние на формирование нравственно правовой устойчивости; ...
27768. Педология 15.29 KB
  Несмотря на имевшиеся недостатки переоценивание роли биологических или социальных факторов в формировании ребенка использование технократических методов исследования отсутствие должного взаимодействия с другими науками педология внесла неоценимый вклад в развитие социальной педагогики. постановлением О педологических извращениях в системе Наркомпросов педология была объявлена лженаукой а педологи лжеучеными мракобесами и даже фашистскими прихвостнями и изгнаны из школы на них обрушились репрессии [4].
27769. Человек как жертва процесса социализации 17.19 KB
  Человек не только объект и субъект социализации. Это связано с тем что процесс и результат социализации заключают в себе внутреннее противоречие. Таким образом можно констатировать что в процессе социализации заложен внутренний до конца не разрешимый конфликт между степенью адаптации человека в обществе и степенью обособления его в обществе.
27770. Песталоцци 18.14 KB
  Передовая студенческая молодежь к которой принадлежал Песталоцци организовала кружок €œпатриотов€ находившийся под влиянием идей французских просветителей и в первую очередь Руссо. Цюрихские власти подвергли кратковременному аресту нескольких активных членов кружка в том числе и Песталоцци. Выйдя из тюрьмы Песталоцци не завершив своего образования поселился в деревне в имении Нейгоф чтобы организовать образцовое сельское хозяйство которое могло бы наглядно показать крестьянам как улучшить свое положение. Но этот утопический...
27771. Социальный педагог 16.1 KB
  Социальный педагог осуществляет социальнопедагогическую деятельность со всеми категориями населения: с детьми подростками молодежью взрослыми. Социальный педагог является связующим звеном между клиентом и его окружением посредником в системе взаимодействия личности семьи общества. или специализированных учреждениях отделение социальной помощи детский дом центр реабилитации социальный приют медикопсихологическая консультация телефон доверия центр занятости и трудоустройства и т.