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


 

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

27061. Состав бухгалтерской отчетности НКО 14.62 KB
  Состав бухгалтерской отчетности НКО Некоммерческие организации составляют и представляют отчетность установленную законодательными и нормативными актами для юридических лиц.14 Закона о бухгалтерском учете бухгалтерская отчетность организаций за исключением отчетности бюджетных организаций а также общественных организаций объединений и их структурных подразделений не осуществляющих предпринимательской деятельности и не имеющих кроме выбывшего имущества оборотов по реализации товаров работ услуг включает: Бухгалтерский баланс; ...
27062. Учет кассовых операций 14.76 KB
  Учет кассовых операций Порядок хранения расходования и учета денежных средств в кассе установлен Инструкцией Центрального банка РФ и Инструкцией по бюджетному учету № 174н. Для учета движения наличных денежных средств в валюте Российской Федерации и в иностранной валюте в кассе учреждения используют счет 020134000 Касса . Прием в кассу наличных денежных средств от физических лиц производится по бланкам строгой отчетности утвержденным в порядке предусмотренном законодательством Российской Федерации и Приходным кассовым ордерам ф. В случае...
27063. Учет расчетов с подотчетными лицами 14.33 KB
  Учет расчетов с подотчетными лицами Подотчетными суммами называются денежные авансы выдаваемые работникам учреждения из кассы на мелкие хозяйственные расходы и на расходы по командировкам. Аналитический учет расчетов с подотчетными лицами ведется в разрезе подотчетных лиц видов выплат и видов расчетов расчеты по выданным денежным средствам расчеты по полученным денежным документам в Карточке учета средств и расчетов либо в Журнале по расчетам с подотчетными лицами. Для учета расчетов с подотчетными лицами по суммам денежных средства и...
27064. Учет расчетов по недостачам 15.83 KB
  Учет расчетов по суммам выявленных недостач и хищений денежных средств и ценностей сумм потерь от порчи материальных ценностей и других сумм подлежащих удержанию и списанию в установленном порядке осуществляют на счете 020900000 Расчеты по недостачам . Учет расчетов по недостачам хищениям ведется в соответствии с КОСГУ на следующих счетах: 020971000 Расчеты по ущербу основным средствам ; 020972000 Расчеты по ущербу нематериальным активам ; 020973000 Расчеты по ущербу непроизведенным активам ; 020974000 Расчеты по ущербу материальных...
27065. Учет удержаний из заработной платы 16.39 KB
  Учет удержаний из заработной платы Счет 30403 Расчеты по удержаниям из выплат по оплате труда Счет предназначен для учета расчетов по удержаниям из заработной платы и денежного довольствия стипендий; безналичным перечислениям на счета во вклады сотрудников учреждения; взносам по договорам добровольного страхования; взносам на пенсионное страхование; суммам членских профсоюзных взносов; исполнительным листам и другим документам. Удержания производятся на основании соответствующих документов: письменных заявлений работников договоров...
27066. Учет расчетов с поставщиками и подрядчиками 12.95 KB
  Учет расчетов с поставщиками и подрядчиками Учет расчетов учреждения с поставщиками за поставленные материальные ценности и оказанные услуги с подрядчиками за выполненные работы осуществляют на счете 030200000 Расчеты с поставщиками и подрядчиками . Аналитический учет расчетов с поставщиками за поставленные материальные ценности оказанные услуги выполненные работы ведется в Карточке учета средств и расчетов либо в Журнале операций по расчетам с поставщиками и подрядчиками в разрезе кредиторов поставщиков продавцов подрядчиков...
27067. Учет бюджетных ассигнований и лимитов бюджетных обязательств 15.06 KB
  учет бюджетных ассигнований и лимитов бюджетных обязательств Счета предназначены для ведения учета учреждениями финансовыми органами показателей бюджетных ассигнований лимитов бюджетных обязательств сумм утвержденных сметой доходов и расходов по приносящей доход деятельности показателей по доходам поступлениям и расходам выплатам принятых учреждениями обязательств. По завершении текущего финансового года показатели остатки по счетам учета бюджетных ассигнований лимитов бюджетных обязательств текущего финансового года на следующий...
27068. Виды и формы бюджетной отчетности 16.13 KB
  Бюджетная отчетность предоставляется на бумажных носителях и или в виде электронного документа с представлением на электронных носителях или путем передачи по телекоммуникационным каналам связи в порядке установленном главным распорядителем бюджетных средств главным администратором доходов бюджета главным администратором источников финансирования дефицита бюджета финансовым органом органом казначейства и органом осуществляющим кассовое обслуживание с обязательным обеспечением защиты информации в соответствии с законодательством...
27069. Синтетический учет материальных запасов 16.14 KB
  Приобретение материальных запасов по фактической сформированной стоимости отражается по дебету соответствующих счетов аналитического учета счета 010500000 Материальные запасы 010531340 010536340 и кредиту счетов 030234730 Уменьшение кредиторской задолженности по приобретению материальных запасов 020834660 Уменьшение дебиторской задолженности подотчетных лиц по приобретению материальных запасов . Безвозмездное получение материальных запасов в том числе по централизованному снабжению распоряжению извещению отражается по дебету...