Как решить систему уравнений в кольце

Алгоритм решения систем линейных уравнений в кольцах вычетов

Алевтина Шахова 6 лет назад Просмотров:

1 Авдошин С.М., Савельева А.А. Алгоритм решения систем линейных уравнений в кольцах вычетов Разработан эффективный алгоритм решения систем линейных уравнений в кольцах вычетов [], эквивалентный по сложности известному алгоритму решения систем в полях Галуа ([2], [4]). Приведены результаты сравнительного анализа предложенного алгоритма и существующих аналогов ([3], [0], [8]) на основе асимптотической оценки их временной сложности. Показано, что разработанный метод является корректным и существенно снижает трудоемкость алгоритмов дискретного логарифмирования. Введение Объектом исследования данной работы являются методы решения систем линейных уравнений в кольцах вычетов. Такие системы возникают в алгоритмах факторизации и дискретного логарифмирования (см., например, метод Диксона, алгоритм Копперсмита-Одлыжко-Шреппеля «COS» и алгоритм решета числового поля в [3]). Частным случаем колец вычетов являются поля Галуа, т.е. кольца вычетов по модулю простых чисел. Методы решения систем в таких полях известны (см., например, метод Гаусса (последовательного исключения) в [2, с.89], [4, с.42]). Модификацией метода Гаусса является метод Жордана. Однако для решения систем линейных уравнений в кольцах вычетов эти методы, вообще говоря, неприменимы. Проиллюстрируем сказанное. Рассмотрим систему линейных уравнений: 26x+ 3y = 4 () 9x+ 34y = в поле Галуа Z 37 и в кольце вычетов Z 36. В соответствии с методом Жордана требуется с помощью элементарных преобразований над строками привести матрицу к единичной. Для получения единичного элемента на диагонали в поле действительных чисел используется деление на число a, равное ведущему элементу; аналогом этой операции в кольце вычетов является умножение на элемент, обратный к a. Обратный элемент по модулю можно найти как решение уравнения: ax (mod ) (2) Для его вычисления используется расширенный алгоритм Евклида (см. [7, с. 744], [0, с.227]). На рис. приведено описание этого алгоритма. Если a и — взаимно простые числа, т.е. НОД( a, ) = = ax + y, то 2 ; в противном случае коэффициент Безу x является решением уравнения ( ) уравнение ( ) 2 не имеет решения и элемент a необратим в кольце Z. Как показано в [7, с.743], время работы алгоритма Евклида при вычислении НОД ( ab, ), где a > b 0, составляет O(log b ). Тогда

2 сложность операции вычисления обратного элемента в кольце Z можно оценить как O(log ). Метод Жордана с учетом алгоритма Евклида имеет временную сложность O( n ( n m+ log ) ) для системы n уравнений с m неизвестными в Z. Евклид( ab, ). d x y a 0 n r s b 0 2. c d / n 3. d x y 0 d x y n r s c n r s 4. ЕСЛИ n > 0 5. ТО перейти к шагу 2; 6. ИНАЧЕ вернуть( d, x, y, r, s ) Рис. В результате вычислений, приведенных ниже, получаем решение системы в поле Галуа Z 37 : x = 6, y = 23. [] [] ( 26 = 0 ) 30 3 [2] [] [2] [] 30 3 [2] ( 23 = 29 ) 30 3 [] [2] [2] Однако в кольце вычетов по модулю = 36 система () не может быть решена ни с помощью метода Жордана, ни с помощью метода Гаусса, поскольку все коэффициенты при неизвестных являются делителями нуля ([9, с.75]) и, следовательно, не является обратимыми. Таким образом, получить единичный элемент на диагонали умножением на какой-либо элемент кольца невозможно. Тем не менее, конечность области определения позволяет убедиться в том, что решение данной системы в Z 36 существует ( x = 7, y = 22), и притом единственно. Для решения систем линейных уравнений в кольцах вычетов необходимы специальные методы. Обзор существующих методов Анализ методов решения систем линейных уравнений в кольцах вычетов, описанных в современной литературе, выявил ряд недостатков, которые затрудняют использование этих алгоритмов на практике. В монографии [3] задача сводится к решению систем линейных уравнений над полями Галуа. Пусть

3 где систем t q α = m = ( ) ax b(mod ), i=, n 3 i i =, тогда решение системы ( ) m = 3 сводится к решению семейства ( ) ax b(mod q α ), i=, n, =, t 4 i i где неизвестные значения x (mod q α ) для фиксированного представляются в виде α α x x + x q x q (mod q ), 5 0, α Здесь 0 xl q, l = 0, α. Редуцируя систему ( 4 ) к модулю q, получаем систему уравнений: над полем Галуа виде ( ) q m = 5 с известными i0 поделив на i 0 ax b(mod q), i=, n ( ) Z. Если мы найдем все x,, 0 = m, то, подставляя x в x в систему ( ) 4, редуцируя ее к модулю q, мы получим систему линейных уравнений над полем 2 q и затем относительно неизвестных x,, = m, и т.д. В конечном счете, найдя значение x (mod q α ) для всех, мы восстановим x (mod ) по китайской теореме об остатках (см. [0, с.420]). 2 2 В нашем примере = 36 = 2 3, т.е. для решения одной системы в кольце вычетов придется решить 4 системы над полями Галуа. Но основным недостатком метода является необходимость разложения на множители числа : вопрос о существовании алгоритма факторизации с полиномиальной сложностью является одной из открытых проблем современной теории чисел. Другой метод предполагает сведение системы линейных уравнений в кольце вычетов к системе линейных диофантовых уравнений. При помощи одного из известных алгоритмов (см. [3] или [0]) расширенная матрица системы ( A b ) приводится к ступенчатому виду ( A b ) и вычисляется правая матрица перехода R размером ( m+ ) ( m+ ), такая, что: ( A b) R = ( A b ). На основании матрицы R можно получить общее решение системы. Проиллюстрируем применение данного способа на примере. Система линейных диофантовых уравнений, соответствующая системе ( ) в Z 36, имеет вид: 26x+ 3y+ 36v = 4. 9x+ 34y + 36v2 = Ее общее решение в кольце целых чисел: Z q

4 x = t t (-2492) y = t0 (-324) + t 5688, t0, t Z v = t0 (-857) + t 5048 v2 = 0 + t0 0 + t Редуцируя результат к модулю 36, получаем: x = 7, y = 22. Однако при решении систем линейных уравнений в кольцах вычетов наблюдается экспоненциальный рост длины коэффициентов. Так, в нашем примере коэффициенты исходной матрицы ограничены числом 36, тогда как в 6 целых числах мы получили общее решение с коэффициентами

0. Заметим, что этот результат соответствует системе в кольце вычетов, состоящей всего лишь из двух уравнений с двумя неизвестными. Для того, чтобы избежать экспоненциального роста длины коэффициентов, разработаны специальные методы решения систем линейных алгебраических уравнений над кольцом целых чисел, такие как модификация метода Гаусса и построение нормальной диагональной формы Смита (см. [8, с. 8]). Несмотря на то, что эти алгоритмы являются полиномиальными, их сложность существенно превышает сложность алгоритма Гаусса при решении систем в полях Галуа. Так, для системы из n уравнений с n неизвестными, коэффициенты которой по абсолютной величине не превосходят α, временная сложность модифицированного алгоритма Гаусса при использовании самого быстрого алгоритма умножения составляет O( n 4 (log α + log n ) ). Трудоемкость построения нормальной диагональной формы Смита матрицы 2 O n m 2 logα. A, где a α, i, n,, m n m i = =, ограничена величиной ( ) Метод решения систем линейных уравнений в кольцах вычетов, предлагаемый в данной работе, лишен недостатков вышеописанных алгоритмов и показал свою эффективность при программной реализации. Описание метода В основе разработанного метода лежит преобразование строк матрицы с использованием коэффициентов Безу, которые позволяет вычислить расширенный алгоритм Евклида (см. рис.). В результате работы алгоритма получаем: НОД ( ab, ) = d= a x+ b y, 0 = n = a r+ b s. a = 26 = a, b= 9 = a : НОД (26, 9) = = 26 ( ) + 9 (3), 0= 26 (9) + 9 ( 26). При 2 Применяя к -й и 2-й строке расширенной матрицы системы () преобразования, соответствующие преобразованиям алгоритма Евклида над поступающими на его вход коэффициентами a = 26 и a 2 = 9, в результате мы получаем матрицу, строчно эквивалентную исходной (см. [5, с.27]):

5 [] [] [2] [] [2] 9 34 [2] [] 9 34 [] [2] [] [2] [2] [] [] [2] [] [2] [2] В полученной матрице: A(, ) x y A(, ) = A(2, ) r s A(2, ), где x, y, r, s удовлетворяют условию: НОД ( a, a2) = a x + a2 y, 0 = a r + a2 s (запись A(, ) используется для обозначения -й строки расширенной матрицы A). Коэффициенты Безу x =, y = 3, r = 9, s = 26 можно получить, оперируя лишь коэффициентами a и a 2. Тогда цепь преобразований ( 6 ) сводится к одному преобразованию следующего вида: [] [] =[] 35 + [2] [2] =[] 9 + [2] 0 [2] С учетом того, что коэффициент a 22 = 7 обратим в Z 36 : 7 3(mod36), преобразуем матрицу к единичной и получаем решение: [] [] =[] + [2] [2] =[2] 3 [2] В общем виде алгоритм решения систем линейных уравнений в кольцах вычетов, представляющий собой модификацию метода Жордана, описан на рис.2. Доказательство корректности Предложенный алгоритм является корректным, т.е. полученная в результате преобразований система равносильна исходной (иначе говоря, решения системы не теряются и новые решения не появляются). 3 в матричном виде: Запишем систему уравнений ( ) Ax = b ( 7) Тогда по теореме о равносильности систем линейных уравнений: Если U — обратимая ( n n) коммутативное кольцо с единицей), тогда система уравнений ( ) системе ( UA) x = Ub. (Доказательство см. в [5, с.58]). Следствие из этой теоремы: ( 6) -матрица над R (R — произвольное 7 равносильна Если матрицы ( A, b ) и ( C, δ ) строчно эквивалентны, то система уравнений ( 7 ) равносильна системе Cx = δ.

6 Поскольку преобразования матрицы в описанном модифицированном методе Жордана базируются на элементарных преобразованиях строк (элементарными преобразованиями строк матрицы с элементами из коммутативного кольца с единицей называют (см. [6, с.85]) умножение любой ее строки на обратимый элемент кольца; прибавление к любой ее строке другой строки, умноженной на произвольный элемент кольца; транспозицию строк), то полученная на выходе алгоритма матрица строчно эквивалентна исходной (см. Модиф _ Жордан( A ). n Число _ Строк( A) 2. i 3. ДЛЯ = i+, n ЦИКЛ 4. НОД ( aii, ai ) = aii x + ai y ВЫЧИСЛИТЬ x, y, r, s : 0 = aii r + ai s 5. Ai (, ) x y Ai (, ) A(, ) r s A(, ) 6. ЕСЛИ коэффициент a ii необратим в Z 7. ТО выйти из алгоритма <матрица вырождена>8. ИНАЧЕ <обнуляем все элементы i го столбца выше ведущего>9. A(, i ) A(, i ) a ii 0. A(, ) A(, ) A( i, ) ai, =, i. i i+ 2. ЕСЛИ i n 3. ТО перейти к шагу 2; 4. ИНАЧЕ вернуть( A) [5, с.27]). Тогда приведенному выше следствию соответствующие системы уравнений являются равносильными. Что и требовалось доказать. Оценка сложности Предложенный алгоритм обладает временной сложностью ( ( log )) Рис.2 O n nm+ для системы в кольце вычетов по модулю, в которой n — число уравнений системы, m — число неизвестных. Для получения этой формулы воспользуемся оценкой временной b сложности алгоритма Евклида T( a, b) = O + logϕ НОД ( a, b), где a > b 0, ϕ = ( + 5) 2 (доказательство этой оценки предлагается в [7, с.745], в качестве упражнения). На каждом -м шаге процедура, реализующая алгоритм Евклида, вызывается раз: первым параметром является текущее значение ведущего

7 элемента, в качестве второго на вход последовательно подаются ai ( i = +, n) и. Пусть di — значение ведущего элемента на i -й итерации цикла: d0 = a, d = НОД ( a, a+, ) = НОД ( d0, a+, ). d = НОД ( d, a ). d = НОД ( d, a ). +, n n n, Тогда число операций оценивается неравенством: n < di ai, >min, + log ( n ) + log НОД ( d, a ). i= i i, Помимо этого, на каждом -м шаге над элементами матрицы производится порядка 2( n )( m+ ) 2nm операций. Число шагов алгоритма для системы равно n. Получаем временную сложность алгоритма: n ( ) ( ). Tn (, ) = 2 nm+ ( n ) + log On ( nm+ log ) = Заключение В заключение приведем сравнительный анализ временной сложности предложенного алгоритма и алгоритмов, описанных в современной литературе, для системы n уравнений с m неизвестными в кольце вычетов Z ( t q α = = ). Алгоритм Модифицированный метод Жордана Метод сведения к полям Галуа* Метод сведения к диофантовым уравнениям (с построением матрицы Смита) Временная сложность ( ( + log )) O n nm t O n ( n m α + log ) + ln lnln e = 2 O n m 2 log р ( ) ln ln ln *Оценка временной сложности этого метода дана при условии использования для разложения на множители числа наиболее эффективного на сегодняшний день (см. [7, c.779]) алгоритма «квадратичного решета» () Померанца, имеющего временную сложность L ( ) + o ln ln ln, где L ( ) e =.

8 Список литературы. Авдошин С.М., Савельева А.А. Свидетельство об официальной регистрации программы для ЭВМ : «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ Ван дер Варден Б.Л. Алгебра. — М.: Наука, с. 3. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, с. 4. Гантмахер Ф.Р. Теория матриц. Гостехиздат, с. 5. Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра: Учебник. В 2-х т. Т. I — М.: Гелиос АРВ, с. 6. Джекобсон Н. Теория колец (Перевод с английского Н. Я. Виленкина). М.: Государственное издательство иностранной литературы, с. 7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, с. 8. Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. Нижегородский Государственный Университет им. Н.И. Лобачевского. htt:// с. 9. Курош А.Г. Теория групп (Издание третье, дополненное). М.: «НАУКА», Главная редакция физико-математической литературы, с. 0. Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. — М.: Мир, с.

Полукольца и системы линейных уравнений

Полученные в предыдущих лекциях результаты можно распространить на системы линейных уравнений вида

где все элементы и , суть элементы некоторого замкнутого полукольца, и речь идет о решении системы (3.16) в этом полукольце.

Для этого введем в рассмотрение множество прямоугольных матриц типа с элементами из произвольного идемпотентного полукольца . Множество всех квадратных матриц порядка с элементами из полукольца обозначим . Через обозначим множество всех матриц любого типа с элементами из .

Операции сложения и умножения матриц определяют точно так же, как и в числовом случае, — с учетом того, что сложение и умножение элементов матриц понимаются в смысле данного идемпотентного полукольца , а именно:

1) суммой матриц и типа называют матрицу того же типа с элементами , и используют обозначение ;

2) произведением матриц типа и типа называют матрицу типа с элементами

Нулевая и единичная матрицы любого порядка определяются с помощью единицы и нуля полукольца.

На множестве всех квадратных матриц фиксированного порядка можно определить алгебру

Теорема 3.8. Алгебра есть идемпотентное полукольцо. Если полукольцо замкнуто, то полукольцо тоже замкнуто.

Операции суммы и произведения матриц определены таким образом, что все свойства операций сложения и умножения в полукольце сохраняются и для соответствующих операций над матрицами. Поэтому для суммы и произведения матриц из выполнены аксиомы полукольца, и, кроме того, операция сложения матриц идемпотентна. Следовательно, — идемпотентное полукольцо.

Выясним смысл отношения порядка в этом идемпотентном полукольце. В силу определения естественного порядка идемпотентного полукольца неравенство для матриц и означает, что , или для всех справедливо . Следовательно, тогда и только тогда, когда для всех справедливо .

Пусть — замкнутое полукольцо. Докажем замкнутость идемпотентного полукольца и существование точной верхней грани у любой последовательности матриц в .

Пусть — произвольная последовательность квадратных матриц порядка . Рассмотрим матрицу . Каждый элемент этой матрицы есть точная верхняя грань последовательности элементов . Эти точные верхние грани существуют, поскольку — элементы замкнутого полукольца . Так как сложение матриц и отношение порядка в полукольце матриц определяются поэлементно, то матрица и будет точной верхней гранью последовательности матриц .

Докажем теперь непрерывность умножения в , т.е. что для любой последовательности матриц и произвольной матрицы имеет место

Матрица есть точная верхняя грань последовательности . Тогда имеем

Элемент есть точная верхняя грань последовательности элементов матриц , т.е.

Используя непрерывность умножения в исходном полукольце , получаем

Используя непрерывность сложения, получаем

Аналогично доказывается, что .

Полукольцо матрицы

Полукольцо будем называть полукольцом матриц над полукольцом . Доказанная теорема позволяет нам применять к замкнутым полукольцам матриц над некоторым замкнутым полукольцом теорему 3.7 и решать произвольные уравнения вида (относительно неизвестной матрицы ):

соответственно, где — итерация матрицы в . Итерация матрицы играет в теории линейных уравнений в замкнутых полукольцах такую же роль, как обратная матрица в классической линейной алгебре.

Основную роль при решении задач теории ориентированных графов и теории формальных языков играют праволинейные уравнения вида (3.17), поэтому мы будем, как правило, рассматривать только их. Леволинейное уравнение (3.18) может быть проанализировано аналогично.

Мы доказали существование решений матричных уравнений в матричном полукольце над замкнутым полукольцом. Теперь нам необходимо разработать технику поиска их решений и применить ее к решению систем вида (3.16).

Полагая, что — j-й столбец матрицы , a — j-й столбец матрицы , уравнение (3.17) можно переписать как систему уравнений относительно неизвестных столбцов матрицы

Каждая система вида (3.21) есть матричная форма записи указанной выше системы (3.16). Поэтому наименьшее решение этой системы, как следует из (3.19), есть

Для поиска решения системы вида (3.21) можно воспользоваться методом последовательного исключения неизвестных, аналогичным классическому методу Гаусса.

Поскольку система уравнений вида (3.16) имеет решение, мы можем подставить его в систему и работать с уравнениями как с тождествами.

Рассмотрим процедуру решения системы уравнений (3.16). Запишем первое уравнение системы так:

Из первого уравнения системы выразим через остальные неизвестные, воспользовавшись формулой (3.14):

В формуле (3.23) выражение в скобках не содержит неизвестного . Подставляя (3.23) вместо в остальные уравнения, получаем систему из уравнении, которая уже не содержит

Приводя подобные члены в каждом уравнении системы, получаем:

Первое уравнение этой системы перепишем так:

Заметим, что не содержит и . Воспользовавшись соотношением (3.14), будем иметь

где не содержит неизвестных. Используя полученное выражение, исключаем из остальных уравнений.

Действуя подобным образом, на i-м шаге получаем

где выражение не содержит неизвестных, а выражение может содержать только неизвестные, начиная с (i+1)-го, то есть .

где выражения и не содержат неизвестных. Таким образом, исходная система (3.16) преобразована к «треугольному» виду: правая часть уравнения (3.28) не содержит неизвестных, уравнение (3.27) при в правой части содержит только одно неизвестное и каждое следующее уравнение при просмотре «снизу вверх» на одно неизвестное больше, чем предыдущее. Первое уравнение системы — уравнение (3.23) — в правой части содержит все неизвестные от до . На этом завершается первый этап алгоритма, который называют прямым ходом метода Гаусса.

Второй этап алгоритма, называемый обратным ходом метода Гаусса, состоит в последовательном нахождении значения всех неизвестных начиная с . Подставив в выражение для вместо правую часть (3.28), найдем . Затем определим , подставив полученные значения и в правую часть выражения (3.27) при , и так далее до тех пор, пока не найдем .

Замечание 3.2. Положив в уравнении (3.17), получим . Таким образом, чтобы вычислить итерацию матрицы , достаточно решить матричное уравнение (3.21) для всех при , равном j-му столбцу единичной матрицы .

Пример 3.6. Проиллюстрируем приведенную схему решения системы из двух линейных уравнений. Имеем

Из первого уравнения выразим — получим . Подставляя это выражение во второе уравнение, получаем

Подставляя этот результат в написанное выше выражение для xi, находим окончательное решение:

Особенно просто решение выглядит в случае тривиальной итерации, т.е. тогда, когда в полукольце итерация любого элемента равна единице полукольца (как в полукольцах ). В этом случае для системы из двух уравнений решение равно

Пример 3.7. Рассмотрим в полукольце (см. пример 3.3.г) систему линейных уравнений

Решим эту систему уравнений, следуя общему алгоритму. Из первого уравнения получаем

Отсюда . Подставляя в полученное выражение для , находим, что

Полукольца с итерацией

Не всякое бесконечное идемпотентное полукольцо является замкнутым. Однако можно заметить, что при решении линейных уравнений и систем требовалось вычисление точной верхней грани последовательностей специального вида, а именно нахождение итерации элементов. Поэтому помимо замкнутых полуколец интерес для приложений представляют так называемые полукольца с итерацией.

Под полукольцом с итерацией в данном контексте мы будем понимать идемпотентное полукольцо, которое является подполукольцом некоторого замкнутого полукольца и вместе с каждым элементом содержит его итерацию. Важнейшим примером такого полукольца является полукольцо регулярных языков.

Полукольцо называют подполукольцом полукольца , если множество есть подмножество множества , замкнутое относительно операций сложения и умножения полукольца , а также содержащее нуль и единицу полукольца .

Рассматривая в полукольце с итерацией произвольное линейное уравнение, т.е. уравнение вида (3.12) или (3.13), получаем следующие результаты. Во-первых, это уравнение имеет наименьшее решение, так как полукольцо с итерацией содержится в некотором замкнутом полукольце в качестве подполукольца. Во-вторых, это наименьшее решение снова окажется в этом же полукольце, поскольку носитель полукольца с итерацией замкнут относительно итерации. Таким образом, носитель полукольца с итерацией замкнут относительно операции нахождения наименьшей неподвижной точки любого линейного отображения (или ), где и — элементы .

Не составляет труда распространить этот результат на произвольные матричные уравнения. Можно доказать следующее утверждение.

Теорема 3.9. Если — матрица, все элементы которой принадлежат некоторому полукольцу с итерацией, то все элементы ее итерации также принадлежат этому полукольцу с итерацией.

Помогите с алгеброй. Поле вычетов по модулю

Здесь на сайте как-то кто-то писал решение к вот такой задачке

Решить систему уравнений в поле вычетов по модулю 7.

x + y + z = 1
4x + 2y + 3z = 1
x + 4y + 4z = 2

Вот собственно решение:

Значит, так. Поле вычетов по модулю 7 состоит всего из семи элементов:

При этом противоположные элементы будут выглядеть так:
-1 = 6
-2 = 5
-3 = 4
-4 = 3
-5 = 2
-6 = 1

Обратные элементы, соответственно, будут выглядеть так:
1/2 = 4
1/3 = 5
1/4 = 2
1/5 = 3
1/6 = 6

Разнообразные арифметические аксиомы ассоциативности, коммутативности и дистрибутивности сохраняются в неизменном виде.

Теперь можно решать исходную систему.

Из первого уравнения получаем:
x = 1-y-z = 1+6y+6z
Подставляем это в третье уравнение:
(1+6y+6z) + 4y + 4z = 2
1 + (6+4)y + (6+4)z = 2
1 + 3y + 3z = 2
1 + 3y + 3z + 6 = 2 + 6
3y + 3z = 1
y + z = 5
Подставляем это в первое уравнение:
x + 5 = 1
x + 5 + 2 = 1 + 2
x = 3
Подставляем это во второе уравнение:
4*3 + 2y + 3z = 1
5 + 2(y+z) + z = 1
5 + 2*5 + z = 1
5 + 3 + z = 1
1 + z = 1
z = 0
Тогда y = 5

Получаем ответ: x = 3, y = 5, z = 0

Подскажите пожалуйста, откуда взялось вот это :