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

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

Алевтина Шахова 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. Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. — М.: Мир, с.

Новый подход к решению систем уравнений в задачах дискретного логарифмирования

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Описание презентации по отдельным слайдам:

Новый подход к решению систем уравнений в задачах дискретного логарифмирования
Выполнила: Савельева А.А.
Научный руководитель: проф., к.т.н. Авдошин С.М.

Криптографические системы, основанные на сложности дискретного логарифмирования
Схема открытого распределения ключей Диффи-Хеллмана
Схема ЭЦП Эль-Гамаля
ГОСТ Р34.10-2001(Россия)
ANSI X9.62/63-2001 (США)

Алгоритмы дискретного логарифмирования в конечных полях, использующие факторную базу

Алгоритм Адлемана
Алгоритм COS
Index-calculus
Решето числового поля

Решение систем линейных уравнений в кольцах вычетов
Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2004 .

Постановка задачи
Решить систему n линейных уравнений c m неизвестными:
Операции сложения и умножения определены по правилам:
(здесь p — некоторое целое положительное число)

Сведение задачи к :

решению семейства систем над полями Галуа
решению системы над кольцом целых чисел
решению уравнения над кольцом матриц
Анализ методов решения систем линейных уравнений в кольцах вычетов

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

Сведение задачи к :

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

Метод сведения к решению системы над простыми полями: пример
Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: Институт проблем информационной безопасности МГУ, МЦНМО, 2004 .

Метод сведения к решению системы над простыми полями: пример (продолжение)
1
2
2

Метод сведения к решению системы над простыми полями: пример (продолжение)
3
1
2
3

Метод сведения к решению системы над простыми полями: пример (продолжение)
3
4
2
1

Метод сведения к решению системы над простыми полями: пример (продолжение)
По Китайской теореме об остатках:

Недостатки метода сведения к решению семейства систем над простыми полями

Решение не одной, а нескольких систем
Факторизация числа p: открытая проблема современной теории чисел (не существует алгоритма с полиномиальной сложностью)

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

Сведение задачи к :

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

Метод сведения к решению системы над кольцом целых чисел (1): пример
Сведение:

Общее решение:
экспоненциальный рост коэффициентов
Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. — М.: Мир, 1999.

Метод сведения к решению системы над кольцом целых чисел (2): модификации
Способы избежать экспоненциального роста коэффициентов:

Использование диагональной формы Смита
Модификация метода Гаусса

Недостаток:
Асимптотическая временная и емкостная сложность значительно больше сложности метода Жордана решения систем в полях Галуа
Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. — Нижегородский Государственный Университет им. Н.И. Лобачевского. – 2002.
Полиномиальный рост коэффициентов

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

Сведение задачи к :

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

Метод сведения к уравнению над кольцом матриц

Ax=b
x=A-1b
Елизаров В.П. Успехи мат. наук. – 1993. Т. 48, вып. 2. с. 181-182.

Эффективный алгоритм вычисления обратной матрицы
?
Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра (в 2-х т). Т. I — М.: Гелиос АРВ, 2003

Предложенный метод
В основе:
Расширенный алгоритм Евклида
Схема Жордана
Применим для:
колец вычетов
полей Галуа
Эффективность:
По временной и емкостной сложности эквивалентен классическим алгоритмам Жордана и Гаусса решения систем в полях Галуа

Расширенный алгоритм Евклида
АЛГ Евклид(a,b)

К.Ц.
К.АЛГ.
Вход:
Выход: d, x, y, r, s такие, что

Матрицы над кольцом
Опр.2 Матрица называется строчно эквивалентной матрице если она может быть получена из A с помощью конечной последовательности элементарных преобразований строк.
Элементарными преобразованиями строк матрицы называют:
умножение любой ее строки на обратимый элемент кольца R;
прибавление к любой ее строке другой строки, умноженной на произвольный элемент кольца R;
транспозицию строк.
Опр.1 Множество всех матриц размером m x n с элементами из кольца R будем обозначать через Rm,n

Применение алгоритма Евклида к матрице
Коэффициенты Безу для a=26, b=9 :

Работа алгоритма
Решение системы:

Вычисление обратной матрицы:

Алгоритм
АЛГ Жордан(А, n, m, p)
ДЛЯ i=1 ДО n ЦИКЛ
<обнуляем эл-ты i-го столбца ниже i-й строки>
ДЛЯ j=i+1 ДО n ЦИКЛ

Алгоритм (продолжение)
ЕСЛИ НОД(aii, p)>1
ТО выйти из алгоритма <матрица вырождена>
ИНАЧЕ

Временная сложность алгоритмов
Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. — Нижегородский Государственный Университет им. Н.И. Лобачевского. – 2002.

Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра
(в 2-х т). Т. I — М.: Гелиос АРВ, 2003
Елизаров В.П. Успехи мат. наук.–1993.Т. 48, вып. 2.

Метод сведения к уравнению над кольцом матриц
Метод сведения к диофантовым уравнениям
(с построением матрицы Смита)
Метод сведения к полям Галуа
Метод, предложенный в данной работе
Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: Институт проблем информационной безопасности МГУ,
МЦНМО, 2004

Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ № 2005612258: «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ 02.09.2005

Временная сложность алгоритмов
Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ № 2005612258: «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ 02.09.2005
Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. — Нижегородский Государственный Университет им. Н.И. Лобачевского. – 2002.

Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра
(в 2-х т). Т. I — М.: Гелиос АРВ, 2003
Елизаров В.П. Успехи мат. наук.–1993.Т. 48, вып. 2.

Метод сведения к уравнению над кольцом матриц
Метод сведения к диофантовым уравнениям
(с построением матрицы Смита)
Метод сведения к полям Галуа
Метод, предложенный в данной работе

Временная сложность алгоритмов
Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ № 2005612258: «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ 02.09.2005
Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра
(в 2-х т). Т. I — М.: Гелиос АРВ, 2003
Елизаров В.П. Успехи мат. наук.–1993.Т. 48, вып. 2.

Метод сведения к уравнению над кольцом матриц
Метод сведения к диофантовым уравнениям
(с построением матрицы Смита)
Метод сведения к полям Галуа
Метод, предложенный в данной работе

Временная сложность алгоритмов
Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ № 2005612258: «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ 02.09.2005
Метод сведения к уравнению над кольцом матриц
Метод сведения к диофантовым уравнениям
(с построением матрицы Смита)
Метод сведения к полям Галуа
Метод, предложенный в данной работе

Временная сложность алгоритмов
Метод сведения к уравнению над кольцом матриц
Метод сведения к диофантовым уравнениям
(с построением матрицы Смита)
Метод сведения к полям Галуа
Метод, предложенный в данной работе

Решение систем, возникающих при дискретном логарифмировании
Свойства:
Большой размер (миллионы уравнений с миллионами неизвестных)
Разреженные матрицы

Поля: структурированное гауссово исключение

Кольца: модифицированный алгоритм структурированного гауссова исключения

Заключение
Результаты, полученные в данной работе:
Проведен анализ известных методов решения систем линейных уравнений над кольцом вычетов
Разработан алгоритм, эквивалентный по сложности методам Жордана и Гаусса решения систем линейных уравнений над полями Галуа
Программа, реализующая разработанный алгоритм, зарегистрирована Федеральной службой по интеллектуальной собственности, патентам и товарным знакам (Роспатент)
Результаты исследований опубликованы в журнале «Информационные технологии» (№2, 2006)

Направление дальнейшей работы
Теоретическое и экспериментальное исследование влияния полученного метода на временную сложность алгоритмов дискретного логарифмирования, использующие факторную базу:
Алгоритм Адлемана
Index-calculus
Алгоритм COS
Решето числового поля

Кольца вычетов
Операции сложения и умножения определяют кольцо вычетов по модулю p . Оно является коммутативным кольцом с единицей.

Опр.1 Делителем нуля в произвольном кольце R называется любой его элемент для которого в R существует элемент удовлетворяющий условию a ·b=0 или b ·a=0

Опр.2 Обратимым элементом в произвольном кольце R называется любой его элемент для которого в R существует обратный элемент a-1, удовлетворяющий условию a · a-1 =1 или a-1 ·a=1

Обратный элемент
Элемент называется обратным к , если
Для нахождения обратного элемента нужно решить линейное диофантово уравнение:
Уравнение разрешимо относительно u и v тогда и только тогда, когда НОД(x,p)=1; в этом случае Для вычисления u и v (коэффициентов Безу) используется расширенный алгоритм Евклида.

Пример решения системы в поле Галуа порядка 37

Пример решения системы в кольце вычетов по модулю 36
Все коэффициенты системы являются делителями нуля, т.е. необратимы. Однако решение существует и единственно:

Вычисления в полях вычетов

Рассмотрим некоторые особенности вычислений в полях вычетов. Найдем, например, определитель , элементы которого суть вычеты из поля
(Z₃, +₃, ×₃). Если действовать «по науке», надо писать

Можно, однако, поступить проще. Будем считать элементы определителя обычными целыми числами из кольца Z, тогда d=1×1–2×2= –3.

Как найти для целого числа из Z соответствующий вычет из Z_n? Для этого надо к числу прибавить (или отнять от него) величину, кратную n, чтобы результат принадлежал множеству вычетов Z_n=<0,1,¼,n–1>. В данном случае прибавим 3 и получим –3+3=0 – тот же результат.

В дальнейшем станем действовать аналогично, к тому же не будем педантично ставить индекс +_n, ×_n около символов операций, обозначая их просто + и
× , если значение индекса n ясно из контекста.

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

Пример. Решим над тремя полями: Q, Z₃, Z₅ систему уравнений A×X=B, где . т.е.

Заметим, что коэффициенты системы (0, 1 и 2), включая свободные члены, можно рассматривать не только как числа (т.е. элементы поля Q), но и как элементы интересующих нас конечных полей Z₃ и Z₅. В противном случае постановку задачи пришлось бы как-то изменять.

Решать систему будем по правилу Крамера. Вычислим над полем Q четыре опре­делителя:

.

Значения неизвестных найдем по формулам Крамера: .

Приведем значения определителей в поле вычетов Z₃=<0,1,2>, получим: D=0, D_x=2, D_y=2, D_z=2. Видим, что над этим полем система несовместна.

Приведем значения определителей в поле вычетов Z₅=<0,1,2,3,4>: D=2, D_x=4, D_y=1, D_z=4. Значения неизвестных снова найдем по формулам Крамера: . Как понимать найденное значение неизвестной ? Дробь не является элементом поля Z₅, поэтому ее надо рассматривать как выражение, которое необходимо вычислить согласно правилам действий в этом поле: (поскольку произведение 2×3=6, а 6 в поле Z₅ переходит в 1). Итак, решение системы уравнений над полем Z₅ таково: x=2, y=3, z=2.

Сделаем проверку (символом Þ обозна­чен переход от целых чисел к вычетам по модулю 5). Первое уравнение: 1×2+2×2=6 Þ 1, второе уравнение: 1×3+2×2=7 Þ 2, третье уравнение: 2×2+1×2=6 Þ 1. Видим, что найден­ные значения вычетов удовлетворяют сис­теме уравнений над полем Z₅.

Решим ту же систему над полем Z₃ методом Гаусса. Составим расширенную матрицу: . Если бы мы решали систему над полем рациональных чисел Q, то первым шагом выполнили бы операцию (3)–2×(1). В поле Z₃ коэффициенту –2 соответствует вычет 1, поэтому выполним операцию (3)+1×(1). В 1-ом столбце имеем 2+1×1=3Þ0, во 2-ом столбце сохранится 0, в третьем столбце 1+1×2=3Þ0, в столбце свободных членов 1+1×1=2, так что . В алгебраической форме 3-е уравнение этой системы имеет вид 0×x+0×y+0×z=2. Очевидно, что оно не имеет решения, поэтому система над полем Z₃ несовместна.

Найдем решение той же системы над полем Z₅ методом Гаусса. Вместо операции (3)–2×(1), с которой начинается решение этой системы над полем рациональных чисел Q, выполним операцию (3)+3×(1), поскольку в поле Z₅ коэффициенту –2 соответствует вычет 3. В 1-ом столбце получим 2+3×1=5Þ0, во 2-ом столбце сохранится 0, в третьем, в 3-ем столбце имеем 1+3×2=7Þ2, в столбце свободных членов 1+3×1=4. Таким образом, получим . 3-ю строку этой матрицы можно сократить (разделить) на 2: .

Теперь выполним операции (1)+3×(3) и (2)+3×(3) – в 1-й и во 2-й строках 3-го столбца получится 2+3×1=5Þ0, остальные элементы этих строк сохраняться: .

Видим, что получилось решение, ранее найденное по правилу Крамера: x=2, y=3, z=2.