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


 

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

24345. Экологическая этика и ее философские основания. Философия русского космизма. Учение о ноосфере 113.5 KB
  Что касается космистского мировоззрения то оно главным предметом своего познавательного и ценностного отношения делает взаимодействие человека и среды последняя понимается чаще всего как Космос. Спирин русский космизм как универсалистский тип миросозерцания отражающий бытие мира и человека в их единстве в нерасторжимой взаимосвязи микрокосма человека и микрокосма природы Казначеев В. Космопланетарный феномен человека: проблемы комплексного изучения. Хотя русский космизм внутренне исключительно разнообразен и включает полярные по...
24346. Сциентизм и антисциентизм как мировоззренческие позиции о роли науки в развитии общества. Наука и паранаука 95 KB
  В современной культуре отчетливо проявила себя дилемма: сциентизмантисциентизм что имеет непосредственное отношение к проблеме соотношения науки и искусства. Для сциентизма характерно преувеличение роли науки в познании окружающего мира и человека объявление ее вершиной развития культуры убеждение в ненужности других сфер культуры О. Противоположным сциентизму направлением мировозренческой ориентации является антисциентизм основанный на недоверии к возможностям науки и разума на критике научных методов познания.
24347. Роль науки в преодолении современных глобальных кризисов (экологический, энергетический, демографический, угроза локальных и ядерных воин) 141 KB
  Она представляет собой не просто окружающую среду которую можно рассматривать как поле для преобразующей деятельности человека а выступает единым целостным организмом в который включено человечество в качестве специфической подсистемы. Деятельность человека вносит постоянные изменения в динамику биосферы и на современном этапе развития техногенной цивилизации масштабы человеческой экспансии в природу таковы что они начинают разрушать биосферу как целостную экосистему. Третья проблема – это проблема сохранения человеческой личности...
24348. Развитие науки как социального института (признаки, функции). Научные сообщества и их исторические типы 105.5 KB
  175 184 Понятие науки как социального института Научноисследовательская деятельность в обществе носит упорядоченный организованный характер. Цель и назначение науки как социального института – производство и распространение знания разработка средств и методов исследования воспроизводство ученых и обеспечение выполнения ими своих социальных функций. В социологии в зависимости от методологических установок сформировались различные подходы к пониманию науки как социального института.
24349. Научные школы (функции, признаки, типы). Историческое развитие способов трансляции научных знаний (от рукописей до современного комп.) 142 KB
  Научные сообщества и их исторические типы: невидимый колледж научные школы. Другой распространенной формой неформального объединения ученых играющих заметную роль в развитии науки являются научные школы. В содержательном плане чаще всего для сторонников научной школы характерен особый подход к проблемам и методам познания.
24350. Наука и экономика (сущность научно-технического прогресса экономика как наука, экономика науки) 87 KB
  Инновационная экономика Одной из важных сфер функционирования науки как социального института является экономика. Термин экономика многозначен и включает в себя по крайней мере два класса явлений: а экономику как отрасль науки изучающую экономические отношения и народное хозяйство; б экономику как различные виды и отрасли производства народное хозяйство страны мирового сообщества отношения в этих сферах по поводу производства распределения и обмена. Непосредственная связь науки и экономики проявляется в экономике как научной...
24351. Наука и власть (политология, политизация науки и проблемы управления наукой) 122 KB
  При рассмотрении проблемы взаимоотношения науки и власти следует имеет в виду два вектора анализа: а воздействие государственной власти на науку; б влияние науки на власть государственную политику. Под научной политикой понимается деятельность государственных учреждений по развитию управлению контролю финансированию науки. Государство выступает по отношению к науке в следующих основных функциях: как законодатель устанавливающий правовые основы функционирования науки в обществе в целом и конкретные нормы регулирования его...
24352. Теория и практика. Критерии истинности познания. Научная истина 98.5 KB
  Мы исходим из установки что наши знания это не абсолютные истины но рабочие гипотезы которые мы готовы сменить отбросить если они противоречат новым фактам. б Понятие истины. Объективность истины. Диалектика абсолютной и относительной истины Важную роль в обосновании принципа доверия к субъекту имеет обоснование возможности достижения объективной истины.
24353. Создание новой базы данных 9.79 MB
  Access хранит все таблицы базы данных, а также другие объекты в одном файле. Прежде, чем приступить к созданию таблиц базы данных, необходимо создать файл пустой базы данных.